无线传感器网络（wireless sensor networks，WSN）是以大量能量有限的智能传感器为节点，并将其分布在所要监控的区域内，然后对信息进行采集、传输和处理的一个网络信息系统^[1]。拓扑控制技术能够在满足网络连通与覆盖性基础上，剔除网络中冗余的通信链路，提高传感器节点数据传输成功率，保持网络能耗均衡，延长网络生命时间及优化网络性能^[2]。

目前，国内外学者对WSN网络拓扑控制算法已经进行了相关研究并取得了一些成果^[3]。较为普遍的两种拓扑控制方法为功率控制^[4]和层次型拓扑控制^[5]。其中：功率控制主要是以传感器节点的功率变化作为切入点，通过在不同时间段内有规律地控制节点的功率以达到降低节点能耗的目的；层次型拓扑控制是以对传感器节点进行簇的划分，以维持网络工作的策略。

现有的WSN网络拓扑优化算法主要针对网络拓扑的连通性^[6]、能耗均衡^[7]、生命周期^[8]等方面进行优化。

在拓扑连通性方面，Deniz等^[9]通过调节节点不同状态下的传输能力，以确保节点故障时网络的连通性。Akbari Torkestani^[10]在部署网络节点时为每个节点配备具有自我学习能力的学习机制，使网络具有一定的自适应性，极大提高了网络的连通。但上述方法对于传感器节点的要求过高，造价过于高昂。郝晓辰等^[11]以负载均衡评价模型为条件选择最优发射功率并利用YG图构建拓扑结构，该拓扑结构虽然降低了网络的开销，但是模型计算和拓扑构建过程较为复杂。在能耗均衡方面，Wang等^[12]提出一种分簇的控制算法，降低了网络平均能耗，但其拓扑结构的健壮性不强。为了有效提高网络拓扑结构的健壮性，Anderson等^[13]利用刚性图中刚度矩阵能够对网络定位的特性，在定位点选择过程中，通过提高刚性矩阵特征值的方法来提高网络的健壮性。但由于传感器节点的能量是有限的，仅考虑网络健壮性是不足的，网络的生存时间将是网络拓扑控制的首要问题。在网络生存周期方面，Zebbane等^[14]将网络进行组划分，并对传感器节点设置了sleep和wake两种模式，以此延长传感器节点的生存时间。罗小元等^[15]提出了一种基于最小刚性图代数特性的拓扑优化算法，该算法综合考虑了链路权值与刚性图的刚度问题，使生成的总链路权值较小，网络鲁棒性较好，延长了网络的生存时间。

传统的拓扑控制算法是在理想情况下进行的，即节点是无私的，但在实际情况中节点会自私地降低能耗以保存自身能量。因此，更为合理的一般性假设为节点总是自私的，它们之间存在竞争行为，并且可以自主决策^[16]。博弈论是具有竞争行为的数学理论，对于节点而言，可以更好地制定节点间的最佳合理性策略^[17]。

Komali等^[18]提出一种基于博弈论的分布式拓扑控制算法（MIA），通过考虑网络的连通性和节点的发射功率制定了节点在不同网络状态下的最佳选择策略。该算法虽然可以保证网络节点的最大策略选择，但是在不同的执行顺序下，网络中的拓扑结构是不一样的。因此Komali在此基础上进行了改进，改进后的DIA算法^[19]保证了网络拓扑结构的唯一性。但该算法并未考虑到节点自身剩余能量问题，在算法的执行过程中，虽然降低了网络的能耗，但是节点自身的剩余能量会加速网络节点能耗的不平衡。李小龙等^[20]在构建效用函数时同时考虑了网路的连通性和节点的剩余能量问题，提出了基于势博弈的分布式拓扑控制算法DEBA，该算法能够保证网络节点行为存在纳什均衡^[21]点，且拓扑结构具有唯一性，通过网络节点的剩余能量有效地均衡了节点间的能量消耗，延长了网络的工作时间。但该算法没有考虑到网路中部分节点在不同状态下的节点度问题，无法保证节点资源的最优设置。蔡钊等^[22]在效用函数中考虑到了节点在不同状态下的节点度，规避了在某单一状态下节点度过大的问题，保证了节点资源。

上述算法并未考虑到网络拓扑结构中节点的节点度、网络拓扑鲁棒性、链路冗余等问题，能量多的节点快速耗尽能量而死亡。针对以上问题，作者提出一种基于最优刚性子图的势博弈无线传感器网络拓扑控制算法。该算法在保证网络连通性的条件下，综合考虑网络节点的剩余能量，同时，对于在网络节点经博弈阶段均衡能耗后存在的冗余链路，提出利用最优刚性子图方法剔除网络中的冗余链路。

1 模型及相关理论 1.1 网络模型及相关假设

无线网络传感器中的网络拓扑结构通常用图 $G = (V,E,P)$ 描述,其中顶点集 $V = \{ 1,2, \cdots ,n\} $ 表示传感器节点， $E{\rm{ = \{ (}}i{\rm{,}}j{\rm{)}} \in V \times V{\rm{:}}i \ne j{\rm{\} }}$ 表示传感器节点间的链路集，对于任意两个节点 $i,j \in V$ ，若满足 $de(i,j) \le {r_{\rm{c}}}$ ，则称节点 $j$ 是节点 $i$ 的邻居节点。 $P =\left\{ ({p_1},{p_2}, \cdots ,{p_n}):\right. \left.{p_i} \in [{p_{\min }},p_i^{\max }]\right\} $ 为节点 $i$ 在其通信半径内与各节点间通信所需功率集合，其中， ${p_{\min }}$ 为节点间接收门限， $p_i^{\max }$ 为节点 $i$ 的最大功率。

为了方便后文计算，给出以下常用定义。

定义1（节点度）　设 ${R_i}$ 为节点 $i$ 的通信邻居节点集合，则集合 ${R_i}$ 中的元素个数（集合 ${R_i}$ 的势）即为节点 $i$ 的度数 ${K_i}$ 。 ${K_i}{\rm{ = |}}{R_i}{\rm{|}}$ ，即 ${K_i}$ 为节点 $i$ 的节点度。

定义2（平均节点度）　无线传感器网络中所有节点的度数之和与节点数目的对比值称为平均节点度 ${K_{\rm ev}}$ ， ${K_{\rm ev}}{\rm{ = }}\displaystyle\sum\limits_{i = 1}^n {{K_i}/n} = \displaystyle\sum\limits_{i = 1}^n {|{R_i}|/n} $ 。

定义3（节点的连通性）　对于任意两节点 $i,j \in V$ 有 $F(i,j) = {\rm{1}}$ ，则称节点间是连通的，否则为不连通。

1.2 博弈论模型

设博弈模型为 $T = \left\langle {N,A,U(A)} \right\rangle $ ，则在博弈中主要包含了个3个要素：参与者、策略集、收益函数。

1）参与者 $N = \{ 1,2, \cdots ,n\} $ ，其中 $n$ 为博弈参与者个数。

2）策略集 $A$ 。 ${A_i}$ 为参与者 $i$ 的行为集合,若 $i$ 存在着 $k$ 个行为，则有 ${A_i} = \{ {a_1},{a_2}, \cdots ,{a_k}\} $ ， $A=\{{A_i}\} _{i = 1}^N$ 。令 ${a_i}$ 为参与者 $i$ 的某一特定行为，则 ${a_{ - i}} = ({a_1}, \cdots ,{a_{i - 1}},{a_{i + 1}}, \cdots ,{a_n})$ 为其他参与者的行为组合，通常用 $a = ({a_i},{a_{ - i}})$ 表示某一特定的行为组合。

3）收益函数 $U(A)$ 。 $U{\rm{ = \{ }}{u_1},{u_2}{\rm{,}}{u_3}, \cdots ,{u_i}{\rm{\} }}$ ，则可用 $ {U_i}({a_i},{a_{ - i}}): $ $A \to R$ 表示参与者 $i$ 在行为组合 $({a_i},{a_{ - i}})$ 下的收益。

1.3 刚性图模型

如图1所示：在无向图 $G = (V,E)$ 中，对于任意两个顶点 $(i,j) \in E$ ，节点的运动轨迹 $f(t)$ 满足 $||{f_i}(t) - {f_j}(t)|| = d$ ，其中， $d$ 为常数。若该无向图中顶点的运动轨迹是不变的，则称该无向图为刚性图，反之则为可变形图。

定义4（最小刚性图）　如果在维持图的刚性的情况下，任意地删除图中的某一条边都会影响该图的刚性，则称该图为最小刚性图。

定义5（最优刚性图）　如果一个拓扑图是最小刚性图，并且在相同顶点的条件下图中链路的加权和最小，那么称该图为最优刚性图。

定义6（最优刚性子图）　对于任意的两个拓扑图 $G = (V,E)$ 、 $G' = (V',E')$ ，若 $V' \subseteq V$ ， $E' \subseteq E$ 则称 $G'$ 是 $G$ 的子图，当且仅当图 $G'$ 是最优刚性图时，称 $G'$ 为 $G$ 的最优刚性子图。

2 网络拓扑控制模型 2.1 势博弈模型

WSN拓扑控制算法要综合考虑网络连通性、节点负载能耗、节点剩余能量、网络生存时间等多个目标进行优化。作者利用DEBA算法^[11]的效用函数作为本文势博弈模型的效用函数，因此，本文的效用函数仍然收敛至纳什均衡解，对此不做具体证明。效用函数的具体描述如式（1）所示：

${\;\;\;\;\;U_i} = {F_i}({p_i},{p_{ - i}})\bigg(ap_i^{\max }\frac{{{E_{\rm{o}}}(i)}}{{{E_{\rm{r}}}(i)}} + b\overline {{E_i}({p_i})} \bigg) - a{p_i}\frac{{{E_{\rm{o}}}(i)}}{{{E_{\rm{r}}}(i)}}$

(1)

式中： $a$ 、 $b$ 为效用函数的权重因子； ${p_i}$ 为节点 $i$ 的发射功率； ${p_{ - i}}$ 为剩余节点的发射功率； ${F_i}({p_i},{p_{ - i}})$ 为网络的连通性，当 ${F_i}({p_i},{p_{ - i}}) = 1$ 时表示网络是连通的，反之不连通，即节点 $i$ 无法通过链路传输信息； $p_i^{\max }$ 为节点 $i$ 的最大发射功率； ${E_{\rm{o}}}(i)$ 为节点 $i$ 的初始能量； ${E_{\rm{r}}}(i)$ 为节点 $i$ 的剩余能量； $\overline {{E_i}({p_i})} {\rm{ = }}\dfrac{1}{k}\displaystyle\sum\limits_{j = 1}^k {\frac{{{E_{\rm{r}}}(j)}}{{{E_{\rm{o}}}(j)}}}$ ，其中， $k$ 为节点 $i$ 在发射功率是 ${p_i}$ 时的一跳邻居节点个数。

2.2 最优刚性子图矩阵构建

1）链路权值构建

在无向图 $G = (V,E)$ 中，若存在两个顶点 $ {v}_{i} {\text{、}}{v}_{j}$ ，使得 $de({v_i},{v_j}) \le {r_{\rm c}}$ ，则两顶点间的链路权值如式（2）所示：

${\;\;\;\;\;\;\;\;\;\;\;\;W({v_i},{v_j})} = \left\{ {\begin{array}{*{20}{c}} {de({v_i},{v_j}),} \\ {\max ,} \end{array}} \right.\begin{array}{*{20}{c}} {link({v_i},{v_j}) = 1} ;\\ {link({v_i},{v_j}) = 0} \end{array}$

(2)

式中， $ de(\cdot) $ 为节点间欧氏距离。若两顶点存在链路则 $link({v_i},{v_j}) = 1$ ，反之则 $link({v_i},{v_j}) = 0$ 。

2）子图矩阵

对于拓扑图 $G = (V,E)$ ，其中节点 $i$ 与其邻居节点所构成子图矩阵 ${{{G}}^i}$ ，其元素取值如式（3）所示：

$G_{xy}^i{\rm{ = }}\left\{ {\begin{array}{*{20}{c}} {1,link(x,y) = 1;} \\ {0,link(x,y) = 0} \end{array}} \right.$

(3)

3）刚性矩阵

在 $r$ 维空间中，通常将节点 $i$ 的坐标表示为 $ ({s}_{i}^{1}, {s}_{i}^{2},\cdots ,{s}_{i}^{r})$ ，则在2维空间中有 $ ({s}_{i}^{1}={x}_{i},{s}_{i}^{2}={y}_{i})$ 。将n个节点随机部署在 $r$ 维空间中，将其按照序号排列其位置坐标如式（4）所示：

${\;\;\;\;\;\;\;\;\;\;\;\;\begin{aligned}[b] &{\rm{\{ (}}s_1^1,s_1^2, \cdots ,s_1^r{\rm{),(}}s_2^1,s_2^2, \cdots ,s_2^r{\rm{),}} \cdots {\rm{, }} \\ &\;\;\;\;\;\;{\rm{(}}s_i^1,s_i^2, \cdots ,s_i^r{\rm{),}} \cdots {\rm{,(}}s_n^1,s_n^2, \cdots ,s_n^r{\rm{)\} }} \end{aligned}} $

(4)

在无向图 $G = (V,E)$ 中，链路集 $E = \{ (i,j) \in V \times V: i \ne j\} $ ，其中每条链路都可以转换为刚性矩阵的行向量。则在2维空间中构建刚性矩阵 ${{{M}}_{|e| \times 2n}}$ （ ${\rm{|}}e{\rm{|}}$ 为拓扑图中的链路总数）时，该图中的第 $k$ 条链路 $l_i^j$ 在刚性矩阵 ${{M}}$ 中对应的第 $k$ 行元素构成的行向量 ${{{m}}_k}$ 定义为：

${\;\;\;\;\;\;\begin{aligned}[b] &{{{m}}_k} = [0,s_1^1 - s_2^1,s_1^2 - s_2^2, \cdots ,s_i^1 - s_j^1,s_i^2 - s_j^2, \cdots ,\\ &\;\;\;\;\;\;\;\;\;\;\;s_j^1 - s_i^1,s_j^2 - s_i^2, \cdots ,0]\end{aligned}}$

(5)

则由 ${\rm{|}}e{\rm{|}}$ 个行向量在2维空间中构成的刚性矩阵 ${{{M}}_{|e| \times 2n}}$ 如式（6）所示：

${\;\;\;\;\;\;\;{M}} = \left[ {\begin{array}{*{20}{c}} {{{{m}}_1}} \\ {{{{m}}_2}} \\ \vdots \\ {{{{m}}_{|e|}}} \end{array}} \right] = ({{m}}_1^{\rm{T}},{{m}}_2^{\rm{T}}, \cdots ,{{m}}_{|e|}^{\rm{T}})$

(6)

3 WSN拓扑优化算法

作者提出了基于最优刚性子图和势博弈理论相结合的WSN节点分布式执行网络拓扑控制算法。该算法分为网络拓扑博弈与拓扑建立、冗余链路删除、拓扑维护与修复3个阶段。具体步骤描述如下：

步骤1：初始化各自的功率为最大功率，初始化传感器节点 $i$ 的最大通信半径为 ${r_{\rm{c}}}$ 。节点 $i$ 向周围节点广播信息包NCK， ${\rm NCK} = \{ {\rm ID}_i,{s_i},E_{\rm{r}}^i\} $ ，其中， ${\rm ID}_i$ 为 $i$ 标志码， ${s_i}$ 为 $i$ 的位置坐标， $E_{\rm{r}}^i$ 为 $i$ 的剩余能量。当传感器节点 $j$ 接收到节点 $i$ 信息包NCK后，节点 $j$ 向节点 $i$ 发送信息包ACK， ${\rm ACK} = \{ {\rm ID}_j,{s_j},E_j^r,{p_{ij}}\} $ ，其中， ${p_{ij}}$ 为节点 $i$ 与节点 $j$ 通信所需要的最小功率。当节点 $i$ 收到周围节点 $j$ 的确认信息包ACK后，则节点 $i$ 将节点 $j$ 添加至节点 $i$ 邻居信息表中。节点 $i$ 通过信息交换后生成策略集 $P$ ，由式（1）计算收益实时更新信息表，直至达到均衡解，由最终各节点的信息表构建节点的邻居节点集合 $R$ ，生成网络拓扑链路图。

步骤2：节点 $i$ 通过邻居节点集合 $R$ 计算邻居个数 $k$ ，构建权值链路集 ${W_i}$ 和子图矩阵 ${{ G}^i}$ 。由定义4～6判断自身所构建的链路集是否满足构建刚性矩阵，若满足则由式（2）～（5）构建刚性矩阵 ${{M}}$ ，否则重新遍历下一节点，且由定义6构建最优子刚性矩阵 ${{{M}}_{\rm{c}}}$ 。最终由最优刚性子图矩阵得到待删除链路集合 $D$ ，通过 $D$ 更新各节点的邻居节点集合 $R$ 。

步骤3：网络正常通行信状态下，设置能量阈值 ${\tau _{\rm{E}}}$ 和触发机制，当 ${\tau _{\rm{E}}} < \dfrac{{{E_{\rm{r}}}(i)}}{{{E_{\rm{o}}}(i)}}$ ，即节点的剩余能量与初始能量之比低于这个阈值时，则重新执行拓扑生成算法。若网络拓扑中有节点失效时，先判断网络是否是连通的，若连通则网络拓扑不变，否则重新执行拓扑生成算法。具体操作描述如下：1）初始化 ${\tau _{\rm{E}}}$ ，计算节点的剩余能量 ${E_{\rm{o}}}(i)$ ；2）当 ${\tau _{\rm{E}}} > \dfrac{{{E_{\rm{r}}}(i)}}{{{E_{\rm{o}}}(i)}}$ ，即出现部分节点死亡或失效时，则执行3）；3）若节点死亡或失效不影响网络的连通性时，则跳转至1），否则重新执行拓扑生成算法。

4 PGOSG算法性能评价

利用Python设计了4组仿真实验，且给出算法复杂度分析，以便去验证PGOSG算法的有效性。具体为：实验1分别从节点的发射功率、节点平均节点度和邻居节点平均剩余能量3个方面考虑权重因子 $\alpha {\text{、}}\beta $ 对网络拓扑性能的影响；实验2对不同算法所构建的网络拓扑链路图进行对比，在不同节点数下对比了DEBA、PGOSG这两种算法的平均节点度和最大节点度，分析了PGOSG算法的鲁棒性；实验3在不同节点数下对比了DEBA算法和PGOSG算法的平均链路长度，分析了PGOSG算法的链路质量；实验4在不同节点下对比了DEBA、PGOSG这两种算法的最小剩余能量，分析了PGOSG算法的生存时间。仿真实验参数如表1所示。

4.1 算法复杂度

算法复杂度是衡量算法计算量的标准，下面主要分析本文PGOSG算法的时间复杂度。PGOSG算法主要包含两个阶段，即拓扑博弈阶段和冗余链路剔除阶段。拓扑博弈阶段，所有节点遍历自身策略由式（1）计算收益，并由收益确定邻居集合。博弈阶段中，假设节点的最大邻居节点个数为 $M$ （即各节点的最大策略数），其中 $1 \le M < n$ ，则算法复杂度为 $o({M^2}n)$ 。在冗余链路剔除阶段，所有节点需由邻居集合构建刚性图矩阵，执行刚性变换算法，其复杂度为 $o(Mn)$ 。综上所述，PGOSG算法的复杂度为 $o({M^2}n)$ 。

4.2 权重因子对网络拓扑的影响分析

使在2维监测区域（300 m×300 m）的内随机放置50个节点，经过多次实验后从中截取20组实验在限定 $ \alpha $ 、 $\;\beta $ 中任意一个参数值为1的情况下，调节另一参数以分析算法中权重因子对网络拓扑性能的影响。

由式（1）可知权重因子 $ \alpha $ 、 $\;\beta $ 存在着某种比例关系，因此为了便于计算在限定 $ \alpha $ 、 $\;\beta $ 中任意一个权重因子值为1的情况下，调节另一权重因子以分析算法中权重因子对网络拓扑性能的影响，以便于选定权重因子，可得 $\alpha$ 、 $ \;\beta $ 对网络性能指标影响见图2、3。

从图2中可以看出，节点的平均发射功率、平均节点度、邻居节点平均剩余能量随 $\alpha $ 的增大而减小。而图3中随着节点数目的增大而减少，由此可知权重因子 $ \alpha $ 、 $\;\beta $ 存在着某种比例关系。由网络拓扑结构的一般性理论可知，当网络中节点的发射功率较低，同时又有适中的节点度，此时的拓扑结构相对完善。因此，由文献[23]中关于网络节点的运算能力和网络性能指标的介绍，作者将 $\alpha $ 设为1， $\;\beta $ 设为1。

4.3 PGOSG鲁棒性分析

为对比不同状态下的网络拓扑链路图结构，在4.2节相同的仿真环境中，随着传感器节点数量从30变化到100时，比较DEBA算法与作者提出的PGOSG的最大节点度和节点平均度，进而验证PGOSG算法的网络拓扑鲁棒性。

图4和5分别为随机链路图和最优子刚性链路图。从图4中可以看出，将节点随机置于特定区域，其所构建的链路结构图中存在的链路较多，易导致信道间的串扰和冲突，数据包需要多次重传，从而会增加节点的能耗，造成节点过早死亡。

从图5可以看出，直接使用最优刚性子图方法生成链路图，降低了节点间的链路数，但并没有考虑节点自身的剩余能量和整个网络中能耗的均衡性，网络中节点会自私的降低自身功率，部分剩余能量较少的节点也会参与转发造成节点的过早死亡。

图6、7分别为使用DEBA、PGOSG算法所构建的链路图。

由图6可见，DEBA算法综合考虑节点的剩余能量和节点能耗均衡等问题，使剩余能量多的节点参与数据转发任务，增加的节点生存时间。但DEBA算法使剩余能量多的节点参与过多的冗余转发，部分节点所构成的子图中存在着链路数过多，链路总权值较大和网络鲁棒性较差等问题。由图7可见，与DEBA算法相比，PGOSG算法在相同参数环境下所构建的链路中的链路总数小于DEBA算法，剔除了网络中的冗余链路。

图8、9分别为DEBA和PGOSG算法的节点的最大度和平均节点度对比。从图8、9中可以看出：节点的最大度随节点数的增加而增加最后趋于稳定；节点的平均节点度先降低，再随节点数的增加趋于稳定。PGOSG算法的最大节点度低于DEBA算法。在节点数增加情况下PGOSG算法的平均节点度始终小于DEBA算法的且平均节点度稳定在3.5左右，可见网络连通情况下PGOSG算法拓扑结构相对比较稳健。

4.4 PGOSG链路质量分析

在4.2节相同实验仿真环境下，通过改变节点的个数对比分析DEBA和PGOSG算法的平均链路长度。

图10为DEBA算法与作者提出的PGOSG算法随着节点数从30增加到100的网络拓扑平均链路长度变化情况。如图10所示，由DEBA构成的拓扑结构平均链路长度比PGOSG的更长，即节点数相同时DEBA算法因网络通信时网络链路较长耗费更多的资源，而PGOSG算法耗费较少，因此PGOSG算法生成的网络拓扑链路质量较好。

4.5 PGOSG延长网络生存时间效果分析

4.2节相同实验仿真环境下，在不同节点数下对比了DEBA算法和PGOSG算法的网络生存时间。

图11、12分别为DEBA和PGOSG算法在不同节点数下的最小剩余能量和网络平局生存时间对比。

由图11可知，DEBA算法虽然关注了能量的均衡，让剩余能量多的节点参与数据转发，但没有考虑到能量剩余多的节点在其子图结构上的链路总能耗问题，部分权值较大的链路增加了节点的负载。从图12可以看出：当在固定范围内部署节点密度不同时，节点的生存时间有所差别；当区域内节点密度稀疏或密集时，网络拓扑的链路通信距离较长或通信链路过多都将导致网络拓扑生存时间的不规则变化；PGOSG算法在固定区域内当节点数达到50时，网络拓扑的生存时间较长，即区域内最佳节点部署数。同时，随着节点数的增加，PGOSG算法的生存时间总高于DEBA算法，这是因为PGOSG算法在均衡节点能耗的同时也删除了部分冗余链路，降低了部分节点的负载，使得节点在相同环境下所造成的能耗较低。

5 结　论

针对现有势博弈算法的网络拓扑结构中节点转发数过多、链路总能耗过大、网络生存时间较短、网络拓扑鲁棒性较差等问题，提出了一种基于最优刚性子图和势博弈的网络拓扑控制算法（PGOSG）。该算法在保证网络连通性的基础下，以势博弈模型均衡节点能耗，进一步利用了最优刚性子图剔除冗余链路。经仿真实验分析了该算法的有效性。下一步研究将针对算法参数选取的机械性，采用机器学习实现自适应参数调节机制。