计算机系统应用  2020, Vol. 29 Issue (7): 160-165   PDF    
结合负载分流的无线传感器网络簇间数据转发算法
梁静1, 葛宇2     
1. 成都工业学院 计算机工程学院, 成都 611730;
2. 四川师范大学 计算机科学学院, 成都 610101
摘要:针对无线传感器网络能量消耗不均, 出现能量空洞的问题, 提出了一种基于负载分流的簇间数据转发算法. 首先分析簇间数据转发可能导致Sink附近能量空洞的问题. 然后, 基于簇头当前的能量状态、数据量和距离信息等因素提出了负载分配权重. 根据该权重设计了对应的负载分流策略, 并用于簇间数据转发算法中. 仿真实验结果显示: 相比基本EEUC算法和经典LEACH算法, 本文提出的负载分流数据转发算法延长了网络存活时间, 提高了网络能量使用效率.
关键词: 无线传感器网络    负载分流    能量空洞    负载分配权重    
Data Forwarding Algorithm Between Clusters in Wireless Sensor Networks Based on Load Diversion
LIANG Jing1, GE Yu2     
1. School of Computer Engineering, Chengdu Technological University, Chengdu 611730, China;
2. College of Computer Science, Sichuan Normal University, Chengdu 610101, China
Foundation item: Fund of Education Bureau, Sichuan Province (16ZB0060)
Abstract: In order to avoid the uneven energy consumption and energy hole in wireless sensor networks, this study proposes a data forwarding algorithm between clusters based on load division. Firstly, this study analyzes the problem that data forwarding between clusters may lead to energy hole near the sink. Then, the load allocation weight of cluster head is designed to represent the cluster head’s current energy state, data amount and distance. According to the load allocation weight, this study designs a new data forwarding algorithm, which forwards the data to cluster head near the sink. The simulation results show that compared with the basic EEUC algorithm and the classical LEACH algorithm, the proposed data forwarding algorithm has no great increase of energy consumption, prolongs the network survival time, and improves the efficiency of network energy utilization.
Key words: Wireless Sensor Network (WSN)     load diversion     energy hole     load allocation weight    

无线传感器网络中传感器节点最大的能量消耗源于无线通信[1], 然而传感器节点一般使用能量十分有限的电池提供能量, 且通常运行在恶劣甚至危险的偏远环境中, 充电和更换电源的难度很大, 因此如何设计有效方法来提高数据通信过程中网络能量的使用效率, 避免出现能量空洞[2]成为了当前研究的核心问题. 分簇路由[3-7]作为一种平衡网络能量消耗, 降低能量空洞出现可能性的重要技术, 是近年来国内外学者的研究热点. 如: 文献[8]提出了基于非均匀分簇和多跳传输的路由算法Energy Efficient Uneven Clustering (EEUC), 该算法利用簇头竞争半径来调节簇规模, 使靠近基站的簇规模相对较小, 这部分簇头收集簇内数据的能耗就会相对减少, 从而拥有更多的能量来进行路由转发. 这种非均匀成簇路由算法在一定程度上平衡了网络能量消耗, 降低了能量空洞出现可能性. 文献[9]将非均匀分簇思路与LEACH结合提出一种新算法, 该算法从控制簇头分布以及簇规模的角度出发, 根据节点稀疏程度和剩余能量来保证簇头分布均匀, 以此平衡网络能耗、减缓能量空洞的出现. 文献[10]从控制簇头数据传播路径的角度出发, 将簇头间数据转发的思想应用到LEACH算法中, 在簇头之间形成了一条通向基站的优化路径, 从而均衡了网络能量消耗. 文献[11]改进EEUC机制, 引入能量项和距离项, 选举簇首时对门限函数进行改进; 并对规模较大的簇进行节点分组, 由各分组的中心节点执行各自分组内成员节点的数据采集与融合任务, 簇首节点只与各分组中心节点进行通信, 均衡簇内节点能耗. 文献[12]基于EEUC路由协议, 以节点剩余能量、簇内成员数目、可用缓存大小、节点信道质量、节点距离为参数, 计算多条传输路径, 提出基于多路径的非均匀分簇能量优化路由协议.

和以上思路不同, 本文从分流簇头负载、平衡节点能耗的角度出发, 分析了负载分配不均可能导致的能量空洞问题, 并结合上述文献中簇间数据转发思路提出了一种基于负载分流的数据转发策略, 以提高网络能量使用效率, 降低能量空洞出现的可能性.

1 网络能耗模型

本文采用和文献[8]一样的简单能量消耗模型, 忽略节点在计算、存储等过程中的能量消耗, 仅计算通信能耗. 在传输 $l$ bit数据经过距离 $d$ 的过程中, 节点发送数据的能量消耗如式(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)

其中, ${d_0}$ 为一阈值, 本文定义为 $\sqrt {{\varepsilon _{fs}}/{\varepsilon _{mf}}} $ ; ${E_{\rm {elec}}}$ 是发送、接收电路处理每比特数据的能量消耗; ${\varepsilon _{fs}}{d^2}$ ${\varepsilon _{mp}}{d^4}$ 是发送每比特数据放大器的能量消耗.

2 基于负载分流的数据转发算法 2.1 簇间数据转发中能量空洞问题分析

按照簇间数据转发思路, 若簇头 ${S_i}$ 通过转发方式传输数据到基站(Sink), 则 ${S_i}$ 要从候选中继中选出一个合适的簇头 ${S_j}$ 帮助其转发数据. 由于所有数据均汇聚到Sink, 导致越靠近Sink的节点所担任的转发任务越重, 过早失效形成能量空洞的可能性越高. 例如图1中, 网络区域内的点表示簇头, 中心点为基站Sink, 所有簇头的数据都将通过 ${S_1}$ ${S_2}$ ${S_3}$ ${S_4}$ 分别汇聚到Sink. 以阴影区域内的簇头为例, ${S_3}$ 需要帮助 ${S_{3{\rm{1}}}}$ ${S_{3{\rm{11}}}}$ ${S_{3{\rm{111}}}}$ ${S_{3{\rm{12}}}}$ ${S_{3{\rm{2}}}}$ ${S_{3{\rm{21}}}}$ 转发数据, 而 ${S_{3{\rm{1}}}}$ 只用帮助 ${S_{3{\rm{11}}}}$ ${S_{3{\rm{111}}}}$ ${S_{3{\rm{12}}}}$ 转发数据, ${S_{3{\rm{2}}}}$ 只用帮助 ${S_{3{\rm{21}}}}$ 转发数据, 相比而言靠近Sink的簇头 ${S_3}$ 承担的转发任务量高于上述簇头. 另外, 对于靠近Sink的簇头 ${S_1}$ ${S_2}$ ${S_3}$ ${S_4}$ 而言, ${S_3}$ 承担的数据转发任务最多, 必然导致其先于 ${S_1}$ ${S_2}$ ${S_4}$ 能量耗尽而失效, 从而使阴影区域中节点的簇头数据将不能再由 ${S_3}$ 汇聚到Sink, 形成能量空洞.

图 1 网络数据转发

2.2 基于负载分流的簇头间数据转发策略设计 2.2.1 负载分流设计思路

负载分流策略通常用于均衡网络资源消耗, 如文献[13]针对异构无线网络研究了负载分流机制, 提出了一种混合负载均衡算法, 实现了保证系统资源利用率的同时提高网络服务质量; 文献[14]针对内容分发网络中大规模数据请求发生的情况, 研究并设计了服务器间的负载分流策略, 有效保证了网络服务质量. 文献[15]使用密度控制机制改变节点的工作、休眠状态, 使各层网络中的节点能量趋于同时耗尽. 同时, 引入路由负载平衡分流的思想, 让数据发送到下一跳簇头时, 分流到多个簇头以平衡簇头间的负载. 受以上研究的启发, 本文在参考EEUC算法思路基础上, 针对Sink附近的簇头容易出现负载分配不均、能量空洞的问题, 依据如下策略进行负载分流处理:

假设簇头 ${S_i}$ 不能直接与Sink通信, 其数据需要中继簇头帮助转发, 且候选中继簇头中能一跳转发数据到Sink的簇头个数大于1, 此时 ${S_i}$ 把数据按权重进行分配, 发送给能一跳转发数据到Sink的中继簇头(如图2, Sink表示基站, 虚线圆表示簇头的通信半径, 簇头 ${S_1}$ 的候选中继有 ${S_2}$ ${S_3}$ ${S_4}$ . ${S_2}$ ${S_3}$ 均能够一跳转发数据到Sink, ${S_1}$ 把数据根据权重转发给 ${S_2}$ ${S_3}$ , 在Sink附近的簇头之间实现负载均衡. ${S_4}$ 尽管也属于 ${S_1}$ 的候选中继, 但由于 ${S_4}$ 不能一跳转发到Sink, 故 ${S_4}$ 不参与分流和转发工作). 特别说明的是, 如果 ${S_i}$ 的中继簇头中能一跳转发数据到Sink的簇头个数小于等于1, 则 ${S_i}$ 不做分流处理, 将数据直接发送到距离Sink最近的中继簇头.

图 2 负载分流思路

2.2.2 分流权重设计

为了控制数据在分流簇头(接收分流数据并帮助转发的簇头)间被合理分配, 本小节从分流簇头能耗比角度进行分析, 并结合分流数据发送方能耗设计了负载分配权重 $\lambda $ .

设簇头 ${S_i}$ 要将数据分流到对应的n个簇头中, 其中一个分流簇头 ${S_j}$ 的当前能量为 ${E_j}$ , 自身已有的数据为 ${l_j}$ , 从 ${S_i}$ 分流到 ${S_j}$ 的数据为 ${l_{ij}}$ , ${S_j}$ 将数据发往Sink的距离是 ${d_j}$ . 结合式(1)、式(2), ${S_j}$ 接收分流数据和发送所有数据消耗的能量与其剩余能量之比如式(3). 其中, 分子部分为接收分流数据 ${l_{ij}}$ 的能耗和发送所有数据(包括自身已有数据 ${l_j}$ 和分流数据 ${l_{ij}}$ )的能耗之和.

$\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)

为了控制分流数据对 ${S_j}$ 能量的影响, 以下对式(3)中各调节项的取值趋势进行分析.

(1) 式(3)中 ${l_j}$ 是分流簇头 ${S_j}$ 自身待发送的数据, 其值越大必然会消耗 ${S_j}$ 越多的能量, 此时若为 ${S_j}$ 分配大量 ${l_{ij}}$ , 必然导致式(3)比值更大. 因此, 在 ${l_j}$ 值较大时应减小 ${l_{ij}}$ , 以防止簇头 ${S_j}$ 的能耗比例过大而提前死亡; 反之则可对 ${S_j}$ 适当增加 ${l_{ij}}$ .

(2) ${d_j}$ 是分流簇头 ${S_j}$ 中数据的发送距离, 其值越大对应能耗越高. 式(3)中 ${d_j}$ 值用 ${S_j}$ 与Sink距离 $d ({S_j},{\rm{Sin}} {\rm{k}})$ 表示, 当 ${d_j}$ 较大时, 应减少分配给 ${S_j}$ 的数据 ${l_{ij}}$ ; 相反则可增加 ${l_{ij}}$ , 这样可以让式(3)的比值得到有效控制.

(3) ${E_j}$ 是分流簇头 ${S_j}$ 的当前能量. ${E_j}$ 越大的分流簇头, 越有能力承担更多的分流任务. 因此, 当 ${E_j}$ 值较高时, 可增加分配给 ${S_j}$ 的数据 ${l_{ij}}$ , 相反则应减少 ${l_{ij}}$ .

另外, 在设计分流权重时还应考虑分流操作中数据发送方 ${S_i}$ 的能耗. 令 ${d_{ij}}$ 表示 ${S_i}$ 与分流簇头 ${S_j}$ 间的距离. 由式(1)可知传输距离和数据量均与能耗成正比, 说明: ${S_i}$ 向较远的分流簇头分配较多的数据, 会加重其能耗. 因此, 当 ${d_{ij}}$ 较大时 ${S_i}$ 应分配较少数据给 ${S_j}$ , 相反则可多分配数据给 ${S_j}$ .

基于以上分析, 本文设计了负载分配权重 $\lambda $ 如式(4), ${\lambda _{ij}}$ 表示 ${S_i}$ 向分流簇头 ${S_j}$ 分配数据的比例.

${\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)
2.3 簇头间数据转发流程

结合前文提出的负载分流思路, 参考文献[8]中的簇构造和簇头选举机制, 以下基于簇间数据转发思想, 提出了对应的簇头间数据转发流程, 其中本文提出的负载分流策略主要体现在Step 4–Step 8.

Step 1. 簇内节点以单跳方式将数据发送到簇头, 由簇头负责转发.

Step 2. 每个簇头广播一条包含其位置信息的NODE_STATE_MSG消息, 其广播范围参考文献[8].

Step 3. 针对每个簇头, 若当前簇头 ${S_i}$ 到Sink的距离在其通信范围内, 则直接将数据发送到Sink, 完成数据传输; 否则执行Step 4.

Step 4. 针对不能直接发送数据到Sink的簇头 ${S_i}$ , 根据其收到的NODE_STATE_MSG消息解析与Sink的距离, 比自身小的邻居簇头记入集合 ${R_{si}}$ .

Step 5. 统计集合 ${R_{si}}$ 中能在一跳内将数据发送到Sink的簇头记入集合 $R{1_{si}}$ . 若| $R{1_{si}}$ | <1, ${S_i}$ 选择 ${R_{si}} - R{1_{si}}$ 中离Sink最近的一个节点作为中继簇头, 不进行分流处理, 转发完数据后退出流程; 若| $R{1_{si}}$ | =1, ${S_i}$ 将所有数据发送给 $R{1_{si}}$ 集合中唯一节点, 也不分流; 否则, 把 $R{1_{si}}$ 中的簇头作为 ${S_i}$ 的分流簇头, 执行以下Step 6分流操作.

Step 6. ${S_i}$ $R{1_{si}}$ 中节点广播请求消息REQUEST, $R{1_{si}}$ 中的簇头将自身的剩余能量和待发送数据量用ACK消息返回给 ${S_i}$ , 同时 ${S_i}$ 记录下自身到各分流簇头的距离以及各分流簇头的相关属性(如: 剩余能量、待发送数据量和到Sink的距离).

Step 7. 将 ${S_i}$ 中数据按式(4)比例进行分配, 并发送给集合 $R{1_{si}}$ 中各分流簇头.

Step 8. $R{1_{si}}$ 中各分流簇头在接收到分流数据后, 将分流数据和自身数据一起发送到Sink, 结束流程.

3 仿真实验

实验采用Matlab编写模拟程序对本文提出的基于负载分流的簇间数据转发算法进行验证, 实验把本文策略(因本文的负载分流数据转发算法中结合了EEUC算法的簇构造和簇间数据转发机制, 故以下将本文算法记为IEEUC)与EEUC算法、LEACH算法从如下3个方面进行比较, 以评估本文改进方案性能.

① 比较3种算法对应的首节点死亡时间和网络失效时间, 并结合T检验结果评估算法在节点生存周期上的表现.

② 比较3种算法能量剩余情况, 评估算法在节点能量使用效率上的表现.

③ 比较3种算法在节点密度(即节点个数)不同时对应的网络失效时间和首节点死亡时间, 评估算法在参数值—“节点个数”变化时的效果.

实验中采用理想MAC 协议, 忽略无线链路中可能发生的丢包错误, 同时设传感器节点位于200 m×200 m的正方形网络区域内, Sink位于原点处, 即坐标(0, 0)位置, 其余网络参数如表1. 另外, 文中未提及的IEEUC、EEUC和LEACH算法相关参数均参考文献[7, 8].

表 1 网络参数

3.1 节点生存周期对比及T检验分析

实验通过比较3种算法的网络节点生存时间来验证本文改进方案的有效性, 对比结果如图3. 指定网络节点死亡10%以上表示网络失效, 从图3可以看出: IEEUC的第一个节点死亡时间比另外两种算法晚100轮左右、网络失效时间也晚100轮以上.

图 3 节点生存周期

另外, 为了进一步比较3种算法的节点生存时间, 实验运用统计学中成对比较实验法, 对EEUC、LEACH和IEEUC的10次运行结果进行T检验. 如表2~表5. 具体地, 表2表3中的数值越大, 说明第一个节点死亡时间和网络失效时间越长. 因此, 取表2表3中IEEUC—EEUC和IEEUC—LEACH的结果作为成对数据差 ${u_d}$ , 对其进行显著性水平为 $\alpha = 0.05$ 的单侧T检验, 检验假设为: ${H_0}:{u_d} = 0, $ ${H_1}: {u_d} > 0$ , 样本容量 $n = 10$ , 自由度 $f = 9$ .T检验结果如表4表5, 其中T为查表临界值. 从表4表5中可以看出: 统计量t均大于临界值T, 对应接受备择假设 ${H_1}:{u_d} > 0$ , 说明IEEUC算法对应的首节点死亡时间和网络失效时间均优于EEUC和LEACH算法.

3.2 能量使用情况对比

为了对比3种算法的网络剩余能量和节点平均剩余能量随时间的变化情况, 实验随机进行10次, 取平均结果如图4图5, 从图中可以看出: 大约从300轮开始, IEEUC算法的能量消耗速度高于EEUC, 说明本文提出的机制利用了Sink附近更多的簇头节点帮助转发数据, 在一定程度上造成了能耗增长. 但是, 文中2.2.1分析了本文负载分流方案是为均衡Sink附近簇头的能耗, 避免相应位置产生能量空洞, 延缓网络的整体失效时间. 结合没有免费午餐定理(No Free Lunch, NFL)来看, 本文方案带来的能耗增加是可接受的.

表 2 第一个节点死亡轮数

表 3 网络失效轮数

表 4 表2数据T检验结果

表 5 表3数据T检验结果

3.3 节点密度变化时算法效果对比

在算法涉及的网络参数中, 节点个数N直接关系到网络区域内节点密度, 以下在节点个数变化时, 分别选择10次实验平均结果对比3种算法对应的首节点死亡时间(如图6)和网络失效时间(如图7).

图 4 网络剩余能量

图 5 节点平均剩余能量

图 6 不同节点个数对应的首节点死亡时间

图6图7中可以看出: 随节点个数的增加, 3种算法的首节点死亡轮数和网络失效轮数都有降低趋势, 但是IEEUC算法对应的首节点轮数大于其余两种算法40%以上, 网络失效轮数晚60%以上. 由此说明, IEEUC算法在节点密度变化时对应的网络生存时间仍优于EEUC和LEACH.

图 7 不同节点个数对应的网络失效时间

通过以上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