前言

最近在学校做了无线传感器网络（WSN）睡眠调度算法方面的一些研究，本篇文章主要对其中的CKN、EC-CKN算法的学习做个总结，并给出基于这两种算法而改进后的ATR-CKN算法的核心实现以及在Nettopo上的运行结果。

CKN与EC-CKN算法

K-邻居节点连通算法（CKN）是一个有效的分布式睡眠/工作时序安排算法。该算法可以在有效的减少网络中处于工作状态的节点个数的同时保证整个网络处于连通状态和需求的路径延迟。执行CKN算法时对WSN中的每个节点u主要进行以下几步：

针对CKN算法在能量消耗方面存在的问题，基于能量消耗的睡眠/工作时序安排算法（EC-CKN）可以延长网络的寿命。EC-CKN算法利用节点当前的剩余能量信息作为参数来决定节点是否进入睡眠状态。EC-CKN算法不仅可以保证整个网络处于K邻居节点连通状态，同时还可以保证每个节点处于工作状态的K个邻居节点当前的剩余能量在所有邻居节点当前剩余能量排序中为最大的K个。

存在的问题

EC-CKN对CKN有了一定的改进，但在某些场景下仍然会存在一些问题，例如下文将介绍的死亡加速与网络隔离。

死亡加速

在下图的场景中，节点B有很多个邻居节点，按理是可以进入睡眠状态的，但是由于它的其中一个邻居节点A只有它一个邻居节点，因此节点A和B永远得不到睡眠机会，这导致的后果就是：节点B的能量很快就被消耗完了，而节点B周围原本刚好满足睡眠条件的节点由于少了一个醒着的邻居节点，睡眠的几率也因此下降，从而加速了整个网络的死亡。

网络隔离

类似于死亡加速，在下面的场景中节点A和B永远也得不到睡眠机会，因此会更快的消耗完能量，导致相连的两个网络被隔离开了。

ATR-CKN算法

ATR-CKN算法优于原始的基于CKN的睡眠调度算法，它的优势在于可以在物理上调整传感器节点的传输半径，从而执行CKN使部分节点进入睡眠状态。ATR-CKN算法在继承了EC-CKN算法的所有主要属性的同时，通过提高节点的睡眠率为延长网络生命周期做出了重要贡献。

相较于EC-CKN，ATR-CKN只用在之前加入一个判断逻辑即可：

核心实现

下面给出在Nettopo上对于ATR-CKN算法的实现，其关键在于执行EC-CKN之前加入下面一段判断逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private void ATRCKN_Function() {
//...
		boolean flag = false;
		Integer[] neighbors1 = neighbors.get(currentID);
		if(neighbors1.length < k) {
			while(!isUsingMaxTR(currentID)) {
				increaseTR(currentID);
				neighbors1 = neighbors.get(currentID);
				if(neighbors1.length >= k) {
					for(int j = 0; j < neighbors1.length; j++) {
						int tr = ((SensorNode)wsn.getNodeByID(currentID)).getMaxTR();
						((SensorNode)wsn.getNodeByID(neighbors1[j])).setMaxTR(tr);
					}
					flag = true;
					break;
				}
			}
			if(!flag) setDefaultTR(currentID);
		}
	//...
}

运行结果

下面将在Nettopo上简单的演示一遍ATR-CKN算法对于死亡加速问题的解决。

k = 2，round = 1的时候：

k = 2，round = 10的时候：

k = 2，round = 30的时候

k = 2，round = 43的时候：

由于增大了传感器节点的物理传输半径，可以看到两个关键节点都可以进入睡眠状态，以此延长了网络的整体寿命。虽然增大传输半径的同时也增加了能量消耗，但在进行了大量实验并对统计数据进行详细分析后，我们可以发现ATR-CKN的生命周期相比EC-CKN平均增加了19％，最大增加了41%，因此可以得出其更优于EC-CKN的结论。