针对无法预估的节点故障影响无线传感器网络寿命的问题，提出了一种考虑节点磨损的分布式自稳定优化算法。利用韦伯函数拟合网络生命周期的分布，定期唤醒睡眠节点进行故障检测；采用分布式调度，无须知道传感节点的位置信息，使用多个节点同时工作，从而提高效率；最后，通过较低的网络通信代价，及时使用空闲节点替代故障节点，保持网络的连通性。理论分析和仿真实验验证了算法的有效性及可靠性。仿真结果表明，当传感器节点的可靠性随着使用时间与磨损下降时，算法可以更好地延长无线传感器网络寿命，相比分布式多目标概率覆盖协议，在寿命延长、覆盖率、节点唤醒次数等方面均取得了更好的性能。
第3期 明勇,等:WSN中考虑节点磨损的分布式自稳定网络寿命优化算法 829 因此可利用这一特性调节参数A=1,从而实现睡眠节点那么只有最小的谁一节点保持活动状态。 引理3如果节点执行了规则r,,那么它与它的邻居节点 检测速度的自调节。睡眠节点检测速度的自馮节有如下两个最多再执行一条规则且该规则必为r1。 优点:a)一个节点自调节检测吋间,无须知道其邻居节点的数 证明设i为执行r2的某个节点。当节点t进入活动状 量,此优点对于恶劣坏境中的无线传感器网络尤为重要;b)节态,其所有邻居节点处于睡眠或唤醒状态。所以有两种情况 点间无须发送消息来互相协调,减少了网终通信开销,节省了a)睡眠的邻居节点,该情况下没有冲突:b)唤醒的邻居节点, 能量。 这些节点l高于节点i 2.2问题2一解决方案 引理4如果节点不是睡眠状态,其最多执行两次规则。 因为两个相邻节点可能同时唤醒、检测,直没有有效的 证明显然每个节点最多执行一个规则。因此,唯一执行 解决方案能够解次每个监控区域中只存在一个活动节点的问两次的情况为,当其处于活动状态下,执行2及n1。 题。本文旨在利用高效的自稳定算法解决该问题,并提高网络 定理1本文算法在执行2n次规则内,使得无线传感器 生命期。首先作如下三个定义 网络达到白稳定的状态。 定义1设l为各传感节点的名字函数。ld(i)表小传感 证明按照自稳定系统理论,由引理2~4推断得到,本文 节点i的身份标志符,且节点的标志符唯一,即当i≠j,ld(i) 算法可保证在有限次步骤内达到合法状态,满足自稳定的条 hd(j)。 件 定义2一个传感节点有活动、唤醒、睡眠三种状态。节 推论1在节点标志符唯一的传感网中,本算法是自稳定 点i的状态表示为S(i) 的 定义3如S(i)=活动∧(Ⅴj∈N1:S(j)=睡眠∨唉醒) 证明当一个睡眠节点唤醒,其向附近邻居节点发送检测 节点i是控制状态,如(S()-睡眠V唤醒)∧(∈N)消息检测是否存在活动节点。如果有一个以上的节点同时被 (S()=活动),点i处于受控状态。 激活,那么通过比较唯一的标志符可以避免冲突,可见这满足 2.2.1问题分析 自稳定的条件。 假设G=(V;E)为传感网模型,=,2,…,为监控3理论分析 区域集,S={1,2,…,n}为传感节点集,Z中每个区域至少有 个S中的传感节点。O为区域z的邻居节点集合,1≤L≤k。3.1消息复杂度分析 每个邻节点j∈饣能够监控区域x(监控z中每个点q) 根据规则r1与2,本文算法不需要节点间同步,消息丢包 q∈x,Vj∈tn:d(q,)≤R,CS,,∈Z (9) 并不妨碍发送者与接收者的白稳定过程。本节的理论分析给 式中:d(q,)为点q=zn与节点j间的距离。相对回题1,节点出了网络生命期优化过程中检测与回复消息的数量⊥限 状态可表示为 定理2本文算法检测/回复所需消息上限为 Vzn∈Z:3i,∈ES(i)=S()=活动→i= (10) 以上的假设使得每个监控区域由最多一个节点覆盖.满足 )1≤i≤n;1≤j≤h (11) min: min: A 实际应用的需求。 其中:n为节点数量;m为通信链路数量;t2为节点i的可靠生 2.2.2分布式自稳定算法 命期;△;为节点第j次睡眠期时间 假设读/写均为原子操作,调度器为分布式/异步调度。假 证明节点讠可靠生命期为t。当1≤i≤n时,对于可靠 设传感节点的标志符是唯一的。定义了以下三个符号 性R为 A():活动邻居节点,∈(i),S()=活动 R=1-F()=nh6=K )/→ A(i):l小的活动的邻居节点∈a(i),S(j)=活动 ∧ld(i)>ld(j) )→(ln)p W(i):ld小的唤酲邻居节点彐j∈。(i),S(j)=唤醒 ∧l(i)>l(j) 式(12)是在可靠性为R;的情况下.节点的生命期。而节点 本文提出的自稳定算法利用如下两条规则实现 睡眠时间可细分为 0<bo<l1<t2<…<l= (13 r1:if(S(i)=唤酲∧A(i))∨(S(i)=活动∧A"(i)) henS(i)←睡眠 式中:4,=[t-1,n](1≤p≤k)表示第P次睡眠的时间。根据 r2:ifS(i)=唤陛∧-A(i)∧W(i) 引理1,节点的唤醒速度随时间单调增加,那么,睡眠时间随时 活动 间单调减少,由此可得节点i的检测过程消耗上限为 2.2.3分布式自稳定算法证明 ),1≤≤n,1≤j≤k。另外,每个节点i在检测过程会 min 4 系统达到自稳定所需的三个必要条件是 发送消息给相邻节点,并且从相邻节点收到回复消息,此开销 a)当系统达到合法状态时,任何节点都不能执行任何规则;最多O(1N)。因此,节点i的检测与回复消息数量最多为 b)当系统处于不合法状态时,至少有一个节点能执行规则 c)无论系统的初始化状态如何,系统可在有限步骤内达O( N,Ix.)。最终,对于整个无线传感器网络的n个传 到合法状态。 感节点,算法的总消息消耗为 引理2每个监控区域x最多由个传感节点覆盖。 证明如果一个区域有两个以上活动节点,根据规则,O(EMx一些 axi )≤O(nm 830 计算机应用研究 第33卷 max-t 定理3上限O(mm )是可达到的 min: ml in: 4i 4仿真结果与分析 证明假设仅有两个传感节点1与s2(即n=2)的线性链 木文利用Ⅵ ATLAB进行仿真实验,将木文算法与分布式 路需要协调两个节点间的通信。设B=1,1处于工作状态、52多目标概率覆盖协议(PCP)“进行对比实验。PCP每Rs算 处于活动状态。如果t1=t2(51与2同时启动与故障)。那 做一轮,R为远小于传感器平均生命期的一个值。每轮的开 么发送的检测消息总量为x其中△2为2恒定的匠眠时间。始,所有节点开始独立运行PCP,然后节点间交换大量的消息 由于S1与拥有相同的生命期,节点1会回复的每条检测来的定睡眠特点与活动节点。PCP将角网格顶点间的距离 消息,所以在s1与s2故障前所有的检测与回复的消息总量为 作为工作节点间的最大距离,使用s表示。S的值传感节点 4 2 的感应范圄r,计算得到。圆盘感知模型屮,最大距离设置为 nax nm x min: 4 (15)3,。对于指数感应模型,为确保最小覆盖的感应概率为覆盖 推论2如果B=1,本文算法检测与回复所需的消息总量阙值参数,计算了最大距离为:3(-如(1=31-0) 最多为:O(m×max,),l≤i≤n 其中α表小感应能力随距离衰退的囚素,显然如果设置a= 证明因为节点的睡眠时间Δ是常量,所以可得此推论。∞,那么指数感应模型降为回盘感应模型。 综上可知,本文算法的消息复杂度为 假设监控区域为10×10的正方形区域,并均分成100个 max 方形网格。传感器数量为200~160,并且传感器均匀分布于 min. min 411≤i≤n;≤/≤h (16) 监控区域,各区域的传感器密度在2-16,网络链路可靠、不丟 3.2可靠性分析 包。分别设置参数β为1.05、1.2和1.5。a设为一个节点的 无线传感器网络的可靠性反怏了其容忍故障的能力,是传 平均寿命,假设为10个时间单位。 感网性能的卞导参数。将传感节点分为无数互斥的传感节点 仿真分别从四个角度比较了本文算法与PCP的性能:a) 集合,其屮毎个集合的成员一起覆盖同一个监控区域。所有集网络生命期;b)有效的监控时间,监控区域的活动节点出故障 合的活动间隔时问是相同的,同时有且只有一个集合处在活动并被替换所耗时间,以(%)表示:c)消息总数;d)每个非活动 状态并提供网络服务,而其余集合都处于睡眠状态。需要协调节点唤醒的次数。 传感网可靠性与所需覆盖集合数量的阈值,即确定对丁一定的 第组实验:在节点数量为(200~1600)的情况下,比较 可靠性阈值,需要使用的最小覆盖集合数量。 本文算法与PCP的生命期时间。如图1所示,在因子B分别为 定理4∫、为某个竹点sFS的故障概峯,为达到传感网规 1.05、1.2和1.5下,本文算法的生命周期均优于 第二组实验:在节点数量为(200~1600)的情况下,对本 定的可靠性阈值RN,最小的覆盖集合数量为 文算法与PCP的覆盖率进行了比较。如图2所小,在因子B分 log(. min I; (1-f)) 17)别为1.05、1.2和1.5的情况下,PCP的覆盖率均优于本文算 法,原因在于其活动节点组成的三角形格∫保证了高覆盖率 式中:为互斥覆盖集合C的最大值。 然而本文算法在高密度情况下(800~160),与P(P仅有5% 证明一个覆盖集包含覆盖整个监控区域所需的节点,因 的差距 此一个给定的覆盖集C;的总体可靠性等于其全部节点成功运 180 行的概率 140日b=12 R=C1(1- (18) 120*b=1.5 100|·PP 相似地,当且仅当每个覆盖集合没有故障时,算法的覆盖 马b-1.2 才是成功的。显然,互斥覆盖集合?的最大数量由覆盖监控 004006008001000120014001600 2004005008001000120014001600 区域的最小集合的大小定义为η=min|n1,由此可得传感网 节点数量 节点数量 图1网络的生命周期 图2覆盖率 的可靠性就是算法成功覆盖全局的慨率,表示为 第三组实验:在节点数量为(200~160)的情况下,比较 Rs=∏∏R=∏∏(1-/)1≤n;1s≤C2(19) 了本文算法与P(P的总消耗消息数量。如图3所示,在因子B 覆盖集合的数量计算依赖如下条件 分别为1.05、1.2和1.5下,PCP的消耗消息数量多于本文算 Ry≥R (20)法,尤其在高密度情况下。 可得 RsN=lll(l-f)>l min I(l-f) (21) 第四组实验:在节点数量为(200~1600)的情况下,比较了 从式(21)可得 木文算法与PCP的节点唤醒次数。如图4所小,在囚子B分别 Rs≤∏min∏(1-f)=(mn∏(1-/)→ 为1.05、1.2和1.5下,本文算法的节点唤醒次数明显大于PCP R)≤nxlg(1mnm(1-) 综上可知,相比文献[14]提出的分布式多目标概率覆盖 可得 log(rSN) 协议,本文算法在覆盖率、网络寿命延长、节点唤醒次数等方面 (min (23)均取得了更好的性能,主要因为PCP没有考虑到随着运行时 最终,可得覆盖集合的最小数7即为本文算法的可靠性:间增加传感器的可靠性下降及故障率升高的影响。本文算法 g(rsn) 采用分布式调度,无须知道传感节点的位置信息,使用多个节 =og(mim;/“71:(1-f) 1≤j≤|C, 点同时工作,从而节省时间,提高了效率。通过较低的网络通 第3期 明勇,等:WSN中考虑节点磨损的分布式自稳定网络寿命优化算法 831 信代价,及时使用空闲节点替代故障节点,保持网终的连通性,[5] lyengar sS, Brooker r. Distributed sensor networks:enso or networ 故提升了WSN各方面的性能。 king and applieations[ W]- 2nd e. [S1.]: CRC Press, 2012 L6」于海斌,梁炜,曾鹏.智能无线怙感器网络系统_M」.北京:科学出 -b=l05 e-b=10 版社,2013 /0=12 「7将杨江,石为人,唐贤伦,等,能量均衡的无线传惑嚣网络非均匀 米b=1.5 -PCP 分簇路由协议[J,软件学报,2012,23(5):1222-1232 [8 Yang Y, Fonoage M I, Cardei M. Improving network lifetime with mo- le wireless sensor networks[ J]. Computer Communications 2010,33(4):409-419 40060080C1C001200140016002004006008001000120014001600 节点数量 节点数量 L9 Dimokas N, Katsaros D, 'Tassiulas L, el al. High performance, low com- 图3消息总数量 图4每节点唤醒次数 lexity cooperative caching for wireless sensor networks[J. Wireless Networks,2011,17(3):717-737 5结束语 [10 Anisi M H, Abdullah A H, Razak S A Energy-efficient data collection in wire less sensor networks[ J. Wireless Sensar Network, 2011, 28 考虑在实际应用中,节点无法预估出现的故障,木文针对 (3):329-337. T Il Caione C, Brunelli D, Benini L. Distributed compressive sampling for 节点的磨损与故障提出了网络生命周期的自优化方案。木文 lifetime optimization in dense wireless sensor networks]. IEEE 算法通过以最小的代价及时替换故障节点,从而维持网络的正 Trans on Industrial Informatics, 2012, 8(1): 30-40 常运行,延长大线传感器网络的生命周期。而且为了证明本文 12] Ben-Othmanl J, Bessaoud K, Bui A, et al. Self-stabilizing algorithm for 提出算法的有效性,进行了理论分析和仿真实验。仿真结果表 efficient topology control in wireless sensor networks_J]. Journal of Computational Science, 2013, 4(4): 199-208 明,当传感节点的可靠性随着使用时间与奢损下降时,本文算[13]Ben, Othman j, Bessaoud K,BuiA,etal. Self-stabilizing algorithm for 法可延长无线传感网的生命期,且性能优于PCP。 energy saving in wireless sensor networks[ C_//Proc of IEEE Sympe 未来会将本文算法应用于其他网络环境,并考虑与其他新 sium on Computers and Communications. 2011: 68-73 颖技术相结合,通过大量实验,进一步改善WsN的性能。 [14 Ba M, Flaurac 0, Makhloufi R, et al. Evaluat ion study of self-slabili zing cluster-head election criteria in WS\s[C//Proc of the 6th In 参考文献 ternational Conference on Communication Theory, Reliability, and I 1 Maraiya K, Kant K, Gupta N. Wireless sensor network: a review on da Quality of Service. 2013: 64-69 ta aggregation[ J]. International Journal of Scientific Enginee- [15 Tian Y, Ou Y, Hamid R K, et al. Distributed multitarget probabilistie ring Research, 2011, 2(4): 1-6 coverage cont rol algorithm for wireless sensor networks[J]. Mathe [2]朱洪波,杨尨祥,未琦,物联网技术进展与应用[冂].闫京邮电大 atical Problems in Engineering, 2014, 2014(3): 193-200 学学报:自然科学版,2011,31(1):1-9 [16 Hancke G P, Gungor V C. Guest editorial special section on industrial [3]邓瀚林,李磊,黄河清,等.无线传感网簇头轮换能耗分析与改进 wireless sensor networks[ J|. IEEE Trans on Industrial Informa- 策略[J.上海交逍大学学报、2011,45(3):317-320 tcs,2014,10(1):762-765. L4 Gungor V C, Lu B, llancke G P Opportunities and challenges of wire- [17 Zhu Chuan, Zheng Chunlin, Shu Lei, et al. A survey on coverage and less sensor networks in smart grid I J|. IEEE Trans on Industrial t' onnectivity issues in wireless sensor networks[J. Journal of Net- Electronics,2010,57(10):3557-3564 work and Computer Applications, 2012, 35(2): 619-632 (上接笫812页)IEE802.1Ibg协议采取的直接序列扩频等技以及ROMA算法,在网络通信繁忙程度为某一区间时,明显仇 术,其內在保护机制与可检测错误并重发数据包的协汊能够在于SICA算法,其他时刻则与SCA算法基木持平 定程度上保证数据包的传输成功率,但同时也会提高传输延参考文献 迟,降低传输效率。图4表明,随着非关节点的CBR流数量[1] Akyildiz I F, Wang Xudong, A survey on wireless mesh networks[J. 的增加, CLICA与HOMA算法的传输延迟明显高于SCA及 IEEE Communications Magazine, 2005, 43(9): S23-S30 TAOA算法,相较SCA算法, TAIOCA的点数据传输平均[2] Raychaudhuri I,criM, Emerging wireless technologies and the future mobile inlernet [M_. Cambridge Cambridge L niversity Press, 2011 延迟随着 CBR flows条数的增加弧度更加平滑,而在CBR流条「31 Crichigno J,WuMY,Shuw. Protocols and architectures for channel 数在10~20条时,SlCA算法的平均延迟相较 TAIOCA有一个 assignment in wireless mesh networks[ J. Ad hoc Networks, 2008, 6 (7):1051-107 蛟大的波动,这是因为 TAIOCA算法在网络比较繁忙同时剩余 [4 si Weisheng, Selvakennedy S, Zomaya A Y. An overview of channel as- 带宽能够提供避让空间的前提下,相较SICA算法可以更好地 signment methods for multi-radio multi-channel wireless mesh networks 利用剩余带宽,降低信道间的十扰。 [J]. Parallel and Distributed Computing, 2010, 70(5): 505-524 [5 Dhananjay A, Zhang Ilui, Li Jinyang, et al. Practical, distributed chan- nel assignment and routing indual-radio mesh networks[ C//Proc of 5结束语 ACM SIGCOMM 2009 Conference on Dala Communication York: ACM Press. 2009. 9-11U 木文针对已有研究工作的不足,在当前无线Mesh网可分[6] Marina m K, Das s r, Subramanian A P. A topology control approach 配正交信道不足的现状下,引入了重叠信道间的扰模型,尝 for utilizing multiple channels in multi-radio wireless mesh networks [J. Computer Networks, 2010, 54(2 ): 241-256 试在考虑不同信道间干扰的前提下,寻求满足整个无线Meh[7] Nezhad M a,Cra- Alabern l. Adaptive channel assignment for wire- 网络节点间干扰最小的信道分配方案。首先根据干扰模型求 less mesh networks using game 出每个节点的每个可诜信道的干扰权值,然后利用累积分布函 International conference on mobile ad hoc and sensor Systems. 2011 数选择最优信道,多轮循环后,整个网终趋近于最优信道分配[8]rgG;nki, Wans BO, Ding yon,etnt. Multicast algorithms fu 方案。模拟实验表明,在整饣网络通信繁忙,节点信道间干扰 multi-channel wireless mesh networks C1//Proc of IEEE Internatio 量大的前提下,该算法在传输成功率上与SICA、CLCA以及 nal Conferenee on NeIwork Protocols. 2007.1-10 [2 Gupta P, Kumar P R 'The capacity of wireless networks[J.IEEE ROMA算法基本相当,而数据传输平均廷迟则明显优于 CLICA Trans on Information Theory, 2000, 46(2): 388-404