基于多Sink的长链状无线传感器网络功率控制算法*

夏 旭,陈志刚,曾 锋,吴 嘉

(1.湖南安全技术职业学院电气与信息工程系,长沙 410151;2.中南大学软件学院,长沙 410083)



基于多Sink的长链状无线传感器网络功率控制算法*

夏 旭1,2*,陈志刚2,曾 锋2,吴 嘉2

(1.湖南安全技术职业学院电气与信息工程系,长沙 410151;2.中南大学软件学院,长沙 410083)

长链状无线传感器网络常用于矿井、隧道等特殊场景,传统的无线传感器网络由于只有一个Sink,应用在长链状无线传感器网络中容易造成Sink周围区域出现“热区”现象,影响网络整体生存期,为了解决上述问题,降低长链状无线传感器网络的整体能耗,延长网络生存期,提出一种多Sink分布式功率控制算法,该算法引入多Sink的网络结构,同时采用非均匀成簇的思想,将多Sink网络结构和分簇的Voronoi scoping路由算法进行结合,为每个Sink分配最优的通信半径和发射功率,将各Sink作为簇头,对网络进行分簇,从而在保证网络覆盖率的前提下,优化网络拓扑,仿真结果表明,该算法在连通度、能耗有效性、分簇干扰和网络性能上具有优势,可以有效的降低网络整体能耗、延长网络生存期。

长链状;无线传感器网络;多Sink;功率控制

基于无线传感器网络的监控技术是一门交叉性强、知识集成度高的新兴技术[1]。由于无线传感器网络本身具有放置灵活、移动性强和自组织等特点,因此,非常适应于煤矿巷道环境监控[2]、油气管道流量监控、隧道交通监控、桥梁监控等长链状的特殊环境中[3],然而,传统的无线传感器(WSN)路由协议在这种长链状场景下存在一定的局限性。

目前,在WSN的路由协议研究中,一般分为平面式路由协议和分簇式路由协议两大类,其中,分簇式路由协议的思想是将网络划分为簇,簇由簇头节点和簇内成员节点组成,簇头负责收集簇内其他成员节点的数据并进行融合,最后将融合后的数据发送到Sink节点,这种分簇式的路由协议的优点是:成员节点大部分时间可以关闭通信模块,由簇头负责数据的远距离转发,有利于能耗的均衡,有效延长网络生存期;簇内成员节点功能简单,无须维护复杂的路由信息,有效的减少了通信;分簇的方式有利于簇内成员节点的管理,有利于网络的稳定性,因此,分簇式的路由协议更适合规模较大的无线传感器网络[4]。分簇算法中具有代表性的有LEACH[5]、TEEN[6]和PEGASIS[7]等。然而,这些分簇算法都是采用单Sink的网络结构,簇头节点和Sink是一跳直接通信,远离Sink的簇头节点必须工作在大功率状态,在规模较大的网络中,需要更大的能耗,将影响网络的生存期,同时,长距离传输数据所带来的干扰问题也是不能忽视的。因此,本文提出对于长链状的基于WSN的监控网络,采用多Sink的网络结构,从而解决以上问题。

在已有的多Sink无线传感器网络研究中,大部分研究集中在研究网络中Sink的最优数目和最佳部署位置来延长网络生存期,研究如何实现Sink之间的负载均衡,从而减少传输过程由于拥塞和碰撞造成的丢包问题。文献[8]中使用k-均值的迭代聚类技术获得最优的Sink数,并确定各Sink的最佳位置。文献[9]提出了一种基于基因表达式的新方法来解决多Sink网络中的Sink最佳部署位置问题,文献[10]根据存储在路由表中的信息素水平值从邻居节点中选择下一跳节点,文献[11]同样也是利用信息素水平值向多Sink转发数据。在最近的研究中,文献[12]提出了一种基于贪婪算法的多Sink部署位置优化算法(MSGA),可以使数据的延时最小化,从而更好的支持实时应用。以上这些算法,并没有针对长链状的环境进行研究,难以应用到长链状的WSN的监控网络中。

基于以上分析,本文提出将多Sink网络结构和分簇的路由算法进行结合的分布式功率控制算法(DPCA-MS:Distributed power control algorithm in Multi-Sink WSN),其中,分簇路由是采用文献[13]提出的Voronoi scoping算法,该算法在Voronoi分簇过程中具有零开销的特点,网络数据的重叠程度也不会因为网络规模和Sink的数目增长而发生变化,有利于减少多Sink网络的整体能耗。通过DPCA-MS算法可以在Sink之间协商最优通信半径,从而获得最佳的连通性,达到延长网络生存期,及时快速的传送监测数据的目的。

1 系统模型

1.1 网络系统模型

本文所研究的无线传感器网络主要是针对长链状结构的监控网络,这种链状结构的特点是长度远远大于宽度,因此,需要在链路上部署若干个Sink,sensor节点周期性的采集数据,并将监测数据传送给最近的Sink,DPCA-MS算法是由各Sink协商确定Sink的最优通信半径和发射功率,在此基础上,将各Sink作为分簇的簇头节点,利用Voronoi scoping算法[12]进行分簇,从而在保证最佳连通性的基础上,优化网络拓扑,降低网络整体能耗,减少分簇干扰,延长网络生存期。

本文讨论的DPCA-MS算法的长链状监控系统结构如图1所示,在链路中央位置每隔一段随机距离(不超过Sink最大通信半径)设置一个Sink,每个Sink通过GPS或者定位机制获得自身位置信息,每个Sink在其通信半径内广播功率控制消息PCM(power control message),为了保证任意两个Sink可以交换PCM信息,假设初始阶段,每两个Sink可以相互通信,每个Sink可以接收某一区域内sensor节点的监控信息。

图1 长链状多Sink传感器网络结构图

为了方便研究,假设网络中sensor节点个数为N,分布在一个狭长的L×W区域内,并且L≥W,sensor节点和Sink一旦部署完毕,位置固定,不再发生位置改变;sensor节点和Sink的发射功率可控,并且可以根据接收信号的强度推算出节点之间的距离和接收功率大小;sensor节点同构,初始能量相同,具有数据融合和自我剩余能量感知功能,Sink能量不受限制。

1.2 功率控制模型

在文献[14]中描述了功率控制机制中如何确定合适的发射功率值,根据电波在自由空间传播损耗的Friis公式,可以得到接收端功率:

(1)

式中:Pr表示节点的接收功率,Pt表示节点的发射功率,gt和gr表示发送天线和接收天线的增益,d表示发送节点和接收节点之间的距离,λ表示由载波频率所决定的载波波长,在常用的2.4GHz无线传感器中,λ的值通常取0.1,n表示信道衰落系数,通常取值为2,由于参数gt、gr、λ都是传感器网络自身的参数,所以网络确定后,这些参数的值就确定了,因此,对于一个确定的网络,可以将这些参数统一用φ表示,即:

(2)

此时,可以将接收端功率公式改写为:

(3)

由此可以得到分簇中Sink节点到簇内子节点的发射功率为:

(4)

显然,当d的值为Sink的最佳通信半径时,可以通过式(4)计算获得最优的发射功率,因此,发射功率的控制问题可以转化为通信半径的控制问题。

2 DPCA-MS算法设计

2.1 网络覆盖率分析

定理1 将两个Sink分别部署在a×b的矩形区域P内,且位于矩形区域的中央线上,为了保证Sink对网络的覆盖率,两个Sink的无线射程的圆环必须相交于区域P外,同时,与Sink对应的矩形顶点也必须位于Sink的无线射程内。

证明:2个Sink分布在a×b的矩形ABCD内,如图2所示,表示两个Sink的无线射程圆相交于E和F两点,为了保证网络覆盖率,需要满足式(5)的关系:

(AEFB∪EDCF)⊇ABCD

(5)

EF为两圆相交的两交点之间的连线,它和矩形的AD边相交于E′,和BC边相交于F′,为了满足式(5)的关系,需要满足EF≥E′F′,因此,两个Sink的无线射程的圆环必须相交于区域P外。

图2 具有2个Sink的WSN

假设Sink节点S2所对应的矩形顶点D和C不在其无线射程内,如图2所示,此时该矩形顶点延伸为D′和C′,矩形ABC′D′和S2的无线射程圆相交于H、H′、G和G′,显然,此时两个Sink的无线射程圆环所覆盖的范围无法包含整个矩形区域ABC′D′,即:

(AEFB∪EHGF∪HH′GG′)⊂ABC′D′

(6)

显然,式(6)不符合式(5)的要求,因此,为了保证网络覆盖率与Sink对应的矩形顶点也必须位于Sink的无线射程内。

根据定理1,网络中存在两个Sink,其无线射程分别为RS1和RS2,需要满足以下公式:

(7)

式中:(x,y)是位于Sink通信范围内的任意sensor节点,(xs1,ys1)和(xs2,ys2)分别为两个Sink的坐标,为了在保证网络覆盖率的前提下,最小化每个Sink的发射功率,本节定义了函数f:

(8)

s.t.

这里是以2个Sink的情况进行为例进行说明,当网络中存在更多Sink时,以此类推即可。

2.2 邻居Sink的发现

在DPCA-MS算法中,只需要为Sink定义一种数据包,如图3所示,该数据包可以被称为握手包,它包括3个数据域:包头、Sink标识ID、Sink位置信息,其中Sink标识ID全网唯一,而且呈升序排列。网络初始化时,各Sink节点通过发送握手包使每个Sink获知其他Sink的相关信息。

图3 DPCA-MS算法中握手包的帧格式

2.3 分布式功率控制算法

在L×W的网络中部署k个Sink,其坐标用(xsi,ysi)表示,1≤i≤k,为了方便描述,令P(X,Y)为一矩形区域,X为矩形的长,Y为矩形的宽,且X>Y,Cir(xsi,ysi,rsi)表示以(xsi,ysi)为圆心,以rsi为半径的圆形区域,为了保证网络覆盖能够达到100%,必须满足以下条件:

P(X,Y)⊂Cir(x1,y1,r1)∪Cir

(x2,y2,r2)∪…∪Cir(xk,yk,rk)

(9)

在DPCA-MS中,为了保证在每个Sink控制其发射功率后,仍能够100%的覆盖整个网络,需要每个Sink节点互相协商出合适的发射功率,根据式(4)在获得各Sink的通信半径后,就可以计算出其发射功率,因此,发射功率的计算问题转化为通信半径的求解问题。

首先,每个Sink利用定位算法获得自身的坐标信息,然后,通过广播邻居Sink发现握手包和PCM消息,告知邻居Sink各自的位置信息,Sink收到握手包后,根据握手包中的Sink标识ID,由SinkID最小的Sink与矩形区域相应顶点的距离作为无线射程,此时,在该Sink的无线射程圆和矩形边界有4个交点,如图4中的S1所示,其他的Sink在选择合适的无线射程时,与矩形边界也有4个交点,如图4中的S2所示。

图4 具有2个Sink的WSN

本文认为,当以每个Sink节点为圆心,相应的无线射程为半径的圆与矩形区域的边界相交后,只要切割线段的并集包含整个矩形的4条边界,则能保证Sink节点对整个网络的覆盖。此时,从第2个Sink开始的无线射程ri,i∈k,必须满足以下关系:

(10)

根据这一理论,如图5所示,以网络中存在3个Sink为例,说明Sink节点选择无线射程的3种情况:(a)选择偏大;(b)选择合适;(c)选择偏小,通过计算可以使各Sink获得最理性的无线射程,从而使每个Sink自动调节选择合适的发射功率。

图5 网络中有3个Sink时无线射程的选择

图6 Sink无线射程计算过程图例

图6是一个简单说明无线射程计算过程的图例,S1和S2位置部署了2个Sink,S1的坐标为(xs1,ys1),S2的坐标为(xs2,ys2),S1为第1个Sink,其Sink标识ID为1,该Sink将|S1B|作为自己的无线射程,记为RS1,然后S2根据RS1计算其无线射程RS2:

(11)

由此可见,各Sink的无线射程RSi,可以表示为:

(12)

在各Sink的发射功率调整完毕后,就可以使用文献[13]提出的Voronoiscoping算法对各Sink所在的区域进行分簇,分簇完成后,各分簇内的sensor节点可以和所在簇的Sink节点进行一跳通信。此时,利用图论的方法将网络描述为:Net=(O,V),其中O表示k个Sink和N个sensor节点的集合,S⊂k是SINK的集合,且|S|=k,V表示一条链路的权重系数,dij表示节点i和j之间的最短距离,此时,某Sink节点m所对应的Voronoi分簇可以表示为:

(13)

在Voronoiscoping分簇算法中,每个sensor节点必须知道自身以及每个Sink节点的坐标信息,可以通过定位算法或者GPS系统解决该问题。

实际上,发射功率维持是一个根据实际工作环境实时的调整自身发射功率的过程,当路由失效后,sensor节点将启动备用路由或寻路机制,从而使每个Sink重新配置发射功率,DPCA-MS算法对Sink无线射程的估算是基于本地Sink之间的链接状况,于是其功率的维持可以通过周期性的交换广播功率控制消息PCM(powercontrolmessage)来实现。因此,可以将DPCA-MS算法描述为表1。

表1 DPCA-MS算法

3 算法性能评价

为了验证DPCA-MS算法适合于长链状无线传感器网络的特殊长带状结构,本节将建立多个网络仿真环境,在连通度、能耗有效性和分簇干扰性能上,将DPCA-MS算法分别和MSGA算法以及使用最大发送功率的情况进行对比分析,在网络性能上针对延时和网络负载,对比DPCA-MS算法中随着Sink数量增加对网络性能的影响情况。连通度可以证明算法的可行性和健壮性。由于每个sensor节点能量有限,能耗的有效性成为算法需要考虑的关键因素,本节的能耗有效性被定义为所有Sink经过DPCA-MS算法对发射功率进行控制后所产生的总能耗最小。分簇干扰是为了考虑传感器节点在决定自己所属簇时受到非自身中心Sink干扰的情况。

实验中采用Java语言,利用OMNET++4.2作为仿真工具,在Windows操作系统下搭建仿真平台,实验中Node和Sink采用简单模块,分别定义为node.ned和Sink.ned,实验的其他参数如表2所示。

表2 仿真具体参数

3.1 连通度

为了保证在执行DPCA-MS算法后,sensor节点和Sink之间能正常通信,本节定义了一个称为平均连通度的参数,该参数是指被任一Sink所覆盖的sensor节点占全部sensor节点的比例。所有实验都是1 000次求平均的结果。

如图7所示为DPCA-MS算法在Sink数量变化时,分别和MSGA算法以及使用最大发射功率3种情况下网络的平均连通度对比情况,显然,随着网络中Sink的增加,网络平均连通度也相应增加,当Sink数达到12个时,平均连通度接近100%,使用DPCA-MS算法后的平均连通度明显好于MSGA算法和使用最大发射功率两种情况,但是,当Sink数达到6个后,3种算法获得的网络平均连通度差别不大。

图7 平均连通度对比

3.2 能耗有效性

在长链状的监控网络环境中,例如,煤矿、隧道、石油管道等,通常不便于更换电池,因此,为了尽可能的延长网络生存期,必须注重能耗的有效性。本节能耗的有效性被定义为:网络中的sensor节点有多个一跳可达的Sink节点,通过对Sink的发射功率进行合适的控制,使所有sensor节点一跳到达Sink所用的总能耗最小。

假设网络中有k个Sink,根据式(4)所描述的发射功率与接收功率、通信距离之间的关系,可以将网络中的总发射功率Psum表示为:

当通信距离最大时,即为通信半径,因此,网络中总的发送功率大小可以利用DPCA-MS算法所计算的各Sink通信半径求和得到。根据文献[14]所描述的Sink发射功率、发射半径和能耗之间的关系,可以得到如图8所示的仿真结果,该结果表示在Sink数量发生变化时,使用DPCA-MS算法、MSGA算法以及使用最大发射功率3种情况下总能耗的对比,显然,DPCA-MS算法可以带来更多的能耗节省,随着Sink数量的增加,能耗节省的量也越多,当Sink数量达到12时,DPCA-MS算法控制的发射功率所消耗的能量比Sink使用最大发射功率所消耗的能量降低了75%,同时,由于网络中sensor节点可以接收到更少的从Sink发出的广播包,也能有效的减少sensor节点接收数据包的能耗,从而使网络的整体能耗下降。

图8 Sink总发射功率对比

3.3 分簇干扰

为了减少簇内的干扰,常用的方法是使用文献[15]提出的基于发射机的编码分配,即每个簇采用独立的扩频编码,每个簇内节点与簇头间的通信都采用唯一的扩频码,簇内节点使用该扩频码传输数据给簇头,簇头节点则根据扩频码对接收信号进行过滤。

本文将分簇干扰定义为一个sensor节点一跳内的平均Sink数,当一个sensor节点需要选择一个Sink作为其中心Sink时,它从邻居Sink收到的广播包越少,就能越节省接收数据包的能耗。如图9所示,在Sink数量发生变化时,使用MSGA算法和使用最大发射功率时,每个sensor节点一跳内的平均Sink数量明显大于使用DPCA-MS算法时的数量,当Sink数为12时,使用MSGA算法,每个sensor节点一跳内的Sink数量约为4个,使用最大发射功率,每个sensor节点一跳内的Sink数量约为5个,而使用DPCA-MS算法后,则仅为2个,分簇干扰的可能性降低了50%,因此,sensor节点只需要在少数几个Sink中选择中心Sink。使用DPCA-MS算法后,每个Sink的通信覆盖范围尽可能的缩小,因此,只有少量sensor节点能收到某一Sink的广播包,从而减少了网络中节点间的相互干扰,同时也大大降低了sensor节点在分簇时受到的干扰。

图9 分簇干扰情况对比

图10 不同数目Sink条件下数据包的延时对比

3.4 网络性能

由于该算法主要针对长链状的监控系统,因此,在网络性能上主要针对数据包的延时情况和网络MAC层负载情况进行测试。这里的延时是指数据包从sensor节点到Sink的时间,网络MAC层负载是指每秒MAC帧要承载的上层数据的数量,将网络场景设置为100 m×5 m矩形区域,Sink数为4个,sensor节点数为30个,数据包发送速率均为1 000 bit/s,测试时间为10 min,所有sensor节点的通信半径限制为10 m。

如图10所示是不同数目Sink条件下数据包的延时对比,当Sink数为4时,数据包的延时下降幅度最大,可见,随着Sink数量的增加,数据的延时呈下降趋势。由于在DPCA-MS算法中,随着Sink数量的增加,数据传输的路径会更短,负载将更轻,因此,可以大幅的减少网络拥塞,也就是说Sink数量越少,发生网络拥塞的可能性越大,数据包延时的程度也更高。

如图11所示是不同数目Sink条件下网络负载情况对比,当Sink数为4时,网络负载的增幅最小,可见,随着Sink数量的增加,网络负载呈下降趋势。当更多的Sink部署在网络中,源sensor节点可以选择距离自己最近的Sink发送数据,因此,可以大幅减少整个网络的通信跳数,从而降低网络的整体负载,同时也可以降低能耗。

图11 不同数目Sink条件下网络负载情况对比

4 结束语

本文根据长链状无线传感器网络的结构特点,提出了一种将多Sink网络结构和分簇路由相结合的多Sink分布式功率控制算法DPCA-MS,并在仿真工具OMNET++环境下实现了建模和仿真。仿真结果证明该算法在连通度、能耗有效性、分簇干扰和网络性能上符合长链状结构的多Sink的网络环境,能有效的延长网络生存期、降低能耗。

[1] 张蕾. 无线传感器网络中多重覆盖算法的研究[J]. 传感技术学报,2014,27(6):802-806.

[2] Xia X,Chen Z,Li D,et al. Proposal for Efficient Routing Protocol for Wireless Sensor Network in Coal Mine Goaf[J]. Wireless Personal Communications,2014(77):1699-1711.

[3] 臧哲,齐建东,张晓武,等. 基于智能算法的层次型多链WSN路由协议[J]. 传感技术学报,2013,26(4):558-563.

[4] Manap Z,Ali B M,Ng C K,et al. A Review on Hierarchical Routing Protocols for Wireless Sensor Networks[J]. Wireless Personal Communications,2013,72(2):1-28.

[5] Wendi B H,Anantha P C,Hari B. An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J]. Wireless Communications,2002,1(4):660-670.

[6] Manjeshwar A,Agrawal D P. TEEN:A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks[C]//Proceedings of IPDPS,San Francisco,CA,USA,April 2000:2009-2015.

[7] Stephanie L,Cauligi S R. PEGASIS:Power-Efficient Gathering in Sensor Information Systems[C]//Proceedings of the IEEE Aerospace Conference,Big Sky,MO,USA,March 2002:1125-1130.

[8] Oyman E I,Ersoy C. Multiple Sink Network Design Problem in Large Scale Wireless Sensor Networks[C]//IEEE International Conference on Communications,2004:3663-3667.

[9] Dai S,Tang C,Qiao S,et al Optimal Multiple Sink Nodes Deployment in Wireless Sensor Networks Based on Gene Expression Programming[C]//International Conference on Communication Software and Networks(ICCSN),2010:355-359.

[10] Paone M,Paladina L,Scarpa,et al. A Multi-Sink Swarmbased Routing Protocol for Wireless Sensor Networks[C]//IEEE Symposium on Computers and Communications(ISCC),2009:28-33.

[11] Wang W,Li W,Chen D,et al. Ant Colony Based Routing Algorithm for Multi-Sink Networks[C]//WRI World Congress on Computer Science and Information Engineering,2009:423-429.

[12] Donghyun Kim,Wei Wang,Nassim Sohaee,et al. Minimum Data-Latency-Boundk-Sink Placement Problem in Wireless Sensor Networks[J]. IEEE/ACM Trans Netw,2011(5):1344-1353.

[13] Henri D F,Deborah E. Efficient and Practical Query Scoping in Sensor Networks[R]. Technical Report 39,CENS,UCLA:Los Angeles,CA,USA,April 2004.

[14] Woo A,Terence T,Culler D. Taming the Underlying Challenges of Reliable Multihop Routing in Sensor Networks[C]//Proc of Conf on Embedded Networked Sensor Systems. New York,USA:ACM Press,2003:14-27.

[15] Hu L. Distributed Code Assignments for CDMA Packet Radio Networks[J]. IEEE/ACM Transactions on Networking,1993,1(6):668-677.

[16] Liu A,Jin X,Cui G,et al. Deployment Guidelines for Achieving Maximum Lifetime and Avoiding Energy Holes in Sensor Network[J]. Information Sciences,2013,230:197-226.

夏 旭(1980-),女,湖南省益阳人,副教授,博士研究生,青年骨干教师,主要研究方向为无线传感器网络,wuwuxuxu@163.com;

陈志刚(1964-),男,湖南益阳人,教授,博导,主要研究方向为可信计算、网络与分布式计算、数据库技术;

曾 锋(1977-),男,广东梅州人,副教授,博士,主要研究方向为无线网络技术;

吴 嘉(1983-),男,贵州贵阳人,博士研究生,主要研究方向为机会网络、软件工程,jiawu5110@163.com。

Multi-Sink Distributed Power Control Algorithm for Wireless SensorNetworks with Long-Chain Structure*

XIAXu1,2,CHENZhigang1,ZENGFeng1,WUJIA1

(1.Hunan Vocational College of Security Technology,Changsha 410151,China;2.School of Software,Central South University,Changsha 410083,China)

Long-chain wireless sensor networks are used in special scenes such as mines,tunnels,etc. The traditional wireless sensor network has only one Sink,so it causes the“hot spot”problem easily and reduces the lifetime of the network when it is used in the long-chain scenes. In order to solve these problems,this paper proposes a Multi-Sink distributed power control algorithm. This algorithm uses the Multiple Sink network structure together with the idea of non-uniform cluster,and combines the multi-Sink network with the clustering Voronoi scoping routing algorithm. It allocates the optimal transmission range and power for each Sink,and clusters the network with each Sink as the cluster head,in order that the network topology is optimized on the basis of a good network coverage rate. Simulation results show that the new algorithm exhibits superior connectivity,power consumption validity,clustering interference,and network performance. Thus it can reduce the overall power consumption and prolong the service life of the network.

long-chain;wireless sensor network;Multi-Sink;power control

项目来源:国家自然科学基金项目(61379057,61309001,61272149);教育部博士点基金优先发展领域课题项目(20120162130008);博士生自主探索创新项目(2014zzts043);2015年安全生产重大事故防治关键技术科技项目(hunan-0012-2015AQ)

2014-12-28 修改日期:2015-03-12

C:6150M;6150P;7230

10.3969/j.issn.1004-1699.2015.06.024

TP393

A

1004-1699(2015)06-0920-07