基于区域划分的连通支配集协议

谢珊珊，白光伟，，曹 磊

（1.南京工业大学 计算机科学与技术系，江苏 南京210009；2.南京大学 软件新技术国家重点实验室，江苏 南京210093）

0 引 言

无线传感器网络是由大量自治节点通过多跳通信方式构建形成的自组织网络。由于通信范围受限、电池供电能量有限和较高的容错性能要求，传感器节点大多依赖于中间节点转发和接收消息。中间转发节点数目过多时，容易加重网络拥塞，容易导致类似广播风暴的问题［1－2］。分簇技术是一种能够优化能耗的拓扑控制技术，能减少冗余数据量，延长网络寿命，有效进行网内数据融合，减少数据报告延迟和增强网络的可扩展性［3－5］。作为一种特殊的分簇形式，虚拟骨干网在传感器网络中可获得良好的节能效果和路由执行效率［1，6－8］。虚拟骨干网的一种构造方法是通过构造整个网络的连通支配集 （connected domination set，CDS）。通常希望在保证网络功能、可靠性和效率的同时获得尽可能小的CDS。

现有的求解连通支配集的协议较多考虑CDS的规模大小［9－11］，并不着重考虑支配节点在网络拓扑中的分布情况，从而产生支配节点分布过于集中导致加快节点死亡等问题。本文在深入研究求解连通支配集的典型协议基础上，提出基于局域划分的连通支配集协议，保证CDS规模降低的同时，使得支配节点分布更加均匀。

1 相关工作

现有的构建CDS算法可分为集中型和分布式两类。集中CDS需要网络的全局信息，不适用于拥有大量节点的大规模网络，基于分布式的局部化算法只需要对于周围邻居内的n跳相邻信息，可以满足协议低消耗、快收敛的要求。

原始MPR机制提供了一种局部化且有效的方式，图1（a）和图1（b）分别表示传统洪泛广播和多点中继转发（MPR）广播方式，可看出MPR机制中节点转发的数据包较传统广播方式明显减少。文献 ［12］提出独立于源节点的创新方法来构造节点转发集合，并提出两条基于ID限制的简单规则构建 CDS。EMPR［13］对 MPR［12］的两条限制规则进行了改进，增加节点有两个不直接相连邻居的限制条件，并提出自由节点的概念。

图1 节点广播策略

无论 MPR［12］还是 EMRP［13］，支配节点的选取都是以节点ID作为评判标准，降低协议复杂度。但单纯依据节点的ID来选择中继节点，对于形成虚拟骨干网并不必要。同时MPR协议没有充分利用拓扑信息，部分支配节点更接近拓扑边界，覆盖邻居个数比拓扑中间支配节点相对减少，不利于形成更小规模的虚拟骨干网。

鉴于此，本文提出基于区域划分的连通支配集协议，根据网络的拓扑信息，分区域选择中继转发节点求解网络的CDS，均匀分布所有支配节点。

2 基于区域划分的连通支配集协议 （RPMPR）

本节提出一种基于区域划分的连通支配集协议RPMPR。我们详细介绍协议的具体机制，包括邻居节点分区策略、分区选择中继节点以及支配节点的选举策略。

2.1 相关定义

传感器网络研究中，一般采用用单位圆盘图 （unit disk graph，UDG）模型，即利用无向图G＝ （V，E）描述传感器网络的拓扑结构。V是节点集合，E为所有边的集合。为方便描述，给出以下相关定义。

定义1（1跳邻居集合N1（v）） 无向图G＝ （V，E）中，对于节点v∈V，节点v的1跳邻居集合N1（v）＝ ｛u∈V｜ （u，v）∈E｝。

定义2（节点集V’覆盖的邻居节点集合N（V’））无向图G＝ （V，E）中，对于节点集合V’，节点集合中所有节点的一跳邻居集合为N（V’）＝∪iN1（vi），vi∈V’。

定义3（2跳邻居集合N2（v）） 无向图G＝ （V，E）中，节点v的2跳邻居集合N2（v）＝N1（N1（v））－（N1（v）∪ ｛v｝）。

定义4（中继转发节点集） 无向图G＝ （V，E）中，对于节点v∈V，存在一个N1（v）的子集V’，满足N2（v）N（V’），N（V’）N2（v）。

定义5（连通支配集） 无向图G （V，E）中，若存在一个节点集合V’（V’V）满足：①由节点集合V’导出的子图是连通图；②图G中任意节点v∈V，满足v∈N（V’）∪V’。则称该节点集合V’为CDS。

2.2 基于拓扑信息的分区策略

2.2.1 分区策略

节点根据邻居节点信息，对所有邻居节点进行区域划分。分区过程中节点直接对邻居节点进行标记，不需要额外代价。分区情况如图2所示，具体步骤如下：

（1）节点u获取所有邻居节点信息，根据各个邻居节点的位置信息将一跳邻居节点分为3个区域；

（2）每个区域间隔120°，A1、B1、C1分别为三区域中节点集合；

（3）根据2跳邻居位置信息，将2跳邻居节点也相应A2、B2、C2区。

若X1（X∈ ｛A，B，C｝）区域非空，X2（X∈ ｛A，B，C｝）区域为空，此时设置X2＝N（X1），X2中节点称为虚拟节点，虚拟节点至少隶属于两个分区。

图2 邻居节点分区

2.2.2 中继节点选举策略

将节点的ID作为选择中继节点依据，容易导致部分节点单纯因ID较大 （较小）被选中，因此考虑节点的度作为选择支配节点的依据。邻居范围内度最大的节点一般相距2跳或3跳距离。

对于每一对区域X1、X2（X∈ ｛A，B，C｝），选择X1中1跳邻居节点覆盖X2中2跳邻居节点。从X1区域选择支配节点，若X1区域中已有节点p被选作支配节点，则节点u也选择节点p作为支配节点；否则，节点u从X1区域内选择支配节点，支配节点q∈X1，并且满足

节点的度相同则选择ID最小的节点作为支配节点。理想情况下邻居节点分区如图3所示。

图3 理想情况下分区选择中继节点

2.3 构造连通支配集

连通支配集构造算法步骤如下：

（1）初始化，所有节点默认成为非支配节点；

（2）邻居节点间进行消息交换，节点获得2跳内的所有邻居节点度信息和位置信息；节点u依据已知的邻居节点信息，按照2.1节中分区方法进行区域划分；

（3）按2.2节中继节点选举策略，A1区域进行中继节点选择；

（4）同时A2区域去除被覆盖节点，涉及到其他B2、C2区也去掉相关覆盖节点；

（5）同A1区域选择支配节点的算法，B1／C1／D1区域执行支配节点的选择；

（6）检查X2（X∈ ｛A，B，C｝）区，若有未被覆盖2跳节点集合非空，跳到步骤 （3）；

（7）以度为依据，选择合适的支配节点；

（8）结束。

图4是MPR［12］和RPMPR协议算法流程对比，不同之处用点划线框出。MPR采用的是贪心算法构建中继转发节点集，RPMPR则通过对邻居节点进行划分，分区域选择中继转发节点。RPMPR协议以节点的度作为选择支配节点的依据。

3 协议性能分析与评价

3.1 实验设计

本节采用网络仿真器ns2对第2节提出的RPMPR协议进行仿真分析。仿真实验基于IEEE 802.11协议MAC协层的DCF机制；300个节点随机分布在200＊200的矩形空间内；节点通信半径均为30m。仿真实验所有分析数据均为多次重复实验取平均值。

图4 协议算法对比

这里将RPMPR协议与几种代表性协议进行对比分析，包括 MPR［12］、WULI［14］、Rulek［15］（记为 Rulek （k）），以及采用节点的度作为选择依据的Rulek（记为Rulek（D，k））。本次实验考虑k＝3的情况。

仿真实验考虑的性能分析标准包括以下方面：

（1）连通支配集规模：即连通支配集中节点个数。

（2）平均最短路径：虚拟骨干网中的平均最短路径。

（3）健壮性：虚拟骨干网中移除支配节点导致网络必须重新构建虚拟骨干网的支配节点数上限。

3.2 结果分析

本文分析了RPMPR协议生成的连通支配集规模，分析了由连通支配集导出的虚拟骨干网分布情况，最后分析生成的虚拟骨干网的平均最短路径和健壮性。

图5是协议生成的连通支配集规模的比较，RPMPR协议产生的CDS较 MPR协议产生的节点数减小14.5%。MPR协议采用节点ID作为连通支配节点选择的依据，不考虑节点通信范围内邻居节点个数及其拓扑位置。选中的支配节点邻居个数少，则需要更多支配节点来覆盖整个网络，不利于形成更小规模的CDS，如节点ID为0的节点在任何情况下都被选中；RPMPR协议采用节点的度作为选择依据，支配节点连接的邻居个数增多，支配节点数目必然减少。Rulek（D，3）较Rulek形成的CDS规模也明显降低，但仍然比RPMPR协议多出7%。这表明RPMPR协议采用分区选择中继转发节点，支配节点分布更加均匀，较少数目的支配节点即可覆盖全网。

图5 连通支配集规模

图6描述的是各协议所形成的虚拟骨干网分布情况。MPR协议生成的虚拟骨干网，例如图6（a）中支配节点a就是这样的 “冗余”节点，图6（a）中还有其它类似因为ID较小而被选中的支配节点。图6（b）中Rulek（3）形成的虚拟骨干网中，支配节点分布相较图6（a）和图6（c）均匀，但支配节点数目较多，且部分支配节点分布靠近拓扑边界。图6（c）中Rulek（D，3）生成的虚拟骨干网，局部区域支配节点分布过于集中，如图6（c）中A、B、C这3个标记区域；支配节点较多，各支配节点覆盖的通信范围也相互重叠，降低控制冗余数据包和信号干扰的效果。从图6（d）可以看出，相较MPR和Rulek（D，3）所形成的虚拟骨干网，基于分区策略的RPMPR协议所形成的虚拟骨干网更集中于拓扑中间，支配节点分布更均匀。

图6 在200＊200m的矩形空间内形成的虚拟骨干网

图7 是各协议关于虚拟骨干网中平均最短路径参数的对比。RPMPR协议产生的CDS的支配节点个数比MPR协议的要少，而RPMPR协议生成的虚拟骨干网的平均最短路径却优于MPR。这是因为MPR协议中部分支配节点间距离较远，如图6（a）中支配节点A到节点B必须通过节点C，导致平均最短路径较长。Rulek（D，3）中局部支配节点分布更为密集，因而平均最短路径略端些。平均最短路径变长也是虚拟骨干网中骨干节点稀疏并且均匀分布所要牺牲的代价之一。

图7 骨干网平均最短路径

图8 描述了各协议关于虚拟骨干网健壮性的性能对比。可以看出，WULI产生的CDS规模较大，健壮性必然较好。相较于MPR和Rulek（3），RPMPR协议在维持更小规模的CDS的同时，健壮性更好。RPMPR的CDS规模比Rulek（D，3）协议减小了7%，健壮性比Rulek（D，3）略微降低。RPMPR协议产生的支配节点分布均匀，不仅有利于生成更小规模的虚拟骨干网，同时保障生成的虚拟骨干网仍具有良好的健壮性。

图8 骨干网健壮性

4 结束语

无线传感器网络中，利用连通支配集导出的虚拟骨干网可以有效应对传感器路由、节能等要求。如何求解网络中最小连通支配集合是其中的关键问题。本文提出一种基于区域划分的连通支配集求解协议 （RPMPR），充分考虑节点能获取到的拓扑信息，采取分区策略构建中继转发节点集，并以节点的度作为支配节点选择依据。仿真实验证明RPMPR形成的连通支配集规模更小，提高了支配节点分布的均匀性，能够较好地适应于节点密集型无线传感器网络。下一步的工作是进一步降低连通支配集规模，同时考虑全网节点能耗均衡，研究构建节点分布更加均匀的连通支配集算法。

［1］XIE Wenbin，LI Jiaming，CHEN Yongguang.Distributed virtue backbone network algorithm based on topology characteristic［J］.Journal of Software，2010，21 （6）：1416－1425 （in Chinese）.［解文斌，李佳明，陈永光.基于区域划分的分布式虚拟骨干网算法 ［J］.软件学报，2010，21 （6）：1416－1425.］

［2］QU L，Ahmet S，Nallasamy M.A low－cost flooding algorithm for wireless sensor networks ［C］.HK：Proceedings of IEEE WCNC，2007：3498－3503.

［3］Cantoni V，Lombardi L，Lombardi P.Future scenarios of parallel computing：Distributed sensor networks ［J］.Journal of Visual Languages ＆Computing，2007，18 （8）：484－491.

［4］ZHOU Xinlian，WU Min，XU Jianbo.BPEC－an energy－aware distributed clustering algorithm in WSNs ［J］.Journal of Computer Research and Development，2009，46 （5）：723－730 （in Chinese）.［周新莲，吴敏，徐建波.BPEC：无线传感器网络中一种能量感知的分布式分簇算法 ［J］.计算机研究与发展，2009，46 （5）：723－730.］

［5］SHEN Bo，ZHANG Shiyong，ZHONG Yiping.Cluster－based routing protocols for wireless sensor networks ［J］.Journal of Software，2006，17 （7）：1588－1600 （in Chinese）.［沈波，张世永，钟亦平.无线传感器网络分簇路由协议 ［J］.软件学报，2006，17 （7）：1588－1600.］

［6］Basagni S，Mastrogiovanni M，Panconesi A，et al.Localized protocols for Ad Hoc clustering and backbone formation：A performance comparison ［J］.IEEE Transactions on Parallel and Distributed Systems，2006，17 （4）：292－306.

［7］Teymoori P，Yazdani N.Local reconstruction of virtual backbone to support mobility in wireless ad hoc networks［C］.Proceedings of the Int’l Symp on Telecommunications，2008：382－387.

［8］WANG L，XIAO Y.A survey of energy－efficient scheduling mechanisms in sensor networks ［J］.Mobile Networks and Applications，2006，11 （5）：723－740.

［9］LU Gang，ZHOU Mingtian，TANG Yong，et al.A survey on exact algorithms for dominating set related problems in arbitrary graphs［J］.Chinese Journal of Computers，2010，33 （6）：1073－1087（in Chinese）.［路纲，周明天，唐勇，等.任意图支配集精确算法回顾 ［J］.计算机学报，2010，33 （6）：1073－1087.］

［10］LIAO Feixiong，MA Liang，FAN Bingquan.Efficient approximation algorithm for minimum connected dominating set［J］.Journal of Chinese Computer Systems，2008，29 （5）：875－878（in Chinese）.［廖飞雄，马良，范炳全.一种求解最小连通支配集的高效近似算法 ［J］.小型微型计算机系统，2008，29 （5）：875－878.］

［11］Rai M，Verma S，Tapaswi S.A heuristic for minimum connected dominating set with local repair for wireless sensor networks ［C］.Gosier，Guadeloupe：Proceedings of ICN，2009：106－111.

［12］Adjih C，Jacquet P，Viennot L.Computing connected dominated sets with multi－point relays ［J］.Ad Hoc ＆ Sensor Wireless Networks，2005 （1）：27－39.

［13］WU J，LOU W，DAI F.Extended multipoint relays to determine connected dominating sets in MANETs ［J］.IEEE Transactions on Computers，2006，55 （3）：334－347.

［14］WU J，LI H.On calculating connected dominating sets for efficient routing in Ad Hoc wireless networks［C］.Seattle，WA：Proceedings of ACM Int’l Workshop Discrete Algorithms and Methods for Mobile Computing and Communications，1999：7－14.

［15］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.