基于分簇的无线传感器网络编码算法①

钟达夫,薛晶晶,唐懿芳,赵仕俊

1(广东科学技术职业学院 计算机工程技术学院(软件学院),珠海 519090)

2(延安大学 物理与电子信息学院,延安 716000)

3(企业信息化与物联网测控技术四川省高校重点实验室,自贡 643099)

4(中国石油大学(华东) 信息与控制工程学院,青岛 266580)

近几年来,无线传感器网络(WSN)得到了广泛关注,大量低成本的感知、处理器件以及有效的无线通信协议出现,使得该项技术被应用在各个领域,包括基础设施保护、工业检测和诊断、战场和环境监测、家庭自动化、智能办公、智能交通等[1–3].由于传感器节点体积较小,所以携带的电池能量有限,存储能力不足.通常节点部署在人无法直接到达的恶劣环境,无法给电池充电或者更换电池,当电池能量耗尽,这个节点就会“死亡”,在一定程度上影响整个网络性能,所以在设计算法时需要考虑能量使用效率从而提高网络性能,并有效延长网络的使用寿命.目前,很多学者已经提出了最大化网络使用寿命的若干算法.在多种方法中,成簇机制能够有效节省节点能量,减少能耗,从而提高网络使用寿命[4,5].

组网过程中,节点以成簇的方式被分成若干组[6],每组包括簇头节点和簇内成员节点,簇内成员节点负责数据的采集并转发给簇头节点,并由网关节点转发到基站.簇头节点负责数据的转发和融合,因此比其他节点消耗更多的能量.同时,如果簇头在转发来自簇内成员节点的数据时不经过处理,那么会消耗更多的能量.因此,本文中,在选择簇头节点时将节点剩余能量考虑在内,并使簇头节点对收到的信息进行网络编码,从而优化网络吞吐量,减少网络负载.

分簇算法和随机线性网络编码相结合,可以实现对采样数据压缩的目的,从而进一步节省网络能量消耗.华国刚[7]于2005年提出将分布式信源编码应用于连状簇的方案,沿着信号路径进行相关信源编码.Mounir[8]在2010年提出将分布式信源编码应用于多跳簇的方案,同时给出了两种数据融合方式,即沿着信号路径向前融合和向后融合.但是这两种方案仅仅利用了两个相邻节点间的相关信息,压缩效率较低,解码比较复杂,同时在簇的形成过程中没有考虑节点剩余能量.针对上述不足,本文尝试将随机线性网络编码应用到分簇的无线传感器网络中,由此延长网络的生命周期,均衡网络能量消耗.

1 随机线性网络编码原理

随机线性网络编码方法的核心思想是利用节点的运算能力,在发送节点处用线性编码组合不同的信息包,在接收节点处获得足够的线性编码组合后,通过运算得到原始信息包,其推广了网络编码理论的应用范围[9,10].

将传统传输和随机线性网络编码传输进行比较如图1所示,无线节点B1需要发送信息包X、Y、Z.图1(a)表示了传统传输的情况,发送节点逐一发送信息包X、Y、Z; 图1(b)表示了随机线性网络编码传输的情况,当节点具有编码能力,可以选取随机参数编码组合α1X+α2Y+α3Z、β1X+β2Y+β3Z、γ1X+γ2Y+γ3Z(其中的参数随机获得,参数值写入编码包中发送),广播逐一发送编码包,接收节点接收到三个编码组合包后,通过线性运算可以解出原始信息包X、Y、Z完成信息传输.

图1 传统方法和随机线性网络编码方法的信息传输比较

采用随机线性网络编码方法,接收节点处理的问题从是否收到完整信息包,转换为是否收到足够多的满足可解性条件的编码包.通过研究发现[11–13],随机线性编码组合发送可以带来良好的吞吐量、鲁棒性、安全性等方面的增益,为网络性能的改善提供了一种新的途径.

2 算法描述

基于簇的线性网络编码算法适用的网络拓扑结构如图2,考虑基于簇的无线传感器网络,网络中大量的节点在单位时间内采集的数据由簇头传输给网关节点.从图2可以看出,本文将网络分为两层.第一层中节点被分成许多簇,簇内成员节点发送数据给簇头节点.第二层是簇头节点之间的通信,将采集的信息传输给基站.

图2 网络拓扑结构

本文提出的算法被分为两个阶段,分别为簇形成阶段与数据采集阶段.

(1) 簇形成阶段: 簇头节点选择同时考虑节点自身ID和剩余能量.在簇形成的开始阶段,节点ID设为1,2,…,n,节点将其ID存入节点区.节点广播的消息中包含节点自身ID值和剩余能量,在通信范围内的节点会收到该消息.算法初始阶段,节点剩余能量相同,簇头选择按照ID值,如果自身的ID值大于接收到节点的ID,该节点就会广播簇头当选通告.当一个采样周期结束后,以节点剩余能量来选择,如果自身的剩余能量大于接收到的节点的剩余能量,就会广播簇头当选通告.簇头选择好后,该节点会发布相应的当选消息,该消息包括自身ID值.网络内的所有节点在时间Tw内收到簇头竞选通告.时间Tw后,如果一个节点只收到一个簇头竞选通告,即MCH_advertise=1,则该节点加入该簇,成为簇内成员,并向簇头发送连接消息.如果一个节点接收到两个以上的簇头广播通告,即MCH_advertise>1,则该节点根据接收信号强度(RSSI),选择接收信号强度最大簇头加入,成为其簇内成员.如果节点没收到任何簇头当选通告,即MCH_advertise=0,则该节点通告自己成为簇头并形成独立的簇.

(2) 数据采集阶段: 在数据采集阶段,簇内的每个节点发送自己的数据包给簇头节点,簇头完成相应数据包的网络编码.簇头节点在它的缓冲区内采用随机线性网络编码对N个数据包进行编码,然后广播编码完成后的数据包.网络编码有许多优点: 减少传输能量、提高网络吞吐量.

当从簇内节点接收到n个原始数据包(M1,M2,M3,…,Mn)后,在有限域F内随机均匀的选择一系列因子(g1,g2,…,gn),然后簇头节点根据以下方程进行编码:

中间的簇头节点作为中继节点将数据包成功的传输到网关节点.在接收到n个独立的编码数据包后,在网关节点处通过线性方程被译码.

3 算法的仿真与结果分析

3.1 仿真设置

仿真实验采用NS2仿真平台,主要仿真参数设置如表1.

表1 仿真参数

在仿真过程中,本文假定节点部署之后是静止的,所有节点是同构的.网关节点的位置固定且离整个网络较远,数据经过簇头节点传输给网关节点.数据源为CBR 流,分别为 20、40、60、80、100.

网络节点采用随机分布方式进行布置,100节点分布如图3所示.

图3 网络节点分布图

3.2 仿真结果

为了验证和评估提出的算法,将标准协议AODV(Ad hoc On-demand Distance Vector routing)[14–16]和本文提出的算法在网络生命周期、分组投递率、网络延时方面做了比较,图4显示了仿真时间内存活节点的总数,存活节点为0时刻定义为网络的最大生存周期,由图4可以看出,本文提出的算法和AODV协议相比,第一个节点死亡的时间和全部节点死亡都较晚,体现了本文提出的算法不仅使节点能耗降低而且能量消耗更加均衡.

图4 存活节点个数

分组投递率表示网络使用该协议能够支持的最大吞吐量,详细刻画了协议的性能和正确性.图5(a)、(b)、(c)分别反映了源节点发送数据包的速率分别为2、10、20个分组时,两个协议在不同数量源节点时的分组投递率.

从图5可以看出,本文提出的算法分组投递率比AODV协议大,分组发送率是2时,结果不是很明显,但是当分组发送率为10和20时,本文算法的分组投递率远大于AODV协议.这表明,本文协议在处理大负载的数据包时,丢包率更低,网络稳定性、鲁棒性也较好.

仿真结果表明,本文提出的协议网络能耗更加均衡,有效延长了网络生命周期,同时在分组投递率和端到端延迟方面性能都比较优,而且更适用于大负载的无线网络环境中.

图6(a)、图6(b)、图6(c)分别反映了源节点发送数据包的速率分别为2、10、20个分组时,两个协议源节点数量改变时端到端的延时图.从图6可以看出,当分组发送率为2时,本文提出的算法在源节点数量为20～60时延迟大于AODV,这是因为簇头节点将数据包保存在自己的缓冲区,直到超过一定的数量才进行传输.然而当源节点数量超过60时,本文提出的协议明显优于AODV.图6(b)、图6(c)表明,当源节点数量小于40时,本文提出的协议和AODV协议性能相同,但是当超过60后,本文的协议明显优于AODV协议,这表明,本文的协议更适用于大负载的网络环境中.

图5 分组投递率与源节点数的关系图

图6 端到端延时与源节点个数关系图

4 结论

本文提出了基于簇的网络编码协议.通过让簇头节点进行网络编码,同时在选择簇头节点过程中,考虑节点剩余能量,从而均衡了网络能量消耗,延长网络生命周期,增加整个网络的吞吐量; 只有簇头节点进行网络编码并将数据包传输给网关节点,这样能够节省簇内成员节点的能量消耗.仿真结果表明本文提出的算法在延长网络生命周期,均衡能量消耗,分组投递率和端到端延迟方面明显优于AODV协议,并且更适用于大负载的网络环境.