无线传感器/执行器网络中的定向简单竞拍聚合协议

摘要：在无线传感器/执行器网络（WSAN）中，移动执行器（actor）节点之间需要通过协商进行任务分配来响应产生的服务请求，其目标是尽可能减少协商时的通信开销和对事件的响应时间现有的解决方案中，基于市场竞拍的分布式简单竞拍聚合协议（SAAP）比较适合资源受限的WSAN网络在SAAP的基础上提出了一种定向的竞拍聚合协议DSAAP，该协议根据方向信息对下一跳子节点进行筛选，同时限制回传的信息，以减少竞拍过程中的消息转发通过实验与现有的SAAP进行比较，发现该协议在最优节点发现率和选出节点与最优节点距离比这两个参数性能不降低的前提下降低了通信开销

关键词：无线传感器/执行器网络； actor协商； 竞拍； 简单竞拍聚合协议； 定向

中图分类号：TP393 文献标志码：A

0引言

无线传感器/执行器网络（Wireless Sensor and Actor Network，WSAN）由大量的传感器节点（sensor）和少量的移动执行器节点（actor）组成，它们通过无线网络互联，用于感知现实世界，处理感知到的数据，并在事件发生时（如火灾）进行决策和行动[1]在WSAN中，sensor节点会向actor汇报事件，之后由actor节点为发现的事件提供相应的服务假设一个actor节点收到了服务请求，此时它需要与其余actor节点在协商之后进行任务分配，以选出响应时间最短的最优节点来响应sensor发现的事件通常，节点是由电池来提供能源的[2]，而通过无线信道传输数据会消耗大量的能源，因此，为了提高网络的寿命，应尽量减少actor节点之间的通信开销，这是在actor协商和任务分配过程中需重点考虑的因素

针对多个actor之间的协商和任务分配的决策问题，现有的文献提出了一些方案，主要分为集中式和分布式的集中式算法[3-4]是指由一个中心节点收集来自所有节点的信息然后进行决策[5]，此方案的好处是理论上可以选出最优节点[2]，但缺点也很明显：首先由于需要获知全网的信息进行决策，所以通信开销会非常大；其次中心节点的通信和计算负担过重，使整个网络的容错性很差

而分布式的解决方案[6-8]仅利用局部节点的信息来进行决策，其产生的消息包数量将大大降低，且整个网络的稳定性也会提高，但缺点是选出的可能是次优解在文献[6]中提出了kSAP（khop Simple Auction Protocol）、kSAAP（khop Simple Auction Aggregation Protocol）和kAAP（khop Auction Aggregation Protocol）其中：kSAP是一种简单的泛洪算法；kSAAP通过构造一棵响应树来获得局部k跳邻居的信息，以供决策；kAAP则是在kSAAP的基础上，在每次选择子节点时增加k跳邻居的信息来减少构造响应树的代价

由于WSAN网络中节点资源的有限性，一般认为分布式方案比较适合actor节点之间的协商和任务分配，而现有的算法中kSAAP的设计是比较合理的因此本文在kSAAP的基础上提出了一种定向简单竞拍聚合协议（Directional Simple Auction Aggregation Protocol，DSAAP），其主要目标是在其余性能不降低的前提下进一步减少通信开销

1竞拍问题与简单竞拍聚合协议

1.1竞拍问题

本文采用文献[6]中的单事件发现模型，假设同一时间只发现了一个事件且只有单个actor收到服务请求此时可能由于某些原因，收到服务请求的actor节点并不一定是距离事件最近的节点，如图1所示状况

在图1中，由于sensor空洞的存在，发现事件的sensor节点无法把事件汇报给最近的actor节点4，而此时收到服务请求的节点2需要通过和其他节点的通信来找出是否有更合适的服务节点对于多个节点之间的协商，文献[6]中采用的是一种基于市场[9]的竞拍机制，整个过程和市场竞拍非常类似，首先由收到sensor汇报的actor节点（被称为采集节点（collector））把服务请求（包括事件的相关信息如位置）转发给网络中的其余actor节点，然后其余节点会返回一个为事件提供服务的代价（cost），文献[6]中代价的评价指标是节点和事件发生地的距离，距离越小则响应时间越短，服务代价越小此代价可以看作是一种投标（bid），采集节点会根据这些出价来选出最优的actor为事件服务kSAAP就是基于这种竞拍策略，下面将简单地说明一下kSAAP

1.2kSAAP

SAAP的全称是简单竞拍聚合协议，k则用来限制寻找最优节点的跳数范围此协议通过构造响应树来返回每个节点的服务代价，整个协议可分为树的扩张和收缩阶段在树的扩张阶段，首先由采集节点发起树的扩张，如图2所示，actor节点1先向1跳邻居节点转发服务请求，然后1跳邻居再向2跳邻居转发请求，直到转发给k跳邻居，一棵以节点1为根的响应树就构造完成了

在树的收缩阶段，由树的叶节点发起响应过程，如图2所示，节点8、9、10会向其父节点7回传自身的服务代价，之后节点7和自身的现有代价作比较，从中选择出最小的代价再次回传给上一级父节点2，如此层层返回，直到所有代价都返回给根节点后终止，此时所有信息都集中到了采集节点

最终根节点1会根据收到的代价来选择自己的k跳邻居节点中最优的服务节点（也可能就是节点1自身）去执行任务，然后把消息路由给该节点

DSAAP分别在树的扩张和收缩阶段对SAAP加以改进，主要是通过在选择子节点以及子节点在回传数据时进行筛选来减少数据包的传递，从而减少通信开销

2.1扩张阶段的改进

在树的扩张阶段，父节点会向所有1跳邻居转发服务请求，但是这种转发在某些情况下是没有必要的比如在图2中，actor节点1没必要向actor节点4、5、6转发数据，因为从全局图上可以看出4、5、6节点明显是远离事件位置的，对于这种情况完全可以不用向下生成下一级子树从局部算法的角度考虑，每个节点只能通过自身的信息来判断是否应该把服务请求转发给下一跳邻居节点，因此不能进行过于复杂的计算筛选子节点

综合以上分析考虑，节点的方向信息是本地信息中比较有参考价值的选择因素，可以选择只向一定方向的子节点转发数据这里先给出子节点和父节点方向角的定义，如图3所示，首先以父节点i和事件e的连线为X轴建立直角坐标系，然后在此基础上定义子节点和父节点的方向角

通过观察，可以看出处于一、四象限的子节点才有可能距离事件更近，所以定义一、四象限子节点的方向角为正方向角，即角度小于90°；而二、三象限子节点的方向角为负方向角，即角度大于90°

对于父节点来说每次转发服务请求时，只需向方向角为正的子节点转发数据包即可，如此可以在树的扩张阶段减少数据包转发量的同时不影响最优节点的发现，本文称之为定向转发算法描述如下：

2.2收缩阶段的改进

收缩阶段是响应树建成之后，子节点向父节点回传信息的阶段，本文的改进思路是只有在服务代价小于已知父节点代价时，子节点才会回传信息本文称之为选择性响应，其算法描述如下：

算法2选择性响应

程序前

for every child a（i）

if a（i）.mincost

transmit its mincost to father

end if

end for

程序后

算法2中每次子节点在选择返回数据包时会先将自己所知的最小代价和父节点距事件的距离进行比较，只有在代价更小的情况下，子节点才会把最小代价发送给父节点，如此可进一步减少通信开销

关于父节点到事件的距离，可由子节点通过父节点和事件的位置来计算（父节点的位置可通过1跳邻居信息获得，而转发的服务请求已经包含了事件的位置），如此在扩张阶段也不会增加转发消息的长度

2.3算法分析

在树的扩张阶段，假设传递单个数据包所需的时间为ST，actor网络的平均节点度为N（即每个actor的平均1跳邻居数），转发跳数限制为k，那么生成整棵树所花费的时间T（N）=ST×Nk，可见生成树算法的时间复杂度是关于平均节点度N的指数级，而采用了定向转发的方式之后，算法的输入规模减少了一半，在最理想的情况下，算法的运算时间可以减少为原来的1/2k，这可以极大地减少数据包的传递数

而选择性的响应机制也可在树的收缩阶段减少通信开销，具体情况和整个actor网络的节点分布有关

可见以上两步改进可以有效减少通信开销

3算法仿真与性能分析

本文采用Matlab进行仿真，比较了DSAAP和SAAP的性能仿真的场景是在一个1000m×1000m的监测区域内随机部署一定数量的actor和sensor节点，且随机产生一个事件，然后由采集节点发起竞拍，竞拍范围限制在5跳邻居之内对于采集节点的选取，使用的是文献[6]中的选取方法，假设di为actor节点ai到事件的距离，令D=1d1+1d2+…+1dn，则节点ai被选为采集节点的概率为1Ddi实验参数如表1所示，同时会使用100次实验取平均值的方法来获取性能数据

从图4可以看出，在最优节点发现率方面，两个协议的性能是相当的，这也符合前文的分析，说明在定向选择子节点之后并不会减少发现最优节点的概率

图5和图6表明DSAAP相对于SAAP具有更小的通信开销，尤其是随着网络规模的扩大和节点度的增加更能体现DSAAP的性能优势DSAAP在树的扩张阶段和收缩阶段均能有效地减少消息包的转发，这达到了当初设计协议的目标

图7给出了选出节点和最优节点的距离比，这一性能指标表明了协议在最坏情况下的效率，可以看出两者是相当的但是节点个数增多之后，这一比例明显增大，说明对于现有规模的网络，只在5跳邻居之内寻找最优节点的结果不够理想

综合来看，DSAAP相对于SAAP确实在最优节点寻找性能保持不变的前提下大大减少了通信开销，因此具有更好的综合性能

4结语

本文针对WSAN中actor节点的协商和任务分配问题，提出了一种定向竞拍聚合协议DSAAP，此协议在SAAP的基础上通过定向选择子节点以及限制信息的回传，使得在寻找最优服务节点性能不变的前提下，实现了通信开销的降低理论分析和仿真实验结果表明，相对于SAAP，DSAAP在通信开销上有比较大的优势，有利于延长网络的寿命

本文的局限性在于只考虑了最简单的单事件发现模型，而没有考虑更复杂的情况，且只是简单比较了消息包的个数，没有引入较可靠的能量模型来比较具体的通信能耗因此下一步的工作是设计一种适合于多事件的任务分配协议，同时在比较通信开销时引入合适的能量模型

参考文献：

[1]MEZEI I， LUKIC M， VELJKO M， et al. Auctions and iMesh based task assignment in wireless sensor and actuator networks[J]. Computer Communications， 2013，36（9）：979-987.

[2]LUKIC M， JANICIJEVIC N， MEZEI I. Improved decision making in WSN based on localized auctions and fuzzy logic [C]// TELFOR 2011： Proceedings of the 19th Telecommunications Forum. Piscataway： IEEE， 2011：238-241.

[3]ATAY N， BAYAZIT B. Mixedinteger linear programming solution to multirobot task allocation problem， WUCSE200654 [R]. Sent Louis： Washington University， 2009.

[4]SHAH K， MENG Y. Communicationefficient dynamic task scheduling for heterogeneous multirobot systems [C]// CIRA2007： Proceedings of the 2007 International Symposium on Computational Intelligence in Robotics and Automation. Piscataway： IEEE， 2007：230-235.

[5]MEZEI I， JANICIJEVIC N. Decision making based on localized auctions in wireless sensor networks[C]// EUROCON2011： Proceedings of the 2011 International Conference on Computer as a Tool. Piscataway： IEEE， 2011：1-4.

[6]MEZEI I， MALBASA V， STOJMENOVIC I. Auction aggregation protocols for wireless robotrobot coordination [C]// ADHOCNOW 2009： Proceedings of the 8th International Conference on AdHoc， Mobile and Wireless Networks， LNCS 5793. Berlin： SpringerVerlag， 2009： 180-193.

[7]MELODIA T， POMPILI D， GUNGOR V C， et al. Communication and coordination in wireless sensor and actor networks[J]. IEEE Transactions on Mobile Computing，2007，6（10）， 1116-1129 .

[8]SUJIT P B， SINHA A， GHOSE D. Team， game， and negotiation based intelligent autonomous UAV task allocation for wide area applications[J]. Innovations in Intelligent Machines， 2007，70（1）：39-75.

[9]TOVEY C， LAGOUDAKIS M G， JAIN S， et al. The generation of bidding rules for auctionbased robot coordination [C]// Proceedings from the 2005 International Workshop on MultiRobot Systems. Berlin： SpringerVerlag， 2005，3： 3-14.

[10]周杰，陈靖峰，菊池久和.3三维空间MIMO信道接收天线阵列互耦效应及系统容量分析[J].通信学报，2012，33（6）：1-10.

[11]AKYILDIZ I F， KASIMOGLU I H. Wireless sensor and actor networks： research challenges[J]. Ad Hoc Networks， 2004， 2（4）：351-367.

[12]MALBASA V， MEZEI I， STOJMENOVIC I. Robot to robot： communication aspects of coordination in robot wireless networks [J]. IEEE Robotics and Automation Magazine， 2010，17（4）： 63-69.

[13]WALSH W E， WELLMAN M P. A market protocol for decentralized task allocation [C]// ICMAS 98： Proceedings of the Third International Conference on Multi Agent Systems. Piscataway： IEEE， 1998： 325-332.

[14]MICHAEL N， ZAVLANOS M M， KUMAR V， et al. Distributed multirobot task assignment and formation control [C]// ICRA 2008： Proceedings of the 2008 IEEE International Conference on Robotics and Automation. Piscataway： IEEE， 2008：128-133.

[15]MEZEI I， MALBASA V， STOJMENOVIC I. Greedy extension of localized auction based protocols for wireless robotrobot coordination[C]// SISY 09： Proceedings of the 7th International Symposium on Intelligent Systems and Informatics. Piscataway： IEEE， 2009： 53-57.