基于演化博弈论的无线传感网监测节点分群算法

刘保见　张效义　李青

摘要：针对大规模无线传感器网络多辐射源定位中，辐射源公共覆盖范围内监测节点能耗过高造成网络寿命降低的问题，提出一种基于演化博弈理论（EGT）的传感网监测节点分群算法。通过将最优节点集的搜索空间映射到博弈的策略组合空间，以博弈的效用函数为目标函数构建了非合作博弈模型；利用纳什均衡分析及均衡的扰动恢复过程实现目标优化；设计了分群算法以优化节点集组成相应的群参与最终的定位。以接收信号强度指示（RSSI）/信号到达时间差（TDOA）两轮定位为例，将该算法与典型的最近邻算法、基于离散粒子群优化（DPSO）的分群算法在定位精度和网络寿命方面作对比。仿真结果表明，该分群算法避免了多辐射源公共覆盖区域内节点能耗较高的问题，延长了网络寿命，同时保证了对辐射源的定位。

关键词：无线传感器网络；多辐射源定位；分群算法；演化博弈论；纳什均衡；网络寿命；定位精度

中图分类号：TP393.02

文献标志码：A

0引言

随着微机电技术与无线通信技术的迅猛发展，无线传感器网络（Wireless Sensor Network， WSN）被广泛应用于环境监测、智能家居、空间探索以及目标定位跟踪等领域[1]。特别是网络的分布式信息处理、抗毁性强、快速展开等特点，使得WSN成为辐射源定位的有效手段和方法[2-4]。与传统的单节点定位方法相比较，基于WSN的分布式辐射源定位方法具有定位精度高、廉价、可靠以及隐蔽性强等优势。网络化监测的另一优势是同时实现多辐射源定位，但是当监测区域内出现多个辐射源节点且各辐射源节点具有公共覆盖区时，如何对监测节点进行分群实现网络能耗与定位精度整体最优，同时避免多辐射源公共覆盖范围内节点能耗增加，是实现多辐射源定位的核心问题之一。

在现有的面向定位的无线传感器网络分群算法研究中，对于多辐射源定位的应用，特别是辐射源节点之间的覆盖区域存在交叠时，一个监测节点可能监测到多个辐射源的辐射信号，致使其能耗消耗过快，出现过早死亡，从而影响网络的寿命。为保证节点的能耗均衡以及尽可能地延长网络的寿命，应当尽量避免多辐射源公共覆盖区域内的节点同时服务于多个辐射源的定位。在文献[5-8]等相关文献中给出了相应的弹性神经网络算法、改进粒子群算法等来优化多辐射源定位中公共区域内的节点服务于多个辐射源定位的情况。然而，在上述方法中没有考虑参与定位节点的个数以及监测节点相对于辐射源的位置对定位精度的影响，仅简单地将参与定位的节点个数定为3个，选择距离辐射源位置较近的节点参与定位。

但是，基于多点联合定位的定位精度与监测节点的分布有密切的关系[9]，优化选取合适位置的节点组成群将有助于提高对辐射源的定位精度。文献[10]给出了一种基于离散粒子群优化（Discrete Particle Swarm Optimization， DPSO）的分群算法，虽然在最优节点集选取的过程中考虑了节点的几何分布对定位精度的影响，但是该分群算法针对的是单辐射源情况，未考虑多辐射源情况下公共区域内节点能耗较高的问题。

在WSN中，监测节点通常随机大规模地布设在监测区域内，在多辐射源个数已知的情况下，如何进行分群在避免多辐射源公共覆盖区域内节点能耗较高、延长网络寿命的同时为定位提供服务是本文所要研究问题的关键。

本文针对WSN中多辐射源公共覆盖区域内的节点能耗较高的问题，基于演化博弈论（Evolutionary Game Theory， EGT）提出了一种面向多辐射源定位的分群算法。首先，建立了问题的数学模型，并将求解的问题模型映射到博弈的模型空间；然后，利用演化博弈论方法求解出全局最优节点集；最后，对最优节点集内的节点再次利用博弈论方法进行群首选取，最终实现了面向多辐射源定位的分群算法。仿真结果表明，该方法在保证对辐射源的定位精度的同时避免了多辐射源覆盖区域内节点能耗较高的问题，延长了网络寿命。

1问题描述

在实际的应用中，监测区域内通常出现多个且移动辐射源节点的情况。多辐射源公共覆盖区域内节点能耗较高的问题也即所谓的“热点”问题，将影响网络的寿命与定位功能。如图1所示，在监测区域内出现两个辐射源节点[T1，T2]，节点集{S1，S2，S3，S4}为两辐射源节点公共覆盖区域内的节点，为避免公共覆盖区域内节点能耗较快，需确定公共区域内的节点参与到哪个辐射源的监测。为此，本文提出了一种面向多辐射源定位的分群算法，以在保证网络低能耗、高精度定位的同时避免公共覆盖区域内的“热点”问题。

1.2群定位精度模型

监测节点的几何分布对目标辐射源定位精度的影响通常采用几何精度稀释因子（Geometry Dilution Of Precision， GDOP）来衡量。GDOP值越小，定位精度越高。依据文献[11]中给出的GDOP表达式，将监测节点位置对定位精度的影响转化为监测节点相对于辐射源节点角度之间的关系，并对表达式进行进一步的推导，给出了影响GDOP值（记为f2）的主要因素。

1.3网络能耗均衡模型

在WSN中，要延长网络寿命，减少网络能耗只是其中的一方面，另一方面则是保证网络能耗的均衡，也即避免网络中出现“热点”问题。为保证网络能耗的均衡，这里将以节点i的剩余能量Eni作为能耗均衡的指标。同时，采用Sigmoid函数将节点能耗均衡指标映射到区间[0，0.5]中，其表达式如式（6）所示：

2基于演化博弈论的节点集优化算法

博弈论是一种研究决策主体的行为发生直接相互作用时的决策以及这种决策的均衡问题的理论[12]。即“理性的”个体在其他参与者策略选定的情况下，如何使得自己的利益最大化的最优反映。博弈论通常包含以下几个要素：参与者、行动、信息、策略、效用、结果和均衡，其中参与者、策略和效用是一个博弈所必需的要素。

演化博弈论是一种动态的博弈过程，其思想来源于自然界生物进化的理论，博弈主体按照一定的规则进行策略的调整。“有限理性”的参与人在博弈的过程中不断学习，选择自己的最优策略。在分析判断博弈方的选择和博弈结果的方法中通常采用纳什均衡分析。

针对第一章中问题的描述，面向多辐射源定位的分群算法本质上是在避免公共区域内节点能耗较高情况下的组合优化问题，而博弈论主要用来解决博弈各方存在利益冲突的理论。如果将最优节点集的搜索空间映射为博弈的策略组合空间，将目标函数映射为博弈的效用函数，则优化问题的求解过程就变换为在博弈空间的上下文中，博弈主体寻求最优效用的策略组合的演化博弈过程。

3面向多辐射源定位的分群算法

在给定各辐射源辐射信号体制不同的情形下，本文提出的分群算法中充分考虑了监测节点的分布对定位精度的影响，使得分群在满足网络低能耗的同时为定位提供服务。为进一步提高网络能量的利用率，定义该分群算法为基于事件触发的分群过程，也即只有在监测区域内出现辐射源节点时才会触发相应的分群。同时，为保证节点有充足的时间进行定位，本文约定完成一次精确定位为一轮（如图3所示）。在每轮定位过程中，主要包含临时中心选取、接收信号强度指示（Received Signal Strength Indication， RSSI）粗定位、面向定位的分群和TDOA定位四个主要部分。其中，面向定位的分群又分为：最优节点集的选取、群首选取以及数据传输。

当监测区域内出现辐射源节点时，则触发相应的分群过程。为避免网络中数据远距离传输所带来的能耗增加的问题，在每轮一开始，辐射源覆盖范围内的监测节点依据剩余能量最大准则选举出临时中心节点。各监测节点将监测到的辐射源信息以及自身的坐标信息发送给临时中心节点；临时中心节点利用数据关联算法[13]对获得的辐射源数据进行聚类分析从而得出辐射源的个数，并对具有不同信号特征的辐射源节点分别进行标记，进而将监测节点与相应的辐射源节点进行关联。

由于监测节点相对于辐射源的分布影响最终的定位精度，为便于面向定位的分群过程中最优节点集的选取，本文算法需要知道辐射源的粗略位置。本文中采用了能耗较低的RSSI定位方法。辐射源覆盖范围内的监测节点将其坐标、监测到的辐射源的数据以及自身的剩余能量发送给临时中心节点，临时中心节点在进行完数据聚合后，执行RSSI定位解算算法获得各辐射源粗略的位置。

3.1最优节点集选取

在获得各辐射源的粗略位置后，临时中心节点利用第2章中基于演化博弈论的方法进行最优节点集的选取。博弈的主体为辐射源覆盖范围内的监测节点；临时中心节点利用前期数据关联的结果，获得每个监测节点所监测到的辐射源节点集，也即是各个博弈主体的策略集；效用函数部分则综合考虑网络能耗、定位精度以及能耗均衡等因素。在获得最优节点集后，对参与同一辐射源节点定位的最优节点集，利用数据聚合过程中辐射源信号特征的不同进行相应的标记。

3.2群首选取

在群首选取阶段，主要是将最优节点集选取阶段所选取的具有相同特征标识的最优节点集组成同一个群参与最终的定位。由于在WSN中，计算所消耗的能量远远小于节点之间通信所消耗的能量。为此，对群首节点的选取，同样采用博弈论的方法进行博弈。博弈的主体为参与同一辐射源定位的最优节点集。各博弈主体的策略集为：成为群首节点或成为成员节点，分别用1、0来表示；效用函数则综合考虑了节点的剩余能量、到临时中心节点的距离以及群能耗等因素。具体定义如式（10）：

其中：C为一常数；Eni表示节点i的剩余能量；Enave表示最优节点集内节点的平均剩余能量；dtoCenter（i）表示节点i到临时中心节点的距离；dmax_toCenter表示最优节点集中的节点到临时中心节点的最大距离；di， j表示节点i到节点j之间的距离；

合理情况是指相应的策略集中仅有一个节点为群首，不合理情况指相应的策略集中没有或有多个节点为群首节点。

为简化计算，这里利用节点之间的距离来代替两节点之间通信所消耗的能量。

在确定各节点集中的群首后，临时中心节点将各监测节点的坐标与相应的分群结果信息（包含是否为群首以及参与哪类特征辐射源的定位）组合为广播消息，并将该消息在辐射源覆盖范围内进行广播。监测节点在接收到临时中心节点所广播的消息后，通过比对自身的坐标信息来获得相应分群结果信息，从而确定自己是否参与定位、参与到哪类辐射源信号特征的定位以及是否为群首。最终，使得具有同一特征标记的最优节点集组成一个群参与相应特征信息辐射源节点的定位。

3.3数据传输及TDOA定位

在完成相应的分群后，则对相应的辐射源进行监测。各监测节点将监测到的辐射源的信号与分群过程中给出的信号的特征相比较，若相同，则接收相应的辐射源信号，否则丢弃相应的辐射源信号。这样避免了多辐射源覆盖范围内的节点服务于多个辐射源而导致能耗消耗过快的问题。各群首节点将监测到的辐射源的信号在群内进行广播，成员节点在接收到相应信息后与自己监测到的辐射源信号相比较进行相应的时差估计，并将估计的结果发送给相应的群首；群首在得到相应的时差估计值后执行Chan氏算法进行相应的定位解算，最终确定辐射源的位置。各群首节点将TDOA定位的辐射源位置信息发送给临时中心节点；临时中心节点在接收到所有辐射源的位置信息后，进行相应的数据压缩并将压缩的结果发送给Sink节点。具体的路由协议可以采用AODV（Ad hoc On-demand Distance Vector routing）、Dijkstra等典型的无线路由协议。

4仿真分析

在Matlab 7.0环境下对本文提出的算法进行了仿真，仿真中设定监测区域为100m×100m，在监测区域内随机布设150个监测节点，Sink节点的位置在监测区域内随机初始化，为简化数据关联部分的工作，监测区域内辐射源的个数已知。为均衡目标函数中各因素的权重，给定相应定位精度、网络能耗、能耗均衡的权值系数分别为[0.3，0.3，0.4]。其他详细的参数如表1所示。

在监测区域内布设两个辐射源节点，并且两辐射源节点公共覆盖范围存在多个监测节点情况下，运行本文提出的分群算法，分群结果如图4所示。其中，[s1，s2，s3]所组成的群用于监测辐射源T1；[s4，s5，s6]所组成的群用于监测辐射源T2。从分群结果上可以看出，本文提出的算法避免了公共覆盖区域内的监测节点服务于多个辐射源。

为比较算法的性能，本文主要从网络能耗和定位精度两个方面，将本文提出的算法与经典的最近邻法[14]（选择距离目标最近的3个节点组成群参与对辐射源的定位）和基于离散粒子群优化（Discrete Particle Swarm Optimization， DPSO）的分群算法作对比。

相应的性能指标使用网络寿命，即网络从开始运行到第一个节点死亡时网络所运行的轮数。

4.1网络寿命

首先针对监测区域内布设两个辐射源节点的情况对算法网络寿命进行仿真；其次，在给定场景下仿真不同辐射源个数对三种算法网络寿命的影响。

仿真结果分别如图5和图6所示。

由图5可以看出，本文提出的算法相比基于DPSO的分群算法、最近邻算法延长了网络的寿命。一方面是由于在最优节点集选取的过程中，本文算法是从整体能耗及定位精度的角度选取最优位置的节点参与定位，同时避免了多辐射源公共覆盖区域内一个监测节点服务于多个辐射源节点的情况，减少了其能耗，从而延长了网络寿命；另一方面，在群首选取的过程中，不仅考虑了节点的剩余能量、距离临时中心节点的远近，还考虑了群的能耗，进一步减少了网络能耗。最近邻算法由于没有考虑能耗等因素，因此，同等条件下其网络寿命较短；同时，由于没有考虑网络的能耗均衡，其第一个节点死亡到最后无法定位之间的时间间隔较长。

由图6可以看出，随着辐射源个数的增加，本文提出的分群算法与基于DPSO的分群算法的网络寿命均在逐渐减小。这是由于在给定场景下，辐射源节点个数的增加降低了网络能耗的均衡性，从而减少了网络寿命。而最近邻算法在分群的过程中没有考虑网络的能耗均衡，因此，辐射源节点个数的增加对该算法下的网络寿命影响不大。同时可以看出在辐射源个数相同的情况下，本文提出的分群算法在延长网络寿命方面要优于基于DPSO的分群算法和最近邻算法。这也进一步验证了该算法避免了多辐射源公共覆盖区域内节点能耗较高的问题，延长了网络寿命。

4.2定位精度

首先针对监测区域内布设两个辐射源节点的情况分别对三种算法的定位精度进行20轮仿真，每一轮中进行100次仿真并将仿真的结果求取平均值作为该轮的仿真值；其次，在给定场景下仿真不同辐射源个数对算法定位精度的影响。仿真结果分别如图7和图8所示。

由图7可以看出基于DPSO的分群算法的平均GDOP值小于本文提出的分群算法，也即基于DPSO的分群算法的定位精度要略优于本文提出的算法。

然而，基于DPSO的分群算法其定位精度值波动较大，而本文提出的分群算法的定位精度值基本维持在稳定值。这是由于本文提出的算法在优化节点选取的过程中考虑了多辐射源覆盖区域内节点能耗较高的问题，从整体能耗以及定位精度均衡的角度选取最优面向定位的节点集；而基于DPSO优化的面向定位的分群算法则是对单个辐射源分别进行优化，并且在最优节点选取的过程中并未考虑公共区域内节点能耗较高的问题。最近邻算法由于既没有考虑公共区域内的节点能耗较高的问题也没考虑节点的位置对定位精度的影响，因此，其定位精度要差于上述两种算法。

由图8可以看出随着辐射源个数的增加，平均GDOP值都在增加，也即对辐射源的平均定位精度在逐渐降低。这是由于给定监测节点布设场景的情况下，辐射源个数的增加等价于辐射源个数不变的情况下监测节点个数的减少，因此，限制了最优节点集的选取，最终导致平均定位精度的降低。同时，可以看出在相同辐射源个数的情况下，本文提出的算法在定位精度方面略差于基于DPSO的分群算法而优于最近邻算法，进一步验证了本文提出的算法是从整体能耗以及定位精度的角度选取面向定位的最优节点集。因此，本文提出的算法在牺牲部分群定位精度的同时延长了网络寿命。

5结语

在节点能耗受限且随机大规模布设的WSN中，给出了一种面向多辐射源定位的分群算法。与经典的最近邻算法、基于DPSO优化的面向定位的分群算法相比，基于演化博弈论的分群算法在牺牲部分群定位精度的同时避免了多辐射源公共覆盖区域内节点服务与多个辐射源的情况，从而延长了网络寿命。

虽然本文算法在避免多辐射源公共覆盖区域内节点能耗较高以及延长网络寿命方面展现了较好的性能，但是，该算法仅考虑了群内单跳通信的情形，为进一步延长网络的寿命，下一步的工作将考虑群内多跳通信的情形并对算法作出相应的改进，使其适应于更广的应用场合。

参考文献：

[1]KONG J-I， KIM J-W， EOM D-S. Energy-aware distributed clustering algorithm for improving network performance in WSNs [J]. International Journal of Distributed Sensor Networks， 2014（5）： 1-10.

[2]PRABHAVATHI M， RAJESHWARI R. Cluster-based mobility management for target tracking in mobile sensor networks [C]// ICoAC 2011： Proceedings of the 2011 Third International Conference on Advanced Computing. Piscataway， NJ： IEEE， 2011：198-203.

[3]HOANG H G， VO B T. Sensor management for multi-target tracking via multi-Bernoulli filtering [J]. Automatica， 2014， 50（4）： 1135-1142.

[4]ARMAGHANI F R， GONDAL I， KAMRUZZAMAN J， et al. Sensor selection for tracking multiple groups of targets [J]. Journal of Network and Computer Applications， 2014， 46： 36-47.

[5]刘美，黄道平.WSN中传感器节点的弹性神经网络任务分配方法[J].华南理工大学学报（自然科学版），2010，38（6）：66-72. （LIU M， HUANG D P. Task allocation method of sensor nodes based on MEMSOM neural network in WSN[J]. Journal of South China University of Technology （Natural Science Edition）， 2010， 38（6）：66-72.）

[6]刘梅，权太范，姚天宾，等.多传感器多目标无源定位跟踪算法研究[J].电子学报，2006，34（6）：991-995. （LIU M， QUAN T F， YAO T B， et al. Multi-sensor multi-target passive locating and tracking[J]. Acta Electronica Sinica， 2006， 34（6）： 991-995.）

[7]LIU J， REN X， MA H. Adaptive swarm optimization for locating and tracking multiple targets [J]. Applied Soft Computing， 2012， 12（11）： 3656-3670.

[8]THIDA M， ENG H-L， MONEKOSSO D N， et al. A particle swarm optimisation algorithm with interactive swarms for tracking multiple targets [J]. Applied Soft Computing， 2013， 13（6）： 3106-3117.

[9]LEVANON N. Lowest GDOP in 2-D scenarios [J]. IEE Proceedings — Radar， Sonar and Navigation， 2000， 147（3）： 149-155.

[10]LIU B， LI Q， ZHANG X. DPSO based clustering algorithm for location in wireless sensor networks [J]. International Journal of Computer and Communication Engineering. 2016， 5（4）： 260-268.

[11]QUAN Q. Low bounds of the GDOP in absolute-range based 2-D wireless location systems [C]// ICIDT 2012： Proceedings of the 2012 8th International Conference on Information Science and Digital Content Technology. Piscataway， NJ： IEEE， 2012： 135-138.

[12]赵昕，张新.基于博弈论的无线传感器网络簇间路由选择算法[J].计算机应用，2013，33（7）：1813-1815. （ZHAO X， ZHANG X. Inter-cluster routing algorithm in wireless sensor network based on game theory[J]. Journal of Computer Applications， 2013， 33（7）： 1477-1480.）

[13]谢宇，程维明.一种基于类间距阈值的模糊聚类算法[J].计算机应用与软件，2008，25（9）：248-249. （XIE Y， CHENG W M. A fuzzy clustering algorithm based on the threshold of clusters interval [J]. Computer Applications & Software， 2008， 25（9）： 248-249.）

[14]TSENG Y-C， KUO S-P， LEE H-W， et al. Location tracking in a wireless sensor network by mobile Agents and its data fusion strategies [J]. The Computer Journal， 2004， 47（4）： 448-460.http：//comjnl.oxfordjournals.org/content/47/4/448.abstract

IPSN 03： Proceedings of the 2nd International Conference on Information Processing in Sensor Networks， LNCS 2634. Berlin： Springer-Verlag， 2003： 625-641.