一种基于区域分裂与合并的势博弈网络拓扑控制算法*

魏连锁，陈齐齐，韩 建，苏 扬

(齐齐哈尔大学计算机与控制工程学院，黑龙江 齐齐哈尔 161006)

1 引言

无线传感器网络WSN (Wireless Sensor Network)是一种由大量分散的微型节点组成的分布式网络，由于其特殊的地理要求，部署的节点能量有限且不易更换电池，因此在设计无线传感器网络时要着重考虑能耗因素与影响[1 - 5]。

近年来，国内外学者提出了大量的拓扑控制算法[6 - 9]。从优化网络生命周期角度出发，从各方面降低能耗。文献[10]设计一种基于链路能耗博弈的拓扑控制算法，使其节点在最大功率下运行获取最小跳数，通过最优响应策略选择收益最大的节点功率和链路来降低网络能耗。随后Santi等人[11]以节点发射功率和通信范围内邻居节点的个数作为因子代入效用函数，提出一种基于博弈论的分布式非合作博弈拓扑控制算法MIA(Max-Improvement Algorithm)，但生成的网络鲁棒性较差，当节点执行顺序不同时会生成不同的网络拓扑结构；之后研究人员在MIA算法的基础上提出了一种改进算法DIA[12]，该算法虽然能够保证网络拓扑结构的唯一性，最小化发射功率，达到纳什均衡[13]，但随着网络的运行，节点的能量分布差异越来越大。为此，文献[14]提出一种基于序数势博弈的网络拓扑控制算法DEBA(Distributed Energy-Balanced topology control Algorithm)，该算法综合考虑节点剩余能量和节点功率等因素，结合势博弈，动态调控网络，均衡了节点负载，但却没有合理考虑网络连通性和鲁棒性问题。文献[15]通过引入超模博弈理念，将节点度、网络连通性和MAC层干扰程度融入效用函数中，提出一种跨层优化的WSN能耗均衡拓扑博弈算法COETG(Cross-layer Optimized WSN Energy balanced Topology Game algorithm)，该算法在保证网络整体连通性的情况下降低了节点发射功率，均衡了网络能耗。上述网络拓扑控制算法达到了较好的网络拓扑控制，在一定程度上提高了网络性能，但是这些算法没有考虑网络节点的密集和稀疏问题，当监测区域中节点数量增加时，将出现个别节点负载过大、部分区域节点分布稀疏或出现瓶颈节点等问题，造成网络节点能耗不均匀、个别节点过早死亡以及网络生命周期短。

针对以上问题，本文提出一种基于区域分裂与合并的势博弈网络拓扑控制算法RSMA(Region Splitting and Merging Algorithm)。对目标区域进行划分，区域内部进行博弈生成网络拓扑结构，对密集区域实行分裂再博弈，减轻节点负载；对稀疏区域进行合并，以保证网络整体连通。仿真实验表明，该算法不仅解决了网络的连通性与密集问题，而且还降低了节点负载，均衡了网络整体能耗，进一步延长了网络生命周期。

2 相关理论与模型

2.1 网络模型

(1)网络区域中的所有节点ID唯一。

(2)网络中的每个节点都能获取通信范围内邻居节点的ID、剩余能量、通信距离和节点之间最小通信功率。

(3)能从任意一个节点判断整个网络的连通性。

2.2 势博弈网络拓扑模型

势博弈为策略博弈Γ=〈M,S,u(S)〉中的一种，主要包含3个要素，参与者M、策略空间S和效用函数u(S)，具体说明如下：

参与者M={1,2,…,m}表示博弈参与者集合，参与者数量为m；策略空间S是Si(i∈M)的笛卡尔积，若参与者i存在k个可选策略，则Si={s1,s2,…,sk}。通常用s=(si,s-i)∈S表示一个策略集合，其中si表示参与者i的策略选择，s-i表示其余参与者的策略选择；效用函数集合u表示为：u={u1,u2,…,um}，其中ui表示参与者i在策略集合(si,s-i)中所得到的效用值。

在网络拓扑控制博弈模型搭建中，最重要的部分即为效用函数的建立。效用函数表示网络中每个节点连入网络中所能产生的效用值。在网络中，对于网络中任意一个节点i，节点的效用函数定义如式(1)所示：

(1)

(2)

其中，fi(pi,p-i)表示其网络的连通性，通过深度遍历算法判断每一个节点接入网络时，网络是否连通。当fi(pi,p-i)=1时网络连通，表示节点i可通过网络链路与其他所有节点进行通信；当fi(pi,p-i)=0时网络不连通，则节点i接入网络时所产生的效用值为负数，在网络拓扑搭建时基本上可以忽略该功率下节点i接入网络的可能。α和β是权重因子，且α,β>0；pi表示节点发射功率；Eo(i)为节点i初始能量；Er(i)为节点i剩余能量；j为节点i当前功率pi下的邻居节点，Eo(j)为节点j初始能量;Er(j)为节点j剩余能量。在效用函数中综合考虑了网络整体连通性、邻居节点剩余能量和节点发射功率等因素。

3 分区域合并与分裂拓扑控制算法

3.1 区域划分阶段

当在监测区域内节点布署较多的情况下，生成的网络拓扑结构局部区域会呈现出2种极端情况：部分节点负载过重以及出现瓶颈节点(在通信半径内无邻居节点或是网络整体不连通)。针对这2种极端情况，本文提出区域划分策略，按照实际情况将监测区域划分为若干子区域。区域划分策略有效控制了节点通信范围内的邻居节点个数，同时也降低了瓶颈节点产生的机率，保证了网络连通性。

3.2 邻居发现阶段

3.3 区域内部博弈阶段

各区域内部中所有节点轮流执行博弈，在每轮博弈中只有一个节点调整其发射功率,代入式(1)中获取其对应效用值，选取最大效用值对应发射功率作为节点最终发射功率。此时，根据网络中所有节点最终发射功率更新邻居节点集合以及生成区域内部网络拓扑结构。当每一个节点对应功率下的效用值达到最大时，且不存在随意调整任意节点的功率使其网络效用值变大，此时网络达到一种最佳动态平衡，即纳什均衡[13]。

3.4 分裂与合并阶段

区域内部网络拓扑结构生成后，在小概率下依然会出现部分子区域节点负载过重，以及出现瓶颈节点，为此本文提出区域内部的分裂与合并策略，进一步优化节点负载和瓶颈节点。在完成分区域博弈后，遍历整个网络中的所有节点，分别对节点度超过阈值的区域与出现瓶颈节点的区域进行标记。

对于节点度超过阈值的区域，其能量消耗过快，导致网络整体能耗不均匀，考虑到延长网络生命周期，本文对此区域进行左右均等分裂，对分裂后的子区域再次执行博弈后生成新的网络拓扑结构。

对于存在瓶颈节点的区域，由于其整体网络不连通，在此对该区域实行合并操作。通过链路权值函数计算得到瓶颈节点与其他节点所有链路对应效益值，并选取最大效益值对应链路，更新邻居节点集合，生成新的网络拓扑结构。

链路权值函数如式(3)所示：

(3)

(4)

其中，k1、k2表示权值调节系数，且k1+k2=1。Eij(t)表示节点剩余能量。LQij(dij)表示节点i与节点j之间的通信链路质量，γ为链路质量调节系数，γ越大表示链路质量LQij(dij)随距离d(i,j)变化越敏感。链路权值函数ωij(t)综合了网络的通信质量和能耗均衡，当节点剩余能量降低时，权值函数中能耗权值占比增加，随着网络运行，能够自适应地提高自身能耗均衡的效果。

3.5 簇首选举及博弈阶段

为了将网络中所有节点连成一个整体，在所有子区域内部选举簇首节点，执行博弈后生成对应网络拓扑结构。考虑到节点转发跳数过多将影响网络生命周期，本文在区域内部选取簇首节点时着重考虑节点的节点度，即优先考虑在一跳范围内连接节点较多的节点，并综合其邻居节点集合选取簇首节点，对每个子区域选取一个簇首节点。簇首节点选取后调整其通信半径，以最大功率广播消息后获取簇首邻居节点集合，并按照不同节点间通信功率生成对应簇首策略集合，执行博弈后更新邻居节点集合并生成簇首网络拓扑结构。

3.6 拓扑维护阶段

考虑到无线传感器网络中每个节点收发数据量不一致，在网络长时间运行时导致节点能量消耗不均衡，以至于部分节点过早死亡，影响网络整体生命周期，因此本文设定当网络中出现节点的剩余能量低于预先设置的阈值时(低于初始能量的20%)，该节点广播拓扑维护请求，请求重新执行算法生成新的网络拓扑结构，以均衡节点能耗，进一步延长网络生命周期。算法实现伪代码如算法1所示：

算法1RSMA

输入：节点个数N,通信半径rc,初始能量Er,剩余能量Eo。

输出：neb_i。

2.Determine the neighbor nodesneb_i；

3.Determine the power for nodei；

4.computehavilable communication power values of nodei；

5.foralli≤Ndo

6 Choose power based on；

10.endif

11. Updatepi,update neighbor；

12.iflen(neb_i)≥value；

13. Split district；

14.endif

15.ifdistrictfi(pi,p-i)=0；

16. Merge district；

17.endif

18. Select cluster；

19. cluster game；

20.ifEr≤min_value

21. Re-executes the algorithm;

22.endif

23.endfor

4 仿真结果及分析

本文采用PyCharm2019仿真软件进行实验仿真,分别选取DEBA算法[14]、COETG算法[15]作为本文算法对比对象。具体仿真参数如表1所示。

Table 1 Simulation parameter settings表1 参数设置

仿真实验的性能评价指标为:

(1)平均节点度：每个传感器节点度之和与网络节点总数之比，计算方式如式(5)所示：

(5)

其中，Di表示节点i的节点度，b表示区域节点数量，a表示所在区域,N为网络节点总数。

(2)网络生命周期：本文设置网络生命周期计算公式如式(6)所示：

(6)

(3)剩余能量标准差：网络剩余能量平均值与每个节点剩余能量的标准差，计算方式如下：

(7)

(8)

为了客观展示本文提出的区域划分以及分裂、合并策略相比传统算法的优势，在区域内布置节点数量较多情况下对比DEBA算法产生的网络链路结构。如图1所示，当区域内部署节点数量较多时，DEBA算法表现出网络通信链路过于复杂，出现了瓶颈节点；易造成网络整体能耗不均衡、网络不连通以及网络生命周期短。显然在节点数量布置过多的情况下，该算法不太实用。

Figure 1 Traditional network link diagram图1 传统网络链路图

在本文提出的区域策略划分下，网络整体链路如图2所示，区块内部网络链路清晰，有效减少了冗余链路。而在分裂与合并策略下优化的网络链路如图3所示，进一步减少了冗余链路，并解决了瓶颈节点问题，且各区域网络处于连通状态。

Figure 2 Partition game link diagram图2 分区博弈链路图

Figure 3 Split and merge game link diagram图3 分裂、合并博弈链路图

在执行区域划分策略以及分裂、合并策略后，区域内部节点分簇、簇首节点网络拓扑如图4和图5所示，在簇首机制下节点通信链路清晰，网络整体连通。

Figure 4 Node clustering diagram图4 节点分簇图

Figure 5 Network topology of cluster head node图5 簇首节点网络拓扑图

为了更客观地反映本文算法的性能，本文进行了5组对比实验，节点数量从250依次增加到600，通过观察3种算法在网络平均节点度、最大节点度、平均发射功率、平均生命周期和剩余能量标准差5个方面的表现来进行对比。

图6和图7显示了3种算法的网络平均节点度和最大节点度对比。在本文提出的RSMA算法中，随着节点数量增加，平均节点度趋于稳定；而DEBA算法和COETG算法在节点数量增加时，节点度也随着攀升，当节点个数增加至一定数量时，平均节点度与最大节点度出现跳跃式增长。由于本文RSMA算法考虑到节点分布时呈现随机性，当区域节点数量增加时，网络冗余链路随之提升，而冗余链路将导致部分节点的节点度过大，因此RSMA算法将冗余链路过大区域进行分割，有效地减少了冗余链路，降低了部分节点的节点度，故网络平均节点度与最大节点度相对较低。

Figure 6 Comparison of average node degree图6 平均节点度对比图

Figure 7 Comparison of maximum node degree图7 最大节点度对比图

图8为3种算法的节点平均发射功率，可以看出，本文提出的RSMA算法具有很好的稳定性，且平均发射功率低于DEBA算法的，COETG算法在节点较少的情况下节点平均发射功率较低，但稳定性不强，当节点数量超过一定限度时，功率随之急速增加。由于RSMA算法采取区域划分策略，降低了区域内部节点通信能耗，而分裂机制有效缓解了节点负载，所以整体上降低了节点平均发射功率。

Figure 8 Comparison of average transmit power图8 平均发射功率对比图

图9为3种算法的网络平均生命周期(式(6))的对比图，可以看出网络平均生命周期随着节点数量的增加而变短，但本文提出的RSMA算法网络生命周期相比其他2种算法表现出较好的稳定性，随着节点数量增加波动较小。由于RSMA算法加入了分裂、合并策略，在保证网络连通的情况下以较低的功率构建网络拓扑结构，有效地降低了节点能耗，从而延长了网络平均生命周期。

Figure 9 Comparison of average life cycle图9 平均生命周期对比图

节点剩余能量标准差由式(7)和式(8)计算得到，3种算法的网络节点剩余能量标准差具体情况如图10所示。

可以看出，DEBA算法和COETG算法的剩余能量标准差上升较快，因为其部分节点负载过大，消耗能量较快；而对于其产生的瓶颈节点而言，节点消耗忽略不计，从而导致网络整体能耗不均衡，节点剩余能量标准差过大。而本文提出的RSMA算法综合考虑了这2种因素，降低了密集区域节点负载，增加了稀疏区域节点连通性，且自适应调节机制动态地均衡了网络整体能耗，降低了网络整体节点剩余能量标准差。

Figure 10 Comparison of residual energy standard deviation图10 剩余能量标准差对比图

5 结束语

本文综合考虑了链路冗余、节点负载、瓶颈节点和生命周期等问题，采用势博弈理论，划分目标区域并结合分裂、合并策略，提出了一种基于区域分裂与合并的势博弈网络拓扑控制算法RSMA。其中区域划分策略有效剔除了冗余链路，分裂与合并策略有效均衡了节点负载，解决了瓶颈节点问题，并保证了网络整体连通性。仿真结果表明，对比现有算法，RSMA算法生成的网络拓扑结构中平均节点度下降18%，最大节点度下降49%，平均发射功率下降25%，平均生命周期提高31%，剩余能量标准差下降20%，整体提升了网络性能。

后续工作中，将综合考虑无线传感器节点布置的随机性，根据其节点分布情况的特征展开研究，结合真实情况对不同环境、不同区域改进算法，进一步优化网络性能。