能耗均衡的移动传感器节点派遣算法*
2014-09-06苗春雨戴国勇陈宇铮陈庆章
苗春雨,戴国勇,陈宇铮,陈庆章
(1.浙江工业大学计算机科学与技术学院,杭州 310014;2.浙江师范大学行知学院,浙江 金华 321004)
能耗均衡的移动传感器节点派遣算法*
苗春雨1,2,戴国勇1,陈宇铮1,陈庆章2*
(1.浙江工业大学计算机科学与技术学院,杭州 310014;2.浙江师范大学行知学院,浙江 金华 321004)
在混合无线传感器网络中,移动传感器节点最耗能的操作是移动,如何减少移动传感器节点的移动距离同时能让其完成任务是一个富有挑战性的研究课题。本文提出了一个移动传感器节点的派遣算法,旨在均衡各个移动传感器节点的移动负载,并且能按优先级响应事件地点,适用于任意数量的移动传感器节点和事件地点的情况。当移动传感器节点数量大于事件地点数量时,将其转化为一个带权完全二分图上的最大匹配问题。当事件地点数量大于移动传感器节点的数量时,本文提出的算法先将事件地点聚类分簇,然后派遣移动传感器节点到各个簇中分别完成访问任务。为了减少传感器节点之间的消息传输量,本文在集中式算法的基础上又提出了一个分布式算法。仿真实验结果表明本文提出的分布式算法能有效降低传感器节点之间的消息传输量,算法能够使得整个混合无线传感器网络的生存寿命延长20%左右。
无线传感器网络;移动传感器节点派遣;负载均衡;最大匹配
我们称一个由静态传感器节点和移动传感器节点组成的无线传感器网络为混合无线传感器网络[1]。移动传感器节点需要在静态传感器节点侦测到环境事件发生时向目标区域移动以做更深入的调查,也需要在静态传感器节点发生故障使得监测区域出现覆盖空洞时向空洞处移动来填补网络空洞[2-3]。因此,在混合无线传感器网络中,一个重要的课题是规划若干移动节点对若干指定事件地点的派遣问题(调度问题)。无论是静态节点还是移动节点一般均采用电池供电,所以减少节点能量的消耗,延长无线传感器网络的使用寿命也是一个值得研究的问题[4]。一般来说,对于一个移动传感器节点,其用于移动的能量消耗是所有能量消耗的主要部分,远大于其用于收集信息、处理信息及网络通信等带来的能耗[5]。当网络中一些静态传感器节点侦测到事件时,处理中心能够获知事件发生地点的所有相关信息,然后移动传感器节点会被派遣到各个事件发生地点以完成时一步的调查。在这个移动过程中,会消耗大量能量。本文针对这一问题,首先提出了一种集中式的移动节点派遣算法,在尽量减少移动传感器节点移动总能耗的同时保证移动节点间的能耗均衡;在此基础上设计了一种分布式的移动节点派遣算法,降低了节点间的通信数据量。最后通过仿真验证了算法的有效性和实用性。本文的主要贡献在于(1)在移动传感器节点派遣算法设计中保证移动节点总能耗较少的同时考虑了节点的能耗均衡(2)提出的方法适用于无障碍物情况下任意的移动节点数量和事件地点数量关系(3)提出了集中式和分布式2种移动节点派遣算法,适应不同的应用场景。
本文其他部分结构如下:第2小节对移动传感器节点调度与派遣的相关工作进行了简要的介绍和总结;第3小节给出移动传感器节点派遣问题的数学模型;第4小节对集中式的能耗均衡节点派遣算法进行详细介绍;分布式的派遣算法在第5小节给出;仿真实验和实验结果的讨论在第6小节进行;第7小节总结全文并指出未来的研究方向。
1 相关工作
当前有大量针对混合无线传感器网络或移动无线传感器网络节点调度的研究[6],文献[7]中提出了一种利用移动信标进行节点定位的方法,移动信标向最大覆盖且未被定位节点区域移动,主要工作针对移动节点的路径规划。文献[8]提出了一种基于虚拟力的混合无线传感器网络节点部署的方法,这个研究在静态传感器节点和移动传感器节点之间建立了一个虚拟势场,利用这个虚拟势场所产生的虚拟力来控制移动传感器节点的运动,使移动传感器能自适应的调整自己的位置,完成网络部署。文献[9]中采用移动传感器节点来修复无线传感器网络运行中产生的覆盖空洞。这些研究的侧重点主要是如何调度移动节点完成网络部署或网络空洞的修补,与移动节点派遣问题存在较大差别。
对混合移动传感器网络中的移动节点派遣问题的相关研究并不是很多,机器人的任务分配问题与本文的研究内容近似。Akkaya[10]等人利用stable marriage算法解决移动机器人事件处理派遣问题,使得机器人的总移动距离最短,但没有考虑能耗问题。文献[11]在考虑能耗均衡的前提下,提出集中式的机器人-事件匹配算法(PMD)及指派算法(SQD)。一方面,无线传感器网络中并不总是存在能够完成集中式运算的设备;另一方面,算法不适用于移动节点数量小于待处理事件数量的情况。Verma[12]等人的研究主要针对单一事件的移动机器人选择和路径设计及导航问题,虽然考虑到了能耗问题,但不适用于事件数量多于机器人数量时的派遣问题。针对上述问题,本文设计的算法适用于任意的移动传感器节点数量和事件地点数量的关系,且在降低总的移动能耗同时,保证节点间的能耗均衡,并且给出了集中式和分布式的2种算法。
2 移动传感器节点派遣问题的数学模型
我们考虑一个由静态传感器节点和移动传感器节点组成的混合无线传感器网络。每个传感器都知道它们自己的位置(可以通过GPS或者其他定位技术来实现。静态传感器节点的密度足够大,使得它们能构成一个覆盖整个传感区域的连通的网络。它们可以持续地监控环境中的一些感兴趣的信息。n个移动传感器S={s1,s2,…,sn}被随机部署在感知区域中,当静态传感器节点检测到事件发生时,移动传感器节点就会被派遣到这些事件地点去做进一步检测。
在移动传感器节点派遣问题中,假设有一个事件地点的集合L={l1,l2,…,lm},每一个事件地点均需一个移动传感器节点来访问。我们允许m和n可以有任意的大小关系。问题的目标就是计算每一个移动传感器节点si的派遣计划SCHsi,使得L中的每一个地点都会且只会被一个移动传感器节点访问一次,且优先级高的事件地点会被优先访问到。每一个派遣计划SCHsi都被表示为一个事件地点的序列,第j个待访问的事件地点表示为SCHsi[j]。令ei是si的当前能量,c(SCHsi)是si要完成派遣计划所需要的能量,则
c(SCHsi)=Δmove×(d(si,SCHsi[1])+
其中Δmove是移动传感器移动单位距离所需要的能量,d(si,SCHsi[1])是si的当前位置到SCHsi[1]的欧几里得距离,d(SCHsi[j],SCHsi[j+1])是SCHsi[j]到SCHsi[j+1]的欧几里得距离。显然地,派遣计划必须要满足ei≥c(SCHsi)。
出于算法性能上的原因,我们为移动传感器节点派遣问题定义2个目标函数。第1个目标函数是最小化移动传感器节点花费的总能量,也就是
(1)
第2个目标函数是最大化传感器移动以后剩余的总能量,也就是
(2)
为了均衡移动传感器的能量消耗,我们在每一轮为移动传感器计算派遣计划时也会同时考虑移动传感器消耗的能量和剩余的能量的标准差。具体来说,移动传感器的能量消耗的标准差是:
(3)
移动传感器的剩余能量的标准差是:
(4)
其中cavg和eavg分别是移动传感器总消耗能量和总剩余能量的平均值。为了均衡移动传感器的负载,我们还需要在计算派遣计划时根据采用式(1)还是式(2)作为目标函数而分别最小化式(3)或式(4)。
上述的建模方式不只考虑到了单轮的移动传感器节点派遣问题,而是在全局的角度来考虑移动传感器节点的派遣调度。大体上来说就是,我们要计算许多轮的派遣计划,其中每一轮都要派遣移动传感器节点到该轮中检测到的事件地点,算法的整体目标是尽可能地延长移动传感器节点所能工作的轮数。每一轮的时间长度取决于用户实际的实时性要求。由于未来可能会发生的事件地点无法被事先预测,所以本研究中只考虑如何优化单轮的派遣计划使得算法达到上述的目标。
3 移动传感器节点集中式派遣算法设计
本章我们提出一个解决移动传感器节点派遣问题的集中式的算法CentralLBSD(Centralized Load Balanced Sensor Dispatch Algorithm),这个算法使用一个中心服务器收集一轮派遣过程中事件地点的集合L和移动传感器节点的集合S的信息。算法首先对所有事件地点按照事件优先级排序,然后对于每一个相同优先级的事件地点集合,算法依次派遣移动传感器节点来访问这些事件地点。为了保证优先级低的事件地点不至于一直不被访问到,每一轮结束以后,该轮中没有来得及访问的事件地点优先级会增大,使得它们在下一轮算法运行过程中能被优先处理。接下来我们讨论在某一种优先级下的移动传感器节点派遣算法的设计。为了减少传感器节点之间的消息传输量,我们在下一章又接着提出了一个分布式的解决方案。方便起见,下文中均用|S|表示移动传感器节点的数量,|L|表示待处理的事件地点数量。
3.1 |S|≥|L|情况下移动传感器节点派遣算法设计
当|S|≥|L|时,对于每一个移动传感器节点si∈S,我们先计算si移动到每一个事件地点lj∈L所消耗的能量c(si,lj)。我们定义消耗的能量函数为c(si,lj)=Δmove×d(si,lj).然后构造一个带权的完全二分图G=(S∪L,S×L),二分图G的点集包含了所有的移动传感器节点和所有的事件地点,对于每一个si∈S和lj∈L,在G里都有一条边(si,lj)。(si,lj)的权值定义为:
w(si,lj)=c(si,lj)
(5)
若采用式(5)作为目标函数,或者
(6)
若采用式(6)作为目标函数,其中emax是一个不小于maxsi∈s{esi}的大数。为了简便,我们就令emax=maxsi∈S{esi}。不难看出,目标函数式(5)和式(6)都可以被看成是为了最小化整个匹配的权值。在图论中,一个匹配P是一个边的集合,其中任意两条边都没有公共顶点。在移动传感器节点派遣问题中,我们的目标就是找到G上的一个匹配P,使得①P里的匹配数最大,②P中所有边的权值和尽可能小,③P的边权值的标准差尽可能小。
为了找到匹配P,我们先给每一个si关联一个优先列表Plist(si),优先列表中包含了所有的lj∈L,且按照权值w(si,lj)递增排序。当边权值相同时,事件地点编号小的排在前面。类似的,对于每一个lj,我们也关联一个优先列表Plist(lj),列表中包含了所有的si∈S,按照权值w(si,lj)递增排序。移动传感器节点与事件地点进行匹配时,按列表项从上到下进行。
为了减小匹配P的标准差,我们给每一个事件地点lj∈L引入一个界Blj来限制lj可以匹配到的候选移动传感器节点。当为事件地点lj找匹配的时候,算法只考虑满足w(si,lj)≤Blj的移动传感器节点si。
为了找到匹配P,我们首先初始化每一个界Blj为每一个事件地点可以匹配到的边的最小值中的平均值,也就是:
(7)
这样对于每一个事件地点lj∈L,我们试着找到一个移动传感器节点si∈Plist(lj)跟来lj匹配,使得w(si,lj)最小并且w(si,lj)≤Blj。如果我们找不到这样的si,那么我们就要持续不断地增大界Blj,界Blj每次增大ΔB,直到事件地点lj能找到一个可用的移动传感器节点为止。我们称ΔB为递增等级,为了在迭代次数与每次匹配所得结果的规模间取得平衡,递增等级ΔB的确定公式如下:
(8)
其中δ是递增等级ΔB的调整系数。根据实验结果δ的值为2.0较好,因篇幅有限,不具体展开说明。
当一个还未匹配的事件地点lj扩大它的界Blj时,就会有更多的候选移动传感器节点出现在它的优先列表Plist(lj)中。如果此时Plist(lj)中第1个还未访问的候选移动传感器节点si也是还未匹配的状态,那么就把(si,lj)加入到匹配中。如果移动传感器节点si已经被跟另一个事件地点lo匹配了,那么根据lj的界Blj和lo的界Blo,我们就能确定si到底应该跟哪个事件地点相匹配。我们称这是一次lj与lo之间的竞争。当以下某一种情况成立时,si就会跟lj相匹配,此时我们就称lj赢得了竞争。
①Blj>Blo。界的增大会使匹配到一条权值过高的边的概率提高,如果lj不和si匹配的话,为了找到可以匹配的移动传感器节点,lj就必须增大它的界Blj,为了避免Blj扩大得太大,所以我们就匹配si和lj。
②Blj=Blo并且lj在si的优先列表里出现在lo的前面。由于lj和lo的界相同,si可以任意选择一个事件地点相匹配,所以si可以选择一个距离最近的事件地点。由于si到lj的距离比到lo的距离要小,所以我们匹配si和lj来减小总的匹配值。
③Blj=Blo并且si是Plist(lj)里的最后一个候选移动传感器节点,但不是Plist(lo)里的最后一个候选移动传感器节点。因为事件地点lj已经不能再从Plist(lj)中挑选其他的候选移动传感器节点,所以此时si应该要跟lj匹配。
图1 事件地点聚类的例子
一旦移动传感器节点si与事件地点lj匹配以后,匹配P中的二元对(si,lo)就应该被新的二元对(si,lj)替换,lo要去找其他的移动传感器节点来与之相匹配。lo将会与其他的事件地点来竞争移动传感器节点。
3.2 |S|<|L|情况下移动传感器节点派遣算法设计
4 移动传感器节点分布式派遣算法设计
在移动传感器节点集中式派遣算法中,需要Sink节点收集移动传感器节点和事件地点的信息,这会导致传感器节点之间大量的消息传递,会使传感器节点的能耗增大,缩短整个无线传感器网络的生存寿命。为解决这一问题,我们提出一个移动传感器节点分布式派遣算法,算法是基于网格的架构[16-17],每个网格头会收集移动传感器节点和事件地点的信息,然后在局部运行集中式派遣算法。因此,计算复杂度和消息的传输量都会大大地减少。
为了减少传感器之间的消息传输量,我们要解决2个主要问题。一个是事件地点和移动传感器节点之间要如何高效地交换信息使得它们能知道彼此的信息。第2个是当事件地点寻找到附近的移动传感器节点以后,如何与其他的事件地点竞争这些移动传感器节点。为了解决上述的2个问题,我们采用基于网格的技术来实现。
为了减少消息的传输量,我们设计了一个基于网格结构的分布式移动传感器节点派遣算法,我们把这个算法称为DistLBSD(Distributed Load Balanced Sensor Dispatch Algorithm)算法。在分布式派遣算法中,目标感知区域被分割成一个个的网格,每一个网格是大小为α×α的正方形,如图2所示。对于每一个网格,我们选举一个静态传感器节点作为网格头来收集这个网格中的信息,要收集的信息包括网格中移动传感器节点的数量和位置信息以及事件地点的数量和位置信息。移动传感器节点会报告它们的位置和剩余的能量给它们所在网格的网格头。当静态传感器节点监测到事件发生时,它们也会通知它们所在网格的网格头有事件发生,我们称有事件发生的网格为事件网格。我们假设网络中所有的传感器节点都是时间同步的,时间被分割成许多轮,每一轮又进一步被分成3个阶段。
DistLBSD算法共有3个阶段。算法的第1个阶段是信息收集阶段,在这个阶段中每个网格头会收集自己所属的网格中的事件地点的信息和移动传感器节点的信息。收集完信息后,网格头会广播自己网格中存在的移动传感器节点的信息,相邻的网格头将能够知道附近网格头中的信息。算法的第2个阶段是竞争阶段,在这个阶段,事件网格的网格头会竞争附近可用的移动传感器节点,网格头会向附近可用的移动传感器节点发送INV(INVitation)消息,移动传感器节点接着会根据收集到的信息计算派遣计划。算法最后一个阶段是派遣阶段,在这个阶段移动传感器节点会按照计算得到的派遣计划访问所有的事件地点。3个阶段的具体时间要根据具体的环境情况来定。
每一个事件网格的网格头维护了一个优先列表,这个优先列表中包含所有的移动传感器节点,移动传感器节点按照它们消耗的能量排序。出于竞争的目的,每一个网格头同时维护一个界,它们会向附近的移动传感器节点发送一个携带有界的INV信息来竞争移动传感器节点。同时,每一个移动传感器节点会维护一个派遣序列SCHsi来记录它要访问的事件网格,SCHsi是一个有最大长度限制的列表,如果SCHsi的长度已经达到最大的话,那么这个移动传感器节点将不会再继续访问其他的事件网格。当一个移动传感器节点si接收到一个邀请消息(INV)时,它并不会马上对这个消息进行回复,而是在接下来的一小段时间内继续收集更多的INV消息,这个过程会持续Δt的时间,这个时间可以是几次数据包传递的往返时间。接下来,移动传感器节点si会查看收到的邀请消息,根据事件网格的界来决定竞争优胜者,把它们记录在派遣序列SCHsi中并给每一个竞争优胜者回复一个确认消息。对于竞争失败的网格,si会回复一个拒绝消息,拒绝消息中包含有si的派遣序列SCHsi还能记录的事件网格数。事件网格的网格头将会从自己的优先列表中移除那些派遣序列已经满的移动传感器节点,并试着邀请其他的移动传感器节点直到它们收到了来自移动传感器节点的确认消息或者该轮中所有的移动传感器节点都已经无法再接受邀请。
4.1 基于网格的消息交换机制
为了减少网格头在搜索其他网格里的可用的移动传感器时的消息传输量,我们提出了一种修改的grid-quorum[18]方法。具体地说是,每个网格头会发送广播(ADV)消息给同一列上的其他网格,广播消息中包含了网格中的移动传感器的数量。通过这种方式,每个网格头将会知道同一列上的所有网格中的移动传感器信息。当一个网格头想要搜索其他网格中的可用的移动传感器时,它会发送一个请求(REQ)消息给同一行上的其他网格头。明显地,由于网格的结构,必定存在一个网格头会同时接收到ADV和REQ消息。
图2 DistLBSD算法工作的例子
为了进一步减少在搜索可用移动传感器时的消息传输量,我们引入搜索长度来限制被搜索的网格数量。每个REQ消息带有2个参数β和Mgrid,其中β是搜索长度,Mgrid记录了已经找到的可用移动传感器的数量。由于负载均衡的特性,我们想尽可能多地获得可用的移动传感器。在确定的搜索长度里,所有可用的移动传感器而不是最近的一个会被参与到调度中来。初始的时候,每个REQ消息里β>0,Mgrid=0.当接受到REQ消息时,网格头会给Mgrid增加该网格所在列上的所有可用移动传感器的数量,因为通过ADV消息,它能知道同一列上所有其他网格的信息。如果β>1,网格头会把β减1,然后把REQ消息向同一行里的下一个网格传递。然而,当β=1且Mgrid的值还是零时,意味着还没有找到可用的移动传感器,此时网格头还会继续发送β=1的REQ消息给下一个网格直到至少找到一个可用移动传感器为止。图2演示了一个例子,其中在初始REQ消息里β=1。当接受到REQ消息时,(0,2)里的网格头把Mgrid的值增加了1,把β的值减少了1。由于β的值减少到了零,REQ消息不会再向左边传播了。当(2,2)的网格头收到REQ消息时,它发现β=1,Mgrid=0,此时(2,2)会继续把该REQ消息传递给(3,2)来搜索移动传感器。通过引入搜索长度,DistLBSD不但能减少消息的复杂度而且能减少来自网格头的对移动传感器的竞争。一旦网格头收集到了移动传感器和事件的信息,它就能在局部执行CentralLBSD算法。
4.2 事件网格竞争移动传感器节点的算法
事件网格竞争移动传感器节点有3个步骤:
Step 1:每一个事件网格gj首先计算每一个移动传感器节点si访问这个网格的移动代价。移动代价定义为w(si,gj)=d(si,rj)+φ(Lj),其中rj是事件网格gj的中心点,Lj是gj中的事件地点的集合。接着,gj把所有可用的移动传感器节点放入到一个优先列表Plist(gj)中并按移动代价递增排序。如果一个移动传感器节点的剩余能力不足以访问完gj,那么这个移动传感器节点就会从gj的优先列表中移除。如果gj的优先列表为空,那么gj将不会参加到这一轮的竞争中,但gj可能会参与到未来的竞争当中。
Step 2:每一个事件网格gj维护一个网格优先级pj和一个界Bj。初始时,pj是网格中所有事件的优先级的平均值,Bj=w(si,gj),其中si是gj的优先列表Plist(gj)中的第β个移动传感器节点。Plist(gj)中的每一个移动传感器节点初始时都是未被请求状态的,当在当前迭代中向某一个移动传感器节点发送一个INV邀请消息时,这个移动传感器节点就会标记为已请求状态。一个移动传感器节点si被作为候选者当前仅当si在Plist(gj)中,且si是未被请求状态并且w(si,gj)≤Bj。
Step 3:每一个事件网格gj选择优先列表Plist(gj)中的第1个候选移动传感器节点si,向si发送一个邀请消息INV(gj,pj,w(si,gj),Bj,cj,n),其中cj是Plist(gj)中满足约束w(si,gj)≤Bj的候选移动传感器节点的个数,n是gj在信息收集阶段中收集到的可用移动传感器节点的总数量。接着gj等待si的响应。如果gj收到了移动传感器节点si发送的确认消息的话,则算法终止,gj将会被si所访问。否则的话,gj应该会收到si发送的拒绝消息,这个拒绝消息中包含si的派遣序列的剩余容量。如果si的派遣序列的剩余容量为零,则gj从它的优先列表Plist(gj)中移除si,否则,gj将si标记为已请求状态,并且下面3种情况的其中之一将会被执行:
①如果gj在当前界Bj下还有候选移动传感器节点,则重复步骤3。
②如果gj在当前界Bj下没有候选移动传感器节点且Plist(gj)中还有未被请求的移动传感器节点,则gj增大它的界Bj使得Bj=w(sk,gj),其中sk是当前Plist(gj)中的第β个未被请求的移动传感器节点,重复步骤3。
③gj已经遍历到Plist(gj)的末尾。如果此时Plist(gj)为空,则算法结束,该轮中gj没有找到移动传感器节点来访问它;若Plist(gj)不为空,则把Plist(gj)中的所有移动传感器标记为未被请求状态,把网格优先级pj的值增加1,重设Bj=w(si,gj),使得si是Plist(gj)中的第β个未被请求的移动传感器节点,重复步骤3。
当gj邀请失败完Plist(gj)中所有的移动传感器节点时,情况(3)就发生了。此时,gj就进入了下一轮迭代,重新遍历一遍Plist(gj)来寻找仍有剩余容量的移动传感器节点。在接下来的叙述中,我们会发现网格优先级pj会帮助gj赢得竞争。
4.3 移动传感器节点接收竞争的条件
为了解决算法的第3个问题,每一个移动传感器节点si维护一个派遣序列SCHsi来记录它需要访问的事件网格。SCHsi的容量设置为|m/n|,其中m是事件网格的数量,n是移动传感器节点的数量,m可以在信息收集阶段来获知,n可以从收到的INV消息中获得,初始时SCHsi为空。一个移动传感器节点从不同的INV邀请消息中获得的n的值有可能不一样(差异不会太大),我们选取最大的n值来计算。移动传感器节点每隔一段Δt的时间就处理一次上个时间段内收到的INV邀请消息。对于所有有相同的网格优先级值的INV邀请消息,只有一个事件网格会被移动传感器节点接收,其他的事件网格都会被拒绝。如果移动传感器节点si没有剩余容量,那么它会发送一个拒绝消息表面它已经没有剩余容量了。否则的话,所有请求的事件网格中具有相同网格优先级的事件网格会竞争SCHsi中的一个位置。具体来说,对于2个邀请消息INV(gj,pj,w(si,gj),Bj,cj,n)和INV(gk,pk=pj,w(si,gk),Bk,ck,n),当前仅当以下一种条件成立时gj赢得竞争:(1)Bj>Bk;(2)Bj=Bk并且w(si,gj)
4.4 基于TSP的移动传感器节点派遣计划计算方法
最后,我们来讨论如何计算每一个移动传感器节点的派遣计划,使得它能以一种节能的方法来遍历整个SCHsi序列。我们提出了一个求解两次TSP问题的方法。每一个移动传感器节点si先对派遣序列SCHsi做第1次TSP求解,在第1次求解TSP问题时,我们把派遣序列SCHsi中的每一个事件网格当做一个点处理,这个点可以是一个事件网格中所有事件地点的中心点。接着,移动传感器节点si对派遣序列SCHsi中的每一个事件网格再分别做一次TSP问题的求解,用于访问这个事件网格中所有的事件地点。最后,我们合并两次TSP问题的解,构成一个最终的派遣计划。由于已经有许多求解TSP问题的启发式算法存在,所以本文就不具体展开求解TSP问题的过程。
5 仿真实验与分析
为了验证算法的正确性和设计合理性,本章使用MATLAB软件对算法进行仿真,主要是通过本文提出引入负载均衡的2种算法与单轮最优算法做比较,从不同角度来论证本文提出的算法的有效性。
5.1 仿真实验设计
实验建立在一个450 m×300 m的矩形感知区域,在这个感知区域里等概率地随机部署400个静态传感器节点和50个移动传感器节点。根据文献[19]的研究结果,设定每一个移动传感器节点初始时有3960 J(焦耳)的能量,移动时消耗的单位能量是8.27 J/m。静态传感器节点和移动传感器节点的通信半径分别是150 m和80 m,这样所有的传感器能构成一个连通的网络。
5.2 仿真结果与分析
我们先来考察不同算法的系统生命期。我们使用50个移动传感器节点来一轮一轮的访问事件地点。在每一轮中,随机选择10～15个静态传感器节点作为事件地点。我们主要观察每一轮中存活的移动传感器节点的百分比。当存活移动传感器节点的数量少于事件地点时,就采用我们提出的聚类算法先对事件地点分组。系统的生存寿命被定义为存活移动传感器节点百分比降低为0时经过的轮数。图3展示了式(1)和式(2)分别作为目标函数优化时的系统生存寿命,式(1)作为目标函数时,算法优化的目标是最小化每轮移动消耗,式(2)作为目标函数优化时,算法优化的目标是最大化剩余能量。从图3中可以看出,当考虑移动传感器节点的剩余能量时,3种算法都会有一个更长的系统生命周期。尽管单轮最优算法每一轮都会以最少的总能量消耗来派遣移动传感器节点,但是这个算法总是会得到最短的生命周期。这是因为单轮最优算法没有均衡移动传感器节点的负载,使得一些移动传感器节点过早地耗尽它们的能量。这些过早耗尽能量的移动传感器节点会加重剩余存活移动传感器节点的负担,让它们有很大的负载,令情况变得更加糟糕。本文提出的算法由于不仅尝试最优化目标函数而且均衡移动传感器节点的负载,使得算法能得到一个更长的生命周期。注意到CentralLBSD算法的性能要优于DistLBSD算法的性能,因为CentralLBSD拥有整个网络的信息。
图3 网络生存寿命的比较
尽管CentralLBSD算法拥有比DistLBSD算法要优的网络生存寿命和负载均衡效果,但是CentralLBSD算法会产生大量的消息传输量。图4演示了CentralLBSD算法和DistLBSD算法产生的数据包数量随着事件地点数量的变化而变化的图。从图中可以观察到CentralLBSD算法产生的消息传输量随着事件地点的增加而增加的非常快,而DistLBSD算法的消息传输量则基本保持不变,因为消息交换的负载分散在网格头之间。
图4 消息传输数量的比较
图5 平均能量消耗
图5比较了3种算法的平均能量消耗。由于单轮最优算法总是会找单轮的最优解,所以它会有一个最少的平均能量消耗。通过使用优先列表,本研究提出的算法的平均能量消耗会比最优解稍稍高一点。在DistLBSD算法中,搜索长度的使用会防止事件所在的网格头搜索那些距离很远的移动传感器节点,这样就使得算法的平均能量消耗比CentralLBSD算法要小。
图6比较了3种算法的能量消耗的标准差。从图中可以观察到单轮最优算法的标准差是CentralLBSD算法的两倍,说明单轮最优算法会造成移动传感器节点的负载很不均衡。DistLBSD算法的标准差要比CentralLBSD算法高,因为每个网格头只能获得部分移动传感器节点的信息。
图6 能量消耗的标准差
6 结论
本论文研究了混合无线传感器网络中如何有效派遣移动传感器节点访问事件地点的问题。针对移动传感器节点的负载均衡问题,本文首先提出了一个集中式的移动传感器节点派遣算法CentralLBSD算法。本文对移动传感器节点的派遣问题进行数学建模,并提出了一个集中式的移动传感器节点派遣算法CentralLBSD,使之可以适用于任意数量的移动传感器节点和任意数量的事件地点之间的派遣问题。为了减小网络中节点之间的消息传输量,接着又提出了一个分布式的移动传感器节点派遣算法DistLBSD。DistLBSD可以有效降低节点之间的消息传输量。仿真实验表明本文提出的2个移动传感器节点派遣算法不但能够降低节点移动的总能耗,同时保证了节点间的能耗均衡,从而延长整个网络的生存期。集中式的算法节能效果更好,但网络中的通信量较大,适用于中小规模,且配备了计算能力较强的Sink节点的网络;而分布式的算法也提供了可用的节能效果,且网间通信量较小,适用与较大型的WSN应用场景。未来的工作可以在此基础上考虑处理时间受限和网络中存在障碍物的情况,进一步提高算法的实用性,并通过实物实验进行验证。
[1] Zhang L,Shao Y,Zhu R,et al. Sensor Deployment for Full Detection on Delay Tolerant Event in Hybrid Wireless Sensor Networks[J]. Sensor Letters,2013,11(5):900-909.
[2]Ko R S. Analyzing the Redeployment Problem of Mobile Wireless Sensor Networks Via Geographic Models[J]. Wireless Communications and Mobile Computing,2013,13(2):111-129.
[3]Yan Chang,Shukui Zhang,Yang Zhang. Uncertainty-Aware Sensor Deployment Strategy in Mixed Wireless Sensor Networks[J]. International Journal of Distributed Sensor Networks. 2013,Article ID:834704.
[4]Pantazis N A,Nikolidakis S A,Vergados D D. Energy-Efficient Routing Protocols in Wireless Sensor Networks:A Survey[J]. Communications Surveys and Tutorials,IEEE,2013,15(2):551-591.
[5]Mei Y G,Lu Y H,Hu Y C,et al. Lee. Deployment Strategy for Mobile Robots with Energy and Timing Constraints[C]//Proc IEEE Int’l Conf Robotics and Automation,2005:2816-2821.
[6]李明. 基于差分算法的异构无线传感器网络多重覆盖节点调度方案[J]. 传感技术学报,2012,25(6):826-830.
[7]刘辉亚,徐建波. 无线传感器网络节点定位的移动信标节点路径规划[J]. 传感技术学报,2010,23(6):873-877.
[8]周彤,洪炳镕,朴松昊. 基于虚拟力的混合感知网节点部署[J]. 计算机研究与发展,2007,44(6):965-972.
[9]王良民,李菲,秦颖. 基于移动节点无线传感器网络覆盖洞修复方法[J]. 通信学报,2011,32(4):1-8.
[10]Akkaya K,Guneydas I,Biak A. Autonomous Actor Positioning in Wireless Sensor and Actor Networks Using Stable-Matching[J]. International Journal of Parallel,Emergent and Distributed Systems,2010,(25):439-464.
[11]Milan Lukic,Ivan Stojmenovic. Energy-Balanced Matching and Sequence Dispatch of Robots to Events:Pairwise Exchanges and Sensor Assisted Robot Coordination[C]//MASS. 2013:249-253.
[12]Verma A,Sawant H,Tan J. Selection and Navigation of Mobile Sensor Nodes Using a Sensor Network[J]. Pervasive and Mobile Computing,2006,2(1):65-84.
[13]Bläser M. A New Approximation Algorithm for the Asymmetric TSP with Triangle Inequality[J]. ACM-SIAM Symp on Discrete Algorithms,2003:638-645.
[14]Bramer M. Principles of Data Mining[M]. Springer,2013.
[15]Cormen T H,Leiserson C E,Rivest R L,et al. Introduction to Algorithms[M]. The MIT Press,2001.
[16]Li X,Santoro N,Stojmenovic I. Localized Distance-Sensitive Service Discovery in Wireless Sensor and Actor Networks[J]. IEEE Trans Comput,2009,58(9):1275-1288.
[17]Lukic M,Mezei I. Distributed Distance Sensitive Imesh Based Service Discovery in Dense Wsan[C]//Ad-Hoc,Mobile,and Wireless Networks,Ser. Lecture Notes in Computer Science. Springer Berlin/Heidelberg,2012,(7363):435-448.
[18]Wang G,Cao G,Porta T L,et al. Sensor Relocation in Mobile Sensor Networks[C]//IEEE Infocom,2005:2302-2312.
[19]Rahimi M,Shah H,Sukhatme G S,et al. Studying the Feasibility of Energy Harvesting in a Mobile Sensor Network[C]//Proc IEEE Int’l Conf Robotics and Automation,2003:19-24.
苗春雨(1978-),男,副教授,博士研究生,主要研究方向为无线传感器网络、可信计算等;
戴国勇(1983-),男,讲师,博士研究生,主要研究方向是无线传感器网络、网络安全等;
陈庆章(1956-),男,教授,博士生导师,主要研究方向是无线传感器网络、分布式处理与协同工作等。
Energy-BalancedMobileSensorsDispatchAlgorithm*
MIAOChunyu1,2,DAIGuoyong1,CHENYuzheng1,CHENQinzhang2*
(1.Department of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310014,China;2.Xingzhi College,Zhejiang Normal University,Jinhua Zhejiang 321004,China)
In a hybrid wireless sensor network,the most energy-cost operation of mobile sensors is movement. It is a challenging research topic that how to reduce the moving cost of mobile sensors while allow it completing the task. A mobile sensor dispatch algorithm that can balance the load of each mobile sensor is proposed,and it can be applied for any number of mobile sensors and event locations. When there are more mobile sensors than event locations,it translates the problem into a maximum bipartite matching problem. When there are less mobile sensors than event locations,it first clustering the event locations,then dispatching each mobile sensor to one cluster of event locations. In order to reduce the amount of message transmission between sensors,this paper further proposes a distributed algorithm. Simulation results show that the distributed algorithm can effectively reduce the amount of message transmission and the whole algorithm can efficiently extend system lifetime.
wireless sensor networks;mobile sensors dispatch;load balance;maximum match
项目来源:国家自然科学基金项目(61379023)
2014-06-11修改日期:2014-07-19
10.3969/j.issn.1004-1699.2014.09.019
TP393.17
:A
:1004-1699(2014)09-1260-09
