2. 南京工业大学 计算机科学与技术系, 南京 210009;
3. 南京邮电大学 宽带无线通信与传感网技术教育部重点实验室, 南京 210003
提出基于独占区域的无线传感器网络连通支配集算法.采用独占覆盖和延时等待规则, 在每个节点维护的独占区域内限制支配节点数目, 从而降低连通支配集的规模.根据节点剩余能量信息优化支配节点在整个网络拓扑中的分布, 以提高能量使用效率和均衡网络负载.仿真结果表明, 基于独占区域的无线传感器网络连通支配集能够显著降低连通支配集的规模, 保证支配节点的分布均匀稀疏, 同时延长整个网络的生命周期.
2. Department of Computer Science and Technology, Nanjing University of Technology, Nanjing 210009, China;
3. Key Laboratory of Broadband Wireless Communication and Sensor Network Technology, Nanjing University of Posts and Telecommunications, Ministry of Education, Nanjing 210003, China
An exclusive-area-based connected dominating set algorithm is proposed for wireless sensor networks. Using exclusive covering and back-off delay rules, each node maintains an exclusive area where at most one dominating node exists so as to reduce the size of connected dominating set. According to node residual energy, the distribution of dominating nodes to enhance energy efficiency and balance network load are optimized. Simulation results demonstrate that the exclusive-area-based connected dominating set can reduce connected dominating set size along with a sparse distribution, and prolongs network lifetime.
在无线传感器网络应用过程中，大量中间节点参与转发数据容易导致数据冗余和传输冲突，出现类似广播风暴的问题[1-2].作为一种特殊的分簇形式，虚拟骨干网在传感器网络中能节约能耗和提高路由效率[3-4].构造虚拟骨干网的重要手段是连通支配集(CDS, connected domination set)，网络中的任意节点与支配节点之间最多相继一跳.基于CDS的节能路由方法能否获得良好的效率，直接依赖于CDS的规模以及生成、维护CDS的开销.在固定网络拓扑中，通常希望在保证可靠性和效率的同时尽可能降低CDS的规模[5-8].
通过研究发现，现有的算法大多只考虑连通支配集的规模，而忽略了支配节点的分布状况，不利于整个网络的负载均衡.鉴于此，提出一种基于独占区域的连通支配集算法，基于独占覆盖和延时等待规则，在各自的独占区域内控制支配节点的数目，从而降低了连通支配集的规模.同时，综合考虑节点的剩余能量，使支配节点的分布更加均匀稀疏，从而均衡网络负载，延长网络生存周期.
1 网络模型和相关定义采用单位圆盘图(UDG, unit disk graph)模型(即无向图G=(V, E))描述传感器网络的拓扑结构，V为节点集合，E为链路集合.网络拓扑中节点通信半径相同，两节点间有链路存在的条件是两节点之间的欧几里得距离不大于其通信半径.
定义1 1跳邻居集合N1(v)
无向图G=(V, E)中，对于节点v∈V，节点v的1跳邻居集合N1(v)={u∈V|(u, v)∈E, u≠v}.
定义2 节点集V′覆盖的邻居节点集合N(V′)
无向图G=(V, E)中，对于节点集合V′，节点集合中所有节点的一跳邻居集合为N(V′)={N1(v)|v∈V′}.
定义3 连通支配集
无向图G=(V, E)中，若存在节点集合V′(⊆V)满足：
1) 由节点集合V′导出的子图是连通图；
2) 图G中任意节点v∈V，满足v∈N(V′)∪V′.
则称该节点集合V′为CDS.
定义4 支配节点集合Ck(v)
无向图G=(V, E)中，节点v的k跳邻居支配节点集合记为Ck(v)={u|u∈Nk(v), u为支配节点}.
定义5 节点独占区域
节点v的通信范围内存在区域β，其所覆盖的节点集合记为β(v)，若满足β(v)⊆N1(v)和|β(v)∩Ck(v)|≤1，则称β为节点独占区域.
如图 1所示，图中R表示节点的通信半径，虚线范围内区域为节点独占区域β，该区域内不允许除中心节点以外的节点成为支配节点，空心节点表示普通节点，实心节点表示在独占区域β之外被选中的支配节点.
|
图 1 独占区域 |
定义6 自适应因子α
用于决定节点独占区域的大小，根据节点连通情况进行自适应调整.
2 独占规则在构建连通支配集的过程中，α值可以自适应地进行调整.如图 1所示，α决定了以αR为半径的独占区域的范围. α初始值由邻居节点分布稀疏程度决定，取值范围为[0.5, 1]；在不对节点分布进行定量的密度分析情况下，以平均节点度进行区分.为防止节点过早死亡，对于邻居节点个数不超过6的节点(位于稀疏分布区域)，α为0.5；若邻居节点个数大于6，α为0.75. α为1表示节点的独占区域是其整个通信范围，用于限制权值低于该节点的邻居节点成为支配节点.
在支配节点补充阶段，α值可根据节点的连通状况在[0, 1]范围内进行适应性调整.对于在邻居范围内连通的节点，α为1时表明节点不需要参与支配节点竞争；对于邻居范围内尚未连通的节点，将α设为0.05，这一取值不考虑邻居范围内节点分布稀疏程度，目的是增加符合条件的连通节点的存在范围；α为0时表示独占区域内只有中心节点本身.
基于独占区域的无线传感器网络连通支配集(EACDS, exclusive-area-based connected dominating set)算法通过独占覆盖和时延等待2种策略的相互结合，共同作用，减小连通支配集规模，同时使得支配节点分布更为均匀.
1) 独占覆盖
节点参与支配节点的选举过程中，节点计算α值，从而决定节点的独占区域β，使得该区域内的支配节点只能存在于区域β之外.在连通支配集形成初期，在节点的独占区域内，检查是否已有其他邻居支配节点存在，若存在，则标记M(v)=T，否则标记M(v)=F.后期补充连通节点时，在节点邻居范围内，检查邻居支配节点是否连通，若连通，则标记M(v)=T，反之标记M(v)=F.
2) 延时等待
在t时刻，节点参与支配节点的选举，根据算法执行的阶段和自身节点的权值，计算节点的等待延迟时间ε.在
为了防止支配节点能量耗尽，每个支配节点设置一个能量阈值，记为δ，将节点v的剩余能量值记为R(v).若满足R(v)＞δ，则节点v有成为支配节点的可能；否则只能作为源节点和目的节点收发消息，且不具有竞争支配节点的权利. δ值的设置需要满足一轮时间内节点通信的能耗需求.此外，采用节点的度作为支配节点选择依据，使得支配节点通信范围内覆盖的邻居个数增多，从而有利于减少支配节点数目.
所有剩余能量值大于能量阈值的节点，在1跳范围内交换信息，根据式(1) 计算相应节点的权值，用于决定每个节点成为支配节点的优先级.
|
(1) |
其中：N表示节点v所在网络拓扑中节点数目；N1(v)为节点v一跳邻居节点的集合，|N1(v)|表示相应的节点数目；dvj表示节点v到邻居节点j的距离；W1和W2为权重参数，可根据具体应用场景进行调节，如节点能量初始值不同时倾向于节点剩余能量高的节点优先权值高，可提高W1，若在节点分布稀疏差别较大场景下，可提高W2.在剩余能量和邻居节点个数相同情况下，与邻居节点距离的平方和越大，表明该节点覆盖范围越大.实验过程中，W1和W2取0.001.
3.2 支配节点竞争节点v竞争成为支配节点的规则如下.
1) 节点v遵循延时等待规则，根据式(2) 计算节点v的等待延迟时间ε，延时时间与λ(v)值成反比例关系，即权值大的节点延时等待时间短，从而有更高的优先级成为支配节点.式(2) 中θ为周期调整参数，用于调整等待延迟时间的取值范围.
|
(2) |
通过多次实验分析，将θ设置为15. I为消息发送的时间间隔，设置为1 000 ms.
2) 在等待延迟时间内，节点v根据收到的消息更新支配节点集合C1(v)，并对M(v)进行标记，表示节点的独占区域内已经存在其他支配节点.
3) 等待延迟时间过期后，节点v没收到任何竞争支配节点的广播消息，则若标记M(v)=F，表示节点v的独占区域内并无其他支配节点存在，根据独占覆盖规则，节点v发送广播消息，竞争成为支配节点；若M(v)=T，表示节点v的独占区域内已经存在其他支配节点.同样，已存在的支配节点需要维护自身的独占区域不被共享，从而迫使节点v放弃成为支配节点的权利.
节点通过采用延时等待规则，优先选择出对于减小虚拟骨干网规模起关键作用的一些节点，使得这些节点能优先成为支配节点，有利于降低连通支配集的规模，同时有利于虚拟骨干网的稳定.
3.3 连通节点补充部分节点在初始阶段优先成为支配节点，并维护各自独占区域内至多1个支配节点存在.然而，由于网络中存在的CDS碎片，因此有必要增加支配节点.对于局部已经连通的支配集，适度增加支配节点也有助于防止个别节点能耗过快死亡导致CDS断开，也有利于形成相对较短的路径.
节点v根据延时等待规则竞争成为支配节点.在选择补充节点时，通过节点的独占覆盖和延时等待规则，优先选择对于网络连通起关键作用的节点.本阶段只有非支配节点才可以参与到补充连通节点的过程中，相应的执行过程如下.
1) 非支配节点检查两跳邻居范围内支配节点之间的连通性，若存在不连通情况，采用独占覆盖规则，节点动态地调整α值.
2)在竞争成为支配节点之前，节点依照延时等待规则，根据式(3) 计算发送补充支配节点的消息的延迟时间γ
|
(3) |
其中μ表示为
|
(4) |
其中，C2(v)为节点v两跳范围的支配节点集合；random()为(0, 0.1) 之间的随机数，减少冲突概率.等待延迟时间过期后，节点v再次检查邻居范围内支配节点是否连通，若仍然未连通，则标记M(v)=F，反之，若此时节点v邻居范围内已经满足连通性，则标记M(v)=T.
3) 依据独占覆盖规则，节点v判断M(v)的值，若M(v)=T，表示此时邻居范围内已经有其他节点成为支配节点，可以连通各CDS碎片，节点v放弃成为支配节点；若M(v)=F，表示邻居范围内没有其他节点成为支配节点，或支配节点数目仍然不能保障CDS碎片实现连通，则节点v宣布成为支配节点.
补充连通节点过程结束后，网络进入稳定阶段，形成虚拟骨干网，相应的节点可以进行数据传输.
4 性能分析与评价4.1 实验设计通过仿真方法对EACDS进行性能分析.在200 m×200 m的目标区域内随机分布300个传感器节点，节点通信半径为30 m，初始能量相同.支配节点选择阶段中，节点密集和稀疏区域节点的α初始值分别设为0.75和0.5；连通节点补充阶段中，非连通和连通节点α分别设为0.05和1.结果数据为多次随机实验求得的平均值.
选取典型的连通支配集算法，包括多点中继算法(MPR)[9]，k跳减枝算法(Rule_k)和基于连通度的k跳减枝算法(Rule_k_D)[10]，这里将k设为3，与EACDS进行性能对比分析.
无线传感器网络的生命周期主要取决于数据发送和传输消耗的能量.这里采用文献[7]介绍的能量模型，该模型中路由查找和路由更新信息取决于整个拓扑的大小.
仿真实验考虑了如下性能分析指标.
连通支配集规模：连通支配集中节点个数.
平均最短路径：虚拟骨干网平均最短路径.
节点死亡时间：即节点死亡轮数.
4.2 结果分析对比了连通支配集规模(见表 1). EACDS相比MPR算法产生的支配节点数减小26.3%.该算法使得支配节点可覆盖的邻居数目增多，因此，支配节点数目的减少是必然的. MPR算法单纯采用节点ID作为连通支配节点选择的依据，不利于减小连通支配集规模，如ID为0的节点在任何情况下都会被选中. Rule_k_D相比Rule_k形成的连通支配集规模有明显降低，但仍然比EACDS高24.1%.
|
表 1 算法对比 |
图 2给出了MPR和EACDS算法所形成的虚拟骨干网分布，A~F分别为标记的各个局部区域，a~c为标记的节点.从图 2(a)中可知MPR算法生成的虚拟骨干网支配节点分布不均匀，如节点密集区域(如B)支配节点个数较多，而节点稀疏区域(如A和C)支配节点稀少，容易导致支配节点能耗过多. EACDS算法形成的支配节点分布相比MPR更均匀.在节点密集区域B附近，支配节点明显降低.这是因为独占覆盖和延时等待规则有效抑制了支配节点的数目.此外，引入α因子有利于解决稀疏区域中支配节点稀少甚至没有的问题. 图 2(b)中，在节点较为稀疏的D和F区域，支配节点数目增多，较图 2(a)中A和C区域有明显的改善.
|
图 2 支配节点分布 |
同时对比了虚拟骨干网中平均最短路长度(见表 1). EACDS算法产生的连通支配集的支配节点数目少于MPR等算法，而EACDS算法生成的虚拟骨干网的平均最短路径却优于其他算法.其他算法形成的支配节点之间的距离较远且分布不均匀，如MPR算法形成的虚拟骨干网(见图 2(a))，支配节点a到b的最短路径至少要通过支配节点c.而EACDS算法中支配节点分布较为均匀，尽管连通支配规模更小，平均最短路径却比MPR更短.
统计了各算法对应的节点死亡时间(见表 2). MPR和Rule_k_D等算法支配节点的选取以节点编号和连通度为依据，只要没有节点死亡，每一轮连通支配集中的节点都是相同的.而EACDS算法中是以节点的权值作为支配节点的选择依据，充分考虑了节点能量和局部拓扑信息，构成连通支配集的节点是动态变化的，使得每个节点成为支配节点的概率降低，从而均衡网络能耗，同时延长网络生存时间.
|
|
表 2 节点死亡时间对比 |
提出了EACDS算法.节点通过独占覆盖和延时等待规则的共同作用维护自身的独占区域，保障独占区域内仅有较少支配节点存在，从而减小了连通支配集的规模，使得支配节点分布更为均匀稀疏.仿真结果表明，EACDS在连通支配集规模、节点分布、能量使用效率等方面优于现有典型的分布式连通支配集构造算法.
| [1] | Ding L, Wu W, Willson J, et al. Efficient algorithms for topology control problem with routing cost constraints in wireless networks[J].IEEE Transactions on Parallel and Distributed Systems, 2011, 22(10): 1601–1609. doi: 10.1109/TPDS.2011.30 |
| [2] | Qu L, Ahmet S, Nallasamy M. Alow-cost flooding algorithm for wireless sensor networks[C]//WCNC. Hong Kong: IEEE Press, 2007: 3495-3500. |
| [3] | Du H, Wu W, Ye Q, et al. CDS-based virtual backbone construction with guaranteed routing cost in wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems, 2013, 24(4): 652–661. doi: 10.1109/TPDS.2012.177 |
| [4] | Thai M T, Tiwari R, Du D Z. On construction of virtual backbone in wireless ad hoc networks with unidirectional links[J].IEEE Transactions on Mobile Computing, 2008, 7(9): 1098–1109. doi: 10.1109/TMC.2008.22 |
| [5] | Wu J, Dai F. Broadcasting in Ad hoc networks based on self-pruning[C]//INFOCOM. San Francisco: IEEE Press, 2003: 2240-2250. |
| [6] | Wu J, Lou W, Dai F. Extendedmultipoint relays to determine connected dominating sets in MANETs[J].IEEE Transactions on Computers, 2006, 55(3): 334–347. doi: 10.1109/TC.2006.40 |
| [7] | Wu J, Dai F, Gao M, et al. On calculating power-aware connected dominating sets for efflcient routing in Ad hoc wireless networks[J].Journal of Communications and Networks, 2002, 4(1): 1–12. |
| [8] | Kim D, Wu Y, Li Y, et al. Constructing minimum connected dominating sets with bounded diameters in wireless networks[J].IEEE Transactions on Parallel and Distributed Systems, 2009, 20(2): 147–157. doi: 10.1109/TPDS.2008.74 |
| [9] | Qayyum A, Viennot. L, Laouiti A. Multipoint relaying for flooding broadcast messages in mobile wireless networks[C]//Proceedings of the 35th Hawaii International Conference on System Sciences. 2002: 3866-3875. |
| [10] | Dai F, Wu J. An extended localized algorithm for connected dominating set formation in Ad hoc wireless networks[J].IEEE Transactions on Parallel and Distributed Systems, 2004, 15(10): 908–920. doi: 10.1109/TPDS.2004.48 |