基于定向扩散的最小连通支配集构造算法.doc

第11期李克清等：基于定向扩散的最小连通支配集构造算法97基于定向扩散的最小连通支配集构造算法李克清，常晋义，王加年（常熟理工学院 计算机科学与工程学院，江苏 苏州215500）摘 要：针对区域覆盖算法未考虑节点的通信梯度问题，利用定向扩散路由在构造以sink节点为根的有向路由树时形成的递增梯度序列，提出了一种基于定向扩散的最小连通支配集构造算法。在路由信息扩散的同时逐级挑选出互不相邻的传感器节点构造出一个最大支撑集，然后在相邻层次的支撑集节点间寻找中间节点将独立集节点连通起来，最终得到一个近似的最小连通支配集。理论及仿真实验结果表明，该算法构造的连通支配集最小且计算耗时少，能多重有效覆盖热点区域，从而延长无线传感器网络的寿命。关键词：无线传感器网络；区域覆盖；最小连通支配集；定向扩散；轮换调度中图分类号：TN953 文献标识码：A 文章编号：1000-436X(2008)11-0091-07Minimum connected dominating set algorithm based on directed diffusionLI Ke-qing, CHANG Jin-yi, WANG Jia-nian(School of Computer Science and Engineering, Changshu Institute of Science and Technology, Suzhou 215500, China)Abstract: A new minimum connected dominating set algorithm based on directed diffusion MCDSDD was proposed, which attempted to improve the existed area coverage algorithms through introducing nodes gradient in wireless sensor networks. During built a directed tree rooted from sink node using directed diffusion routing algorithm, an ascending nodes gradient series could be constructed. Non-adjacent sensor nodes were picked out and made up a maximum dominator set during routing information diffusion gradient by gradient, and then some intermediate nodes are sought from those nodes, which were adjacent to both nodes unconnected in maximum dominator set and their gradients just between them yet, to “glue” the non-adjacent two nodes in maximum dominator set, and last, an approximate minimum connected dominator set was constructed. Simulation results show that MCDSDD can save time and multiple covers hot spot in the surveillance area, and prolong the life time of the WSN.Key words: wireless sensor networks; area coverage; minimum connected dominator set; directed diffusion; round-robin scheduling1 引言收稿日期：2008-06-21；修回日期：2008-10-20基金项目：江苏省教育厅高校自然科学基础研究自筹经费项目（08KJD520012）Foundation Item: The Natural Science Foundation of the Jiangsu Higher Education Institutions of China (08KJD520012)无线传感器网络（WSN, wireless sensor network）由大量的具有网络自组织能力的微型传感器组成，实时监测、感知和采集监测对象的各种参数，以多跳中继的方式将信息传送到管理者，实现“无处不在的计算”理念1,2。无线传感器网络与传统网络（包括WLAN、ad hoc网络和蜂窝移动电话网络）有着不同的设计目标。基于TCP/IP协议栈的Internet遵循“端到端”的边缘论设计思想35，将一切与功能相关的处理都放在网络的端系统上，中间节点仅负责数据分组的转发。蜂窝移动电话网络等能在高度移动的环境中通过优化路由和资源管理策略最大化带宽的利用率，同时也为用户提供一定的服务质量保证。无线传感器网络节点体积小、处理能力有限且靠自备电池供电，组成一种以数据为中心的网络结构，除少数节点需要移动外，大部分节点都是静止不动的。无线传感器网络的覆盖问题是其基础研究课题，已有文献证明覆盖问题是一个NP难题6。随机部署的传感器多采用飞行器进行空中抛撒，传感器节点在监测区域内十分稠密且具有分布不均匀性，监测区域中存在着大量的冗余节点。冗余节点不仅不能提高网络的监测质量，反而会增加大量的冗余信息加重WSN的传输负担，额外消耗传感器节点的能量。因此在满足一定网络覆盖质量的前提下，如何构造网络的最小覆盖连通节点集是传感器网络覆盖问题的主要研究目标。网络的最大独立集可构成网络的支配集，其大小有上限，因此不少学者提出先建立最大独立集，而后添加部分非独立集节点作为边界节点，以连通独立集节点构成连通支配集。Ivan Stojmenovic等学者提出了Ivan算法7，其思想是先并行构建最大独立集，而后添加边界节点，构成连通支配集。该算法采用最大权值构建最大独立集，其权值可以是编号、节点度和编号或节点度和坐标。Ivan算法的计算复杂度为O(n)，通信复杂度为O(n2)。由于其不加选择地添加边界节点，在极限情况下，其连通支配集尺寸等于全网的节点数目。Khaled M. Alzoubi等提出了一种基于生成树的连通支配集构造算法8，简称Khaled算法。其基本思想是先构造一棵生成树，由树根节点沿生成树建立层次关系，而后节点根据层次关系依次加入最大独立集。针对Khaled算法的并行性差的问题，Bohan等学者提出了Bohan算法9，改进了灰色节点的功能，使其能协调黑色节点的生成。Khaled算法和Bohan算法的通信复杂度均为O(n lg n)。堵丁柱等提出了一种基于触发的最大独立集串行构造算法10，简称Dudingzhu算法，该算法无需构造生成树，节点根据信令触发形成时间上的串行关系。Dudingzhu算法的通信复杂度为O(n)，计算复杂度为O(n)，其中为节点的最大度。Khaled算法、Bohan算法以及Dudingzhu算法均为基于生成树的最小连通支配集构造算法，区别在于Dudingzhu算法省去了构造生成树的过程。sink节点通常是WSN中的任务发起者，利用与sink节点通信时所形成的梯度关系建立相应的最小支配集，能更好地反映出WSN的逻辑拓扑，有效提高算法的收敛速度。2 最小连通支配集的构造算法节点随机部署的WSN中存在着大量的冗余传感器节点，网络中的连通支配集节点能独立完成网络的监测任务，因此在区域覆盖问题中，只要连通支配集中的节点不失效，监测区域就不会出现盲区，区域覆盖的服务质量就可以得到保证。当WSN中的节点足够稠密时，可以构造出尽可能多的互不相交的连通支配集（不妨记做S1，S2，Sn），系统让S1，S2，Sn轮流地在工作，休眠2个状态之间切换，从而在不降低网络覆盖服务质量的前提下，尽量地延长WSN的服务时间。D.R. Estrin等在文献11中提出的定向扩散路由（directed diffusion routing），可以按传感器节点到达sink节点的跳数划分成不同的梯度，节点的梯度表示其和sink节点间的相对距离，值越大表示距离sink节点的位置越远。定向扩散模型符合WSN以数据为中心的设计思想，节点感知的所有信息经过梯度逐渐递减的节点中继转发到sink节点，形成一条条汇聚到sink节点的监测数据流。以定向扩散的方式形成一个以sink节点为源节点的、逐级递增的节点梯度序列，接着逐级挑选出互不相邻的传感器节点构造出一个最大支撑集，然后在相邻层次的支撑集节点间寻找中间节点将独立集节点连通起来，最终得到一个近似的最小连通支配集。算法名称：基于定向扩散的最小连通支配集构造算法(MCDSDD, minimum connected dominating set algorithm based on directed diffusion)。约定：1) 节点具有惟一的标识；2) 节点的通信半径均相等，且假定感知半径小于通信半径的一半；3) 节点具有5种状态，各种状态均以颜色表示，分别为white，gray，green，red，black；4) 消息在节点内的排队时间可以忽略不计，消息满足遵循先发先至的原则；5) 消息格式为四元组（发送者的节点标识，发送者的层次，消息类型，发送者的颜色）。初始状态：所有节点的初始状态为白色，层次为1；记sink节点的标识为0。第1阶段：找出互不连通的节点集。发起者：sink节点。sink节点将自己的颜色标记为黑色，然后向其所有邻居节点发送dominator消息（0，1，dominator，black）。接收者：不同颜色的节点完成各自的处理。if( 接收者是白色节点 ) 当收到的是一条dominator消息（id0，h，dominator，black），则改颜色为灰色，调整层次为h1，随后向其邻居节点发送dominatee消息（id，level，dominatee，gray）；如果收到的是一条dominatee消息（id0，h，dominatee，gray），则改颜色为绿色，依次完成下面4个动作：1) 设置一个selecting超时定时器Timer；2) 调整节点所在的层次为h1；3) 置计数器kdominate1；4) 发送selecting消息（id，level，selecting，green）。如果收到的是selecting消息或selected消息，不作任何处理，直接丢弃。else if( 接收者是绿色节点 ) 如果收到的是一条selected消息（id0，h，selected，black），或者超时定时器Timer被触发，那么改颜色为灰色，并发送dominatee消息（id，level，dominatee，gray）。如果收到的是一条dominatee消息（id0，h，dominatee，gray），则将计数器kdominate增1。如果kdominate等于邻居节点的数目，那么改颜色为黑色，并发送selected消息（id，level，selected，black）。如果收到的是一条selecting消息（id0，h，selecting，green），且其节点标识idid0，则kdominate增1。如果kdominate等于邻居节点的数目，那么节点改颜色为黑色，并发送selected消息（id，level，selected，black）。如果收到一条dominatee消息，不作任何处理，直接丢弃。在构造最小连通支配集的过程中，共有8种不同的消息类型，如表1所示。表1MCDSDD中的消息类型表消息类型说明发送者颜色接受者颜色处理丢弃dominator选举扩散黑色白色Dominatee应答dominator灰色 白色，绿色 黑色，灰色selecting选举绿色 绿色，白色灰色selected宣告选举成功黑色绿色灰色connecting构造连通支撑集黑色灰色answer应答connecting灰色黑色announcement通知连通的优胜者节点黑色灰色join加入最小连通支配集红色黑色灰色在第1阶段执行过程中，节点只可能在白色、灰色、绿色和黑色4种之间进行变化，如图1所示。白色为所有节点的初始状态，绿色为中间状态，第1阶段之后，无线传感器网络中只有灰色和黑色节点。图1 节点的颜色转化定义1 在无线传感器网络中，与节点v能相互通信的节点w称为节点v的邻居节点。所有与节点v相邻的节点构成的集合称为节点v的邻居集，记做N(v)，即N(v)=w|dist(u,w)rc。集合N(v)的大小叫做节点v的度，记做d(v)。定理1 在无线传感器网络中，MCDSDD的第1阶段中节点间通信的消息数目为发送消息条数=|V|Vgreen|接收消息条数=，Vgreen表示图中颜色为绿色的节点集d(v)证明 在MCDSDD的第1阶段，节点间仅有4种通信消息：dominator，dominatee，selecting和selected，每个节点至少发送一条消息，最多发送2条消息。节点的初始颜色均为白色，根据收到消息种类的不同，将自身的颜色变换为黑色、灰色和绿色。仅发送一条消息的节点为1) 发起者sink节点的颜色自动变化为黑色，随后发送dominator消息。2) 白色节点在收到dominator消息后变换为灰色，随后发送dominatee消息。3) 白色节点在收到dominatee消息后变换为绿色，随后发送selecting消息。绿色是一种中间颜色，绿色节点在收集消息后将其颜色变换为黑色或灰色，然后发送第2条消息：selected消息或dominatee消息。根据上述分析，不难看出，每个节点均会发出一条消息，绿色节点还会多发送一条消息，以通知其邻居节点。因此，发送消息条数|V|Vgreen|。无线传感器网络采取广播方式通信，节点发送的每一条消息均会被其邻居接收，因此对于节点v发送的消息会被d(v)个邻居节点接收。所以有结论：接收消息条数=。证毕。引理1 无线传感器网络中，MCDSDD第1阶段的黑色节点至少存在有一个灰色邻居节点。引理1的结论显然。引理2 无线传感器网络中，MCDSDD第1阶段后的黑色节点与其上层相邻黑色节点的最大跳数为2。证明 每个黑色节点至少有一个上层的灰色邻居节点，不妨设黑色节点为u。分2种情形讨论：1) 若节点u是由白色节点直接变为黑色节点，表明节点u的上层节点只有一个灰色节点为v。此时，如果节点v的上层节点没有一个黑色节点的话，节点v应该变色为黑色，如图2(a)所示。因此节点v的上层节点中至少有一个黑色节点存在。2) 若节点u的颜色变化顺序是白色绿色黑色，表明节点u有多个的上层节点，它们分别发送收到dominatee给节点u，随后节点u与其邻居节点竞争，最后变为黑色。对于节点u的任何一个上层节点，不妨记做v。若节点v的上层节点均为灰色节点，如图2(b)所示，那么节点v的上层节点中至少应该变为黑色节点。综合上述，引理得证。图2 黑色节点u与其上层黑色节点的2种情形最小支撑集(minimum dominating set)中的节点互不连通，为了能将各个传感器搜集到的信息传回给sink节点，还需要将最小支撑集中的节点连通起来。经过算法的第一阶段，网络中的节点颜色要么为黑色（最小支撑集节点），要么为灰色。要使黑色节点变得连通，必须选择一些灰色节点作为中继节点，将黑色节点连接起来。由于第1阶段中的黑色节点处于奇数层，因此黑色节点在层次数低的方向上一定能找到另一个黑色节点。灰色节点的上下层均可能有黑色节点。第2阶段：构造最小连通支配集。发起者：sink节点在第1阶段结束后，向其下游节点发出connecting消息（0，1，connecting，black）。接收者：所有第1阶段的黑色、灰色节点以及本阶段产生的红色节点。if( 节点的颜色是灰色 ) 当收到一条来自上游节点的connecting消息（id0，h，connecting，black）时，则计算到节点标识为id0的邻居节点间的通信能耗E，随后发送answer消息（id，id0，answer，E）给其上游节点。当收到上游节点的announcement消息（id0，dest_id，announcement，black）时，如果dest_id=id，则改颜色为红色，并将自己加入到最小连通支配集中，随后发送join消息（id，level，join，red）给其下游黑色节点。else if( 节点的颜色是黑色或红色 ) 当第一次收到由红色节点发来的join消息（id0，h，join，red）时，如果level=h+1，则将自己挂接到最小连通支配集中，并向其下游节点广播一条connecting消息（id，level，connecting，black）。如果收到了所有下游灰色节点的通信能耗，则从中选择一个能耗最少的灰色节点，不妨记做dest_id，并将其加入到最小连通支配集中，并发送announcement消息（id0，dest_id，announcement，black）给dest_id节点。定理2 无线传感器中，MCDSDD的第2阶段节点间的通信消息数目为发送消息数=|V|M|接收消息数=+，其中M表示最小连通支配集。证明 无线传感器网络经过第1阶段的处理，网络中只剩下黑色和灰色2种节点，连通不同黑色节点的灰色节点会变色为红色，因此经过第2阶段的处理，网络中的节点有3种颜色，其中黑色和红色组成最小连通支配集。黑色节点发出connecting消息，所有处于其下游的灰色节点回应一条关于其通信能耗的answer消息。随后，黑色节点会根据收集的信息，选择作为连通的下游灰色节点，并发送一条announcement通知消息。对应的灰色节点在收到announcement消息后，将自身的颜色更新为红色，然后发送join消息，通知其下游黑色节点加入到连通的最小连通支配集中，如图3所示。图3 MCDSDD在第2阶段的消息传播顺序图在MCDSDD中，黑色节点发送connecting消息和announcement消息，灰色节点回应一条answer消息，红色节点则发送一条join消息。因此总的发送消息数目为2倍的黑色节点数目+灰色节点数目+红色节点数目（黑色节点数目+灰色节点数目）+（黑色节点数目+红色节点数目）|V|+|MCDS|。由于无线传感器网络采用广播介质，每发送一条消息，其邻居节点均会收到该消息，因此接收消息数+。由定理1和定理2可知，MCDSDD的总发送消息数目|V|+|Vgreen|+|V|+|M|2|V|+|Vgreen|+ |M|4|V|。即每个节点最多发送4条消息，因此网络中的通信开销不大。定理3 无线传感器网络中，MCDSDD是一个黑红交错图。证明 在MCDSDD的第1阶段，每个节点的初始颜色为白色。sink节点为黑色节点，sink节点的邻居节点在接收dominator消息之后，直接变化为灰色。灰色节点发送dominatee消息给其邻居节点，白色节点在收到dominatee消息后变化为绿色。绿色节点之间经过选举协商，优胜者作为支配集节点，变色为黑色，其他未被选中的节点变色为灰色。随后灰色节点发送dominatee消息给其邻居节点，黑色节点发送给其邻居节点，开始新一轮的支配集构造。重复上述过程，直到所有节点均变色为灰色或黑色为止。从MCDSDD支配集的构造过程中，黑色节点不可能相邻，否则表明有2个相邻的绿色节点同时被选举作支配集，与MCDSDD第1阶段算法相矛盾，因此黑色节点均互不相邻。在网络支配集的生成过程中，需要寻找一些灰色节点来连接相邻层次的黑色节点，使得支配集成为一个连通支撑子图。在MCDSDD的第1阶段，相邻层次的黑色节点之间至少有一个灰色节点，选择该灰色节点变色为红色节点，组成一个红黑相间的交错图。证毕。MCDSDD在第1阶段找出网络中的支配集，在第2阶段将先期找出的节点连通起来，构成传感器网络中的最小连通支配集，该支配集构成一个红黑交错图。定理4 MCDSDD构造出的连通支配集S的尺寸最多为最小连通支配集的8倍加1，即。证明 假定传感器网络内所有黑节点的集合为S1，所有红节点的集合为S2，则|S|=|S1|+|S2|。由图4 选定不同的起始节点，构成不同的红黑相间图于黑节点选择红节点存在着严格的时序关系，并且除sink外的每个黑节点只选择一个红节点作为其父节点，在不考虑几个黑节点选择了同一个红节点作为父节点的情况下，有|S2|S1|-1。根据最大独立集的性质有，因此有结论。对于同一个图，如果选定的起始节点不同，得到的红黑相间图也会有所区别，如图4所示。图4分别描绘了以给定节点u和节点v为起始点，顺序执行MCDSDD的2个步骤，得到不同的红黑相间图，其中以节点v为起点得到最小连通支配集。3 仿真与比较为便于把本文提出的MCDSDD与Bohan算法、Dudingzhu算法进行比较，在Windows XP下分别用VC+实现了3种算法。假定N个传感器节点随机均匀分布于一个方形监测区域内，监测区域半径的边长为L m，每个节点的通信半径定为rsm。假定网络中的节点平均度为d，则总的节点数目N约为。为了检验算法的有效性，对于每个度数分别生成50次网络随机拓扑结构，计算出每次支配集节点与总节点数目的比例，最后取其平均值。图5为MCDSDD、Bohan算法和Dudingzhu算法连通支配集尺寸的仿真对比，横轴为节点的平均度，纵轴为连通支配集节点总数与网内节点总数的比值。由图5可知，MCDSDD，Bohan算法和Dudingzhu算法在计算支配集的比例上差别不大，图5 连通支配集与节点总数的比例关系（正方形区域：边长为50m，节点的通信半径为10m）对应的曲线很靠拢。由于上述3种算法构造的连通支配集最极端的情况都是最小连通支配集的8倍左右。Dudingzhu算法在选择边界节点时没有利用时间上的先后关系，有可能会形成了环路，一定程度上会造成连通支配集比例偏大。Dudingzhu虽然在构造最大独立集方面占有优势，但在选择边点时却有可能选择更多的冗余节点。MCDSDD在选择边界节点时，也是和生成最小独立集的顺序一致，下游节点仅仅回答上游节点的问讯，一切决策交由上游节点完成，因此选择的边界节点中冗余节点会少一些，而且由于考虑了节点的能耗，使得网络的寿命也会相应延长。图6为上述模拟情形下的几种算法的计算耗时对比图。MCDSDD中的灰色节点仅将自身的通信能耗发给上游节点，一切计算和判断由上游节点完成，因此协议简单，计算耗时最少。Bohan算法需要构造生成树，这使得其协议较复杂。Dudingzhu算法在构造最大独立集和边界节点选取过程中，要进行多次比较，这使得其时延最大。图6 计算连通支配集的平均耗时（正方形区域：边长为50m，节点的通信半径为5m）4 结束语本文针对现有区域覆盖算法没有考虑节点距离sink节点的梯度问题，提出了一种基于直接扩散的最小连通支配集构造算法MCDSDD。该算法能有效地降低计算构造近似最小连通支配集的时间，并能实现多重覆盖。参考文献：1AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. A survey on sensor networksJ. IEEE Communications Magazine, 2002, 40(8): 102-114.2AGRAWL D P, ZENG Q A. 无线与移动系统导论（影印版）M. 北京: 高等教育出版社，2003.AGRAWL D P, ZENG Q A. Introduction to Wireless and Mobile SystemsM. Beijing: Higher Education Press, 2003.3INTANAGONWIWAT C, GOVINDAN R, ESTRIN D, et al. Directed diffusion for wireless sensor networkingJ. IEEE/ACM Trans on Networking, 2003,11(1): 2-16.4SALTZER J, REED D, CLARK D. End-to-end arguments in system designJ. ACM Trans on Computer Systems, 1984,2(4):195-206.5SHIH E, CHO S, ICKES N, et al. Chandrakasan A. Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networksA. Proc of the ACM MobiCom 2001C. ACM Press, 2001.272-286.6GAO S, VU C T,