基于博弈理论无线传感网覆盖空洞修复算法

段鸿轩，李跃新

(1.东北石油大学 计算机系，黑龙江 大庆 163318；2.湖北大学 计算机与信息工程学院，湖北 武汉430064)

0 引 言

在无线传感网络中节点失效将会导致覆盖空洞(cove-rage holes，CH)，并且降低网络可靠性和完整性[1-4]。目前已研究出各种网络修复和拓扑控制(topology control，TC)方案用于降低节点失效的不良影响，比如节点迁移、功率调整以及聚类方法[5,6]。

近期，研究人员提出了一种混合拓扑控制方案[7,8]，该方案使移动无线传感网能够调整其位置和传送功率以修改或者维持位置最佳网络覆盖，在修复覆盖空洞中，节点调整对于降低能源需求至关重要。因此，网络寿命与恢复可以得到改善。一般来说，混合拓扑控制需要集中协调，以便跟踪拓扑变化。然而，由于覆盖空洞随机出现的特性，多数情况下并不是都可以获得覆盖空洞精确的时间和区域信息。

实际上，分布式拓扑控制是非常有价值的[7,8]，在该控制策略中对于非相邻节点，节点几乎一无所知。在网络出现覆盖空洞的情况下，每个幸存节点能够独立自发反应。每一个节点测量周围未覆盖区域，与相邻节点相互作用，并且采取分布式节能行动，延伸剩余幸存网络的覆盖以取代覆盖空洞。这种方法的潜在益处在于节点可以优化它们自己的能源使用，同时也有助于网络的整体寿命。由于在每一个独立传感器节点无法获得整体网络的全局视图，很难保障这种分布式方法的收敛性。

因此，我们提出一种基于博弈理论的分布式算法以缓解覆盖空洞，该方法使节点以不对等的、分散化的方式做出混合拓扑控制决策。基于博弈理论观念[9,10]，该方法可以结合不同拓扑方案，比如迁移和传送功率控制。我们用公式表示了新的势博弈，其中节点可以自主有效地决定适当拓扑控制行为(也就是物理移动或者调整功率)。由于决策基于节点状态以及从相邻节点收集来的信息，该覆盖空洞算法能够解决实时反应和覆盖需求，尤其是对于部署在恶劣环境中并且没有合适集中控制的网络。提出的博弈理论混合拓扑控制算法，延长了移动传感网络寿命。该算法容许每个传感器改变其位置和传感覆盖区域以节能有效地填补网络传感覆盖空隙。分析验证了该拓扑控制算法是约束的势博弈。综合仿真与对比研究结果表明，所提算法在连续随机覆盖空洞情况下有效改善了网络弹性。

1 系统模型

我们用Ei表示节点有限能量，i∈V。每一个节点通过GPS或者一些其它定位方法知道自己的位置。传感节点i相邻节点的集合表示如下

(1)

覆盖空洞k可以看成是一个圆的半径rHolek以(xHolek,yHolek)为中心。这个圆代表节点在该位置发生故障的事件，可能是由于物理性损伤造成的。

通过结合不同中心和半径的多种覆盖空洞，任何复杂的空洞(凸或非凸形状)都可以轻易计算得出，部署节点分类为损坏节点(D-nodes)和未损坏节点(U-nodes)[11]。损坏节点为失效节点的集合，存在于损坏区域。未损坏节点会直接或间接受到影响。我们假设如果在其范围内存在至少一个损坏节点时，未损坏节点均能够独立检测损坏事件。

2 提出的分布式修复算法

在这部分中，本文提出利用博弈理论方法修复覆盖空洞。该方法证明为势博弈，并且具有整体收敛性和稳定性。

2.1 博弈问题表述

在这个问题中，传感器允许同时与另外一个传感器彼此相互作用，将其覆盖区域扩到最大限度。每一个传感器基于其对局部网络的了解、环境和其它玩家的行为预测，力图最大化其实用功能。双向互动可以建模为一个博弈，其中传感器为参与者，每次步骤t，博弈重复。在步骤t>0，每个传感器i∈V选择一个行动si∈Ai以最大化其期望效用。Ai为节点i可以采取的行动集合。每个参与者的效用不仅仅取决于行动，还取决于其它所有参与者的行动。

ui(si,s-i)=w1×P(si,s-i)-w2×C(si)

(2)

式中：P(si,s-i)和C(si)分别代表策略si在节点i的效益和成本。w1和w2分别代表与效益和成本相关联的权重，用于平衡这两个方面以及调整博弈速率。所有参与者改变策略的动机可以通过一个单一整体函数表示，我们称之为势函数。

效用函数或者支付函数确定一个节点在覆盖一个区域时候收获多少收益以及付出多少成本。收益必须足够高才能有助于传感器对于覆盖空洞的修复，成本也必须足以避免可能发生的多余运作。为了最大化网络传感覆盖，每一个节点旨在减少与其相邻节点的重叠传感覆盖范围。为此，我们定义节点i收益为P(si,s-i)，表示只由该节点覆盖的区域，如图1所示，公式如下

(3)

图1 传感器节点i收益

成本的两种类型均为能源消耗形式，皆考虑在内。其中一种对应节点传感功率变化，通过Cp(si)表示；另一种对应节点位置变化，通过CT(si)表示。

节点i传感功率变化的成本可以通过如下公式得知

(4)

式中：T为两个连续覆盖空洞之间的预期间隔持续时间；|·|代表绝对操作；c1为约束常数，是为了阻止网络不必要的功率频繁变化。注意，这里指数函数是用于定义成本以抑制传感器传感范围过度变化。这是因为成本增长远远快于传感范围增加。另外，还需要注意，在Δpi<0的情况下，成本取得负值并变成收益，这会激励节点四处移动以降低过高的传感功率，从而达到延长节点寿命的效果。

节点位置变化成本通过如下公式表示

(5)

式中：Δai表示节点i移动距离；常数c2用于预防不必要的频繁小移动。指数函数同时也用于定义传感器位置变化的成本以阻止传感器移动过远。

因此，总成本可以通过如下公式求得

C(si)=k1CP(si)+k2CT(si)

(6)

式中：k1为传感功率变化成本权重系数；k2为位置变化成本权重系数。注意的是节点i成本只取决于其策略si，并且与其它节点策略s-i无关，所以

C(si,s-i)=C(si)

(7)

定理1 定义覆盖博弈是一个约束势博弈，通过如下势函数表示

φ(s)=w1S(s)-w2C(s)

(8)

式中：s={si,s-i}表示所有节点策略的集合；S(·)表示传感器整体覆盖范围。

(9)

参考式(3)，我们得出

因此，我们可以证明

也就是说，任何传感器改变其策略的诱因都可以使用单一整体势函数表示，因此提出的博弈被证明为势博弈。

2.2 分布式学习算法

每个节点的效用取决于相邻节点动作。节点不能预先访问效用值。因此，基于动作的学习算法，比如更好(或最好)答复学习算法和自适应学习算法并不能用于解决这个问题。所以，分布式学习算法是最为合适的，仅需要从先前步骤中接收到的支付。参与者根据对其它参与者动作的观察而调整自己动作。在特殊情况下，参与者既不知道其它参与者采取的动作也不了解支付函数结构形态。

我们提出了一种基于支付函数的分布式学习算法，以便实现势博弈。在提出的算法中，对于每个t≥0和i∈V，我们将传感器i更加成功的行动表示为τi(t)

(10)

提出的学习算法步骤如下：

(1)初始化：t=1，所有传感器保持其最初状态。

(2)更新：在每个时间点t≥2，每个传感器遵循如下规则更新状态：

1)传感器i选择探索率ε∈(0,0.5]并计算si(τi(t))；

3)基于概率1-ε，传感器i在时间点t+1保持时间点t的策略；

(3)重复：传感器i执行(2)。

3 仿真结果与分析

通过Matlab仿真软件对提出算法进行了验证分析。传感器节点随机均匀部署于200 m×200 m的二维矩形区域内。节点通信范围设置为30 m，节点传感范围随机初始化7 m至15 m均匀分布，使用不同数量节点N进行了测试，从60到500个节点，探测率ε=0.3，仿真参数见表1。采用覆盖率和能量消耗两个指标来评估提出算法的性能[2]，并与文献[12]提出的基于移动节点的修复策略和文献[7]提出的分布均匀同步覆盖学习算法进行了比较。

表1 仿真参数

3.1 网络覆盖质量结果

采用区域覆盖率指标来评价算法修复覆盖空洞的能力。将二维矩形监测区域划分成M×N大小的网格，如果网格单元坐标都在节点范围内，那它们便是被传感节点覆盖。覆盖率可以定义为覆盖至少一个传感节点的网格数量与给定区域内总网格数量比，即

(11)

式中：x和y——节点横纵坐标，Fq——每个网格是否被覆盖。

每次实验中，我们进行50次测试，每个实验由5个连续随机故障组成，均匀分布于部署区域。当覆盖率在70%以上时，网络才有效，当N=400时，该算法修复连续覆盖空洞的能力(依据覆盖率)，如图2所示。一开始的覆盖率为100%，当节点开始失败时，网络覆盖率开始下降。从图2可以看出，本文提出算法可以保持网络有效覆盖256到437个时间单位，比其它两种策略分别多出约75、100个时间单位。并且当节点开始失败时，提出算法的网络覆盖率下降速率最慢，可见提出的算法优于其它覆盖空洞修复策略并且有效维护了网络覆盖。图3显示了随着节点数量从60到500逐渐增加时，即传感节点密度增加时，3种算法的覆盖率变化情况。通过50次测试计算平均覆盖，从图3可以看出，提出算法能够维持更高覆盖率。

图2 不同算法的覆盖率结果对比曲线，N=400

图3 随着节点密度增加时，不同算法的覆盖率结果对比曲线

3.2 能耗结果分析

图4显示了其它两种方法和本文算法在替换失败节点所需的平均能耗方面的性能比较结果。当网络覆盖率达到90%以上时，提出算法替换失败节点所需的平均能耗趋于平稳。随着网络覆盖率的增加，空洞数量不断减少，3种方法替换失败节点所需的平均能耗均也不断减少，但是本文提出算法明显胜于其它算法，所需的平均能耗最少，如图4所示。

图4 随着网络覆盖率增加，替换单个失败节点的平均能耗

4 结束语

本文提出了一种无线传感网覆盖空洞修复算法。该算法基于博弈理论，结合了传感功率控制和物理节点迁移。通过具体仿真研究，在不同节点密度和覆盖率条件下，对该提议方法性能进行了研究分析。结果显示，无论在覆盖率还是能耗方面，该算法都优于其它两种覆盖空洞修复算法，延长了网络生存时间，更好地保持了网络覆盖。在后续研究工作中，我们计划通过实际约束条件进一步优化该算法，以便提高其适用性，比如，传感器的移动限制在某个方向上。

[1]Sahoo P,Liao WC.HORA:A distributed coverage hole repair algorithm for wireless sensor networks[J].IEEE Tran-sactions on Mobile Computing,2015,14(7):1397-1410.

[2]WANG Shan,WANG Qingsheng,FAN Maosen.A method of wireless sensor network coverage hole repair based on mobile node[J].Sensor and Micro System,2015,34(4):134-136(in Chinese).[王珊,王庆生,樊茂森.基于移动节点的无线传感器网络覆盖空洞修复方法[J].传感器与微系统,2015,34(4):134-136.]

[3]Rafiei A,Maali Y,Abolhasan M,et al.A tuned fuzzy logic relocation model in WSNS using particle swarm optimization[C]//IEEE Vehicular Technology Conference Vtc-fall,2013,14(6):1-5.

[4]Zhang J,Li S,Li Q,et al.Coverage hole recovery algorithm based on perceived probability in heterogeneous wireless sensor network[J].Journal of Computational Information Systems,2014,10(7):2983-2990.

[5]Xu N,Huang A,Hou TW,et al.Coverage and connectivity guaranteed topology control algorithm for cluster-based wireless sensor networks[J].Wireless Communications & Mobile Computing,2012,12(1):23-32.

[6]ZHAO Haifu,CHEN Jiong,GU Yuantao.Mobile base station’s relocate method based on improved virtual force algorithm[J].Telecommunication Engineering,2012,52(3):294-299(in Chinese).[赵海富,陈炯,谷源涛.基于改进虚拟力算法的通信基站再部署策略[J].电讯技术,2012,52(3):294-299.]

[7]Zhu M,Martínez S.Distributed coverage games for energy-aware mobile sensor networks[J].Siam Journal on Control & Optimization,2013,51(51):1-27.

[8]Miranda K,Molinaro A,Razafindralambo T.A survey on rapidly deployable solutions for post-disaster networks[J].IEEE Communications Magazine,2016,54(4):117-123.

[9]Qin N,Guo L,Ding Z,et al.A vector algebraic algorithm for coverage compensation in hybrid wireless sensor networks[J].International Journal of Distributed Sensor Networks,2013(1):1-8.

[10]Bialek-Davenet S,Leflon-Guibout V,Minh OT,et al.Hole detection for increasing coverage in wireless sensor network using triangular structure[J].International Journal of Computer Science Issues,2012,9(1):672-673.

[11]Han CY.Repair method for coverage holes of wireless sensor networks based on distance[J].Transducer & Microsystem Technologies,2013,32(4):91-94.

[12]HUANG Yue,WU Chengdong,ZHANG Yunzhou,et al.Repair strategy of coverage holes in hybrid wireless sensor networks[J].Journal of Jiangnan University(Natural Science Edition),2012,11(4):418-422(in Chinese).[黄月,吴成东,张云洲,等.混合无线传感器网络覆盖空洞修复策略[J].江南大学学报(自然科学版),2012,11(4):418-422.]

[13]Wang X,Zheng W,Lu Z,et al.Dense femtocell networks power self-optimization:An exact potential game approach[J].International Journal of Communication Systems,2016,29(1):16-32.