2. 四川师范大学 计算机科学学院, 成都 610101
2. College of Computer Science, Sichuan Normal University, Chengdu 610101, China
无线传感器网络中传感器节点最大的能量消耗源于无线通信[1], 然而传感器节点一般使用能量十分有限的电池提供能量, 且通常运行在恶劣甚至危险的偏远环境中, 充电和更换电源的难度很大, 因此如何设计有效方法来提高数据通信过程中网络能量的使用效率, 避免出现能量空洞[2]成为了当前研究的核心问题. 分簇路由[3-7]作为一种平衡网络能量消耗, 降低能量空洞出现可能性的重要技术, 是近年来国内外学者的研究热点. 如: 文献[8]提出了基于非均匀分簇和多跳传输的路由算法Energy Efficient Uneven Clustering (EEUC), 该算法利用簇头竞争半径来调节簇规模, 使靠近基站的簇规模相对较小, 这部分簇头收集簇内数据的能耗就会相对减少, 从而拥有更多的能量来进行路由转发. 这种非均匀成簇路由算法在一定程度上平衡了网络能量消耗, 降低了能量空洞出现可能性. 文献[9]将非均匀分簇思路与LEACH结合提出一种新算法, 该算法从控制簇头分布以及簇规模的角度出发, 根据节点稀疏程度和剩余能量来保证簇头分布均匀, 以此平衡网络能耗、减缓能量空洞的出现. 文献[10]从控制簇头数据传播路径的角度出发, 将簇头间数据转发的思想应用到LEACH算法中, 在簇头之间形成了一条通向基站的优化路径, 从而均衡了网络能量消耗. 文献[11]改进EEUC机制, 引入能量项和距离项, 选举簇首时对门限函数进行改进; 并对规模较大的簇进行节点分组, 由各分组的中心节点执行各自分组内成员节点的数据采集与融合任务, 簇首节点只与各分组中心节点进行通信, 均衡簇内节点能耗. 文献[12]基于EEUC路由协议, 以节点剩余能量、簇内成员数目、可用缓存大小、节点信道质量、节点距离为参数, 计算多条传输路径, 提出基于多路径的非均匀分簇能量优化路由协议.
和以上思路不同, 本文从分流簇头负载、平衡节点能耗的角度出发, 分析了负载分配不均可能导致的能量空洞问题, 并结合上述文献中簇间数据转发思路提出了一种基于负载分流的数据转发策略, 以提高网络能量使用效率, 降低能量空洞出现的可能性.
1 网络能耗模型本文采用和文献[8]一样的简单能量消耗模型, 忽略节点在计算、存储等过程中的能量消耗, 仅计算通信能耗. 在传输
${E_{Tx}}\left( {l,d} \right) = \left\{ {\begin{array}{*{20}{c}} {l{E_{\rm {elec}}} + l{\varepsilon _{fs}}{d^2},d < {d_0}} \\ {l{E_{\rm {elec}}} + l{\varepsilon _{mf}}{d^4},d > {d_0}} \end{array}} \right.$ | (1) |
节点接收数据的能量消耗如式(2)[8]:
${E_{Rx}}\left( l \right) = l{E_{\rm {elec}}}$ | (2) |
其中,
按照簇间数据转发思路, 若簇头
2.2 基于负载分流的簇头间数据转发策略设计 2.2.1 负载分流设计思路
负载分流策略通常用于均衡网络资源消耗, 如文献[13]针对异构无线网络研究了负载分流机制, 提出了一种混合负载均衡算法, 实现了保证系统资源利用率的同时提高网络服务质量; 文献[14]针对内容分发网络中大规模数据请求发生的情况, 研究并设计了服务器间的负载分流策略, 有效保证了网络服务质量. 文献[15]使用密度控制机制改变节点的工作、休眠状态, 使各层网络中的节点能量趋于同时耗尽. 同时, 引入路由负载平衡分流的思想, 让数据发送到下一跳簇头时, 分流到多个簇头以平衡簇头间的负载. 受以上研究的启发, 本文在参考EEUC算法思路基础上, 针对Sink附近的簇头容易出现负载分配不均、能量空洞的问题, 依据如下策略进行负载分流处理:
假设簇头
2.2.2 分流权重设计
为了控制数据在分流簇头(接收分流数据并帮助转发的簇头)间被合理分配, 本小节从分流簇头能耗比角度进行分析, 并结合分流数据发送方能耗设计了负载分配权重
设簇头
$\begin{array}{l} ({E_{Rx}}\left( {{l_{ij}}} \right) + {E_{Tx}}\left( {{l_j} + {l_{ij}},d} \right))/{E_j} = \\ \left\{ {\begin{array}{*{20}{c}} {\dfrac{{{l_{ij}}{E_{\rm {elec}}} + ({l_{ij}} + {l_j}){E_{\rm {elec}}} + ({l_{ij}} + {l_j}){\varepsilon _{fs}}{d_j}^2}}{{{E_j}}},{d_j} < {d_0}} \\ {\dfrac{{{l_{ij}}{E_{\rm {elec}}} + ({l_{ij}} + {l_j}){E_{\rm {elec}}} + ({l_{ij}} + {l_j}){\varepsilon _{fs}}{d_j}^4}}{{{E_j}}},{d_j} > {d_0}} \end{array}} \right. \\ \end{array} $ | (3) |
为了控制分流数据对
(1) 式(3)中
(2)
(3)
另外, 在设计分流权重时还应考虑分流操作中数据发送方
基于以上分析, 本文设计了负载分配权重
${\lambda _{ij}} = 1 - \dfrac{{{l_j} + {d_{ij}} + {d_j} + {E_j}^{ - 1}}}{{\displaystyle\sum\limits_{j = 1}^n {} ({l_j} + {d_{ij}} + {d_j} + {E_j}^{ - 1})}}$ | (4) |
结合前文提出的负载分流思路, 参考文献[8]中的簇构造和簇头选举机制, 以下基于簇间数据转发思想, 提出了对应的簇头间数据转发流程, 其中本文提出的负载分流策略主要体现在Step 4–Step 8.
Step 1. 簇内节点以单跳方式将数据发送到簇头, 由簇头负责转发.
Step 2. 每个簇头广播一条包含其位置信息的NODE_STATE_MSG消息, 其广播范围参考文献[8].
Step 3. 针对每个簇头, 若当前簇头
Step 4. 针对不能直接发送数据到Sink的簇头
Step 5. 统计集合
Step 6.
Step 7. 将
Step 8.
实验采用Matlab编写模拟程序对本文提出的基于负载分流的簇间数据转发算法进行验证, 实验把本文策略(因本文的负载分流数据转发算法中结合了EEUC算法的簇构造和簇间数据转发机制, 故以下将本文算法记为IEEUC)与EEUC算法、LEACH算法从如下3个方面进行比较, 以评估本文改进方案性能.
① 比较3种算法对应的首节点死亡时间和网络失效时间, 并结合T检验结果评估算法在节点生存周期上的表现.
② 比较3种算法能量剩余情况, 评估算法在节点能量使用效率上的表现.
③ 比较3种算法在节点密度(即节点个数)不同时对应的网络失效时间和首节点死亡时间, 评估算法在参数值—“节点个数”变化时的效果.
实验中采用理想MAC 协议, 忽略无线链路中可能发生的丢包错误, 同时设传感器节点位于200 m×200 m的正方形网络区域内, Sink位于原点处, 即坐标(0, 0)位置, 其余网络参数如表1. 另外, 文中未提及的IEEUC、EEUC和LEACH算法相关参数均参考文献[7, 8].
3.1 节点生存周期对比及T检验分析
实验通过比较3种算法的网络节点生存时间来验证本文改进方案的有效性, 对比结果如图3. 指定网络节点死亡10%以上表示网络失效, 从图3可以看出: IEEUC的第一个节点死亡时间比另外两种算法晚100轮左右、网络失效时间也晚100轮以上.
另外, 为了进一步比较3种算法的节点生存时间, 实验运用统计学中成对比较实验法, 对EEUC、LEACH和IEEUC的10次运行结果进行T检验. 如表2~表5. 具体地, 表2和表3中的数值越大, 说明第一个节点死亡时间和网络失效时间越长. 因此, 取表2、表3中IEEUC—EEUC和IEEUC—LEACH的结果作为成对数据差
为了对比3种算法的网络剩余能量和节点平均剩余能量随时间的变化情况, 实验随机进行10次, 取平均结果如图4、图5, 从图中可以看出: 大约从300轮开始, IEEUC算法的能量消耗速度高于EEUC, 说明本文提出的机制利用了Sink附近更多的簇头节点帮助转发数据, 在一定程度上造成了能耗增长. 但是, 文中2.2.1分析了本文负载分流方案是为均衡Sink附近簇头的能耗, 避免相应位置产生能量空洞, 延缓网络的整体失效时间. 结合没有免费午餐定理(No Free Lunch, NFL)来看, 本文方案带来的能耗增加是可接受的.
3.3 节点密度变化时算法效果对比
在算法涉及的网络参数中, 节点个数N直接关系到网络区域内节点密度, 以下在节点个数变化时, 分别选择10次实验平均结果对比3种算法对应的首节点死亡时间(如图6)和网络失效时间(如图7).
从图6、图7中可以看出: 随节点个数的增加, 3种算法的首节点死亡轮数和网络失效轮数都有降低趋势, 但是IEEUC算法对应的首节点轮数大于其余两种算法40%以上, 网络失效轮数晚60%以上. 由此说明, IEEUC算法在节点密度变化时对应的网络生存时间仍优于EEUC和LEACH.
通过以上3个方面实验结果说明: 本文基于负载分流的簇间数据转发算法IEEUC与采用直接转发机制的EEUC和LEACH算法相比, 负载分流会将本该发给一个簇头的负载分流给n个簇头, 这必然会增加分流簇头的能耗. 但是, 分流方案均衡了Sink附近簇头的负载, 能降低能量空洞出现的可能性, 从而延长了网络生存时间(在网络失效时间和首节点死亡时间上IEEUC优于EEUC和LEACH).
4 结束语本文针对无线传感器网络中, 簇间数据转发容易导致靠近Sink的节点提前失效造成能量空洞的问题, 提出了一种负载分流策略, 并结合了EEUC算法的簇构造和簇头选举机制设计了基于负载分流的簇间数据转发算法. 仿真实验结果表明: 本文提出的方案通过分流簇头负载, 能延长网络寿命, 提高了网络能量使用效率, 具有良好的性能.
[1] |
Pantazis NA, Nikolidakis SA, Vergados DD. Energy- efficient routing protocols in wireless sensor networks: A survey. IEEE Communications Surveys & Tutorials, 2013, 15(2): 551-591. |
[2] |
Semente RS, Oliveira FDM, Lock AS, et al. Energy- efficient WSN systems. In: Mason A, Mukhopadhyay SC, Jayasundera KP, eds. Sensing Technology: Current Status and Future Trends III. Cham: Springer. 2015. 111–132.
|
[3] |
Narendra K, Varun V, Raghunandan GH. A comparative analysis of energy-efficient routing protocols in wireless sensor networks. In: Sridhar V, Sheshadri HS, Padma MC, eds. Emerging Research in Electronics, Computer Science and Technology: Proceedings of International Conference, ICERECT 2012. New Delhi, India. 2014. 399–405.
|
[4] |
Zhu XD, Li J, Xia YF, et al. An efficient distributed node clustering protocol for high dimensional large-scale wireless sensor networks. Proceedings of the 8th International Conference on Ubiquitous Information Management and Communication. Siem Reap, Cambodia. 2014. 4.
|
[5] |
Xu XN, Xiao MB, Yan W. Clustering routing algorithm for heterogeneous WSN with energy harvesting. Applied Mechanics and Materials, 2015, 733: 734-739. DOI:10.4028/www.scientific.net/AMM.733.734 |
[6] |
刘唐, 孙彦清. 基于负载均衡和最短路径的异构无线传感器网络成簇算法. 计算机科学, 2014, 41(10): 169-172, 209. DOI:10.11896/j.issn.1002-137X.2014.10.038 |
[7] |
Heinzelman WB, Chandrakasan AP, Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks. IEEE Transactions on Wireless Communications, 2002, 1(4): 660-670. DOI:10.1109/TWC.2002.804190 |
[8] |
李成法, 陈贵海, 叶懋, 等. 一种基于非均匀分簇的无线传感器网络路由协议. 计算机学报, 2007, 30(1): 27-36. DOI:10.3321/j.issn:0254-4164.2007.01.004 |
[9] |
卢先领, 王莹莹, 王洪斌, 等. 无线传感器网络能量均衡的非均匀分簇算法. 计算机科学, 2013, 40(5): 78-81. DOI:10.3969/j.issn.1002-137X.2013.05.020 |
[10] |
陈炳才, 么华卓, 杨明川, 等. 一种基于LEACH协议改进的簇间多跳路由协议. 传感技术学报, 2014, 27(3): 373-377. DOI:10.3969/j.issn.1004-1699.2014.03.019 |
[11] |
黄金国, 刘涛, 周先春, 等. 结合节点分组和门限优化的改进EEUC机制. 计算机工程与设计, 2018, 39(8): 2432-2437. |
[12] |
徐万一, 王军, 张亚君, 等. 基于多路径的非均匀分簇路由协议. 沈阳化工大学学报, 2019, 33(2): 171-177. DOI:10.3969/j.issn.2095-2198.2019.02.015 |
[13] |
盛洁, 唐良瑞, 郝建红. 异构无线网络中基于业务转移和接入控制的混合负载均衡. 电子学报, 2013, 41(2): 321-328. DOI:10.3969/j.issn.0372-2112.2013.02.018 |
[14] |
Gupta P, Goyal MK, Gupta N. Reliability aware load balancing algorithm for content delivery network. In: Satapathy SC, Govardhan A, Raju KS, et al., eds. Emerging ICT for Bridging the Future-Proceedings of the 49th Annual Convention of the Computer Society of India (CSI) Volume 1. Cham: Springer. 2015. 427–434.
|
[15] |
刘唐, 彭舰, 陈果, 等. 基于密度控制的传感器网络能量空洞避免策略. 计算机学报, 2016, 39(5): 993-1006. DOI:10.11897/SP.J.1016.2016.00993 |