《1 前言 》

1 前言 　 　

在传感器网络[1] （WSN ， wireless sensor network）的拓扑控制[2 ~ 4] 中，一般可通过设置或动态调整节点的通信功率，以保证网络拓扑连通、双向连通或多连通。 WSN 生命期[5] 作为拓扑控制的关注要素，通常指在传感器网络系统的流量路由过程中，最先因电池能量耗尽而失效节点的生命期。分别从网络层和数据链路层对网络拓扑进行分析：a. 从路由的角度考虑，网络拓扑应保持全局连通，同时拓扑中链接的健壮性亦需关注。 b. 从 MAC 协议的效率来看，网络拓扑的连通冗余度过高，意味着节点的信号覆盖范围可能过大，会造成隐终端和暴露终端[6] 问题。回顾前人提出的多种无线多跳网络拓扑控制算法，文献[7]提出一种分布式拓扑控制方案 R&M ，它基于转播区域和闭包概念，通过计算转播区域和衡量转播代价，以低功率实现了网络连通，然而该算法所产生拓扑的连通冗余度偏高，因此会削弱上层协议的运行效率；Li 等人提出一种基于本地最小生成树结构的拓扑控制算法 LMST[8] ，全局调整本地独立构建的最小功率生成树，以获得双连通的拓扑，能有效地降低维持全局连通的传输功率和 MAC 层冲突，但忽视了拓扑结构的健壮性，所形成的脆弱拓扑很大程度上会削弱网络生命期的延续能力，无法满足拓扑之上路由协议均衡耗能的要求。综合考虑全局功耗、结构健壮性及通信干扰三者的算法研究尚未见报道，笔者针对传统拓扑控制方案的缺陷，设计了一种基于遗传算法的拓扑控制方案 TCM （ topology control method based on genetic algorithm）。

《2 WSN 网络模型及问题描述》

2 WSN 网络模型及问题描述 　 　

一组无线传感器节点随机散布于兴趣区域，节点能根据网络拓扑为当前传输辖域内的邻居节点提供报文接收和转发服务，随着流量经由的节点，其电池能量不断消耗。生成树结构[9] 在 TCM 中被用作拓扑形成的基本构架元素。

《2.1 生成树模型的构建》

2.1 生成树模型的构建

在 WSN 的本地拓扑控制中，欲使网络生命期最大，形成的生成树还必须符合能使网络层及数据链路层协议高效的拓扑要求，因此，通过局部网络抽象为生成树模型进行理论分析，并赋予生成树新的约束条件。首先，假设任意两节点间的通信链接具有双向性，使回复确认机制成为可行，链路的双向性可通过在拓扑连通前提下的单向链路的添加或移除 [4 , 8]方式得以保证；其次，假定所有节点具有相同的最大发射功率 pmax ，节点以 pmax 进行信号发射时能覆盖半径皆为 rmax 的圆形区域；再次，由于过大的节点入度和出度都可能引发数据报文的通信冲突，为此综合节点的出度、入度之和为“度”概念，作为衡量 MAC 层干扰的主要指标；最后，不考虑网络环境中存在障碍物等影响通信质量的外因。

WSN 可抽象为一个二维平面内的有向图 G（V，E），其中 V ， E 分别表示节点、链接的集合。节点 i 的邻接覆盖图定义为 G（V，E）内以 i 为中心、rmax 为半径的圆面区域，记作 Gi（Vi，Ei ），其中｜V｜＝ n ，｜E｜＝ m 。在 TCM 方案中提出一种描述 WSN 中节点 j 和 k 间链接健壮程度的参数 Rjk ，并定义为

其中 ej ，ek 分别表示传感器节点 j 和 k 的剩余可用能量。综上分析，在 Gi（Vi，Ei ）内构建的生成树 Ti 满足的目标可归纳为如下３个极值问题：

目标 1 （低功耗目标） min ｛ y1（i）＝Σ pk ｜ i ∈ V ，k ∈ Vi｝，其中 y1（i）∈（0，（ ni - 1） pmax ）；

目标 2 （高健壮目标） max ｛ y2 （i）＝Σ Rjk ｜（ j ， k）∈ Ti ， Ti Gi （ Vi ， Ei ）｝；

目标 3 （低干扰目标） min｛ y3 （i）＝Σdegi （k）｜ i ∈ V ， k ∈ Vi ｝，其中 degi（k）表示节点 k 在生成树 Ti 内的度值。

由于无线通信中固有的信号特征，目标 3 中生成树的节点度区别于传统模型的度概念，需要在定义上进行扩展。由于传感器节点的电磁波发射是呈全方位辐射状的，即对信号可达范围内的所有节点都存在事实上的链接，其中未出现在 Ti 构造中的隐式链接同样会引起 MAC 层信道干扰，因此也必须考虑入节点的度值，同时应避免同源链接引发干扰度的重复计入。

《2.2 模型转化》

2.2 模型转化

带低功耗、高健壮及低干扰目标的生成树问题求解，可直观地描述为寻求一种剩余可用能量充沛的传感器节点以低功率进行通信，同时避免邻居密度过高的节点使用较大通信功率，最终能实现全局通信.通的情形。因此，合理的生成树模型需在网络的低功耗、链接的高健壮性以及节点的低干扰度三者之间取得折衷。为了处理该复杂的数学模型，依据模型的结构特征和优化要求的特点，将基于生成树的多目标优化问题转化为多判据最小生成树问题 [10] 。首先，必须实现目标函数变量的一致性，定义一个表示节点 i 周边链接状态的 mi 维列向量 X ＝（ x1 x2 　… 　 xmi）T 作为统一变量，其中当属于Ti 时 xj = 1 ，否则 xj = 0 ，易知组建生成树结构的显式链接数必恒为 ni－1 ；其次，原模型必须符合最小生成树[9] 的最小特点，因而必须转化目标 2 为极小值问题，通过取健壮参数的倒数来实现。由目标 1 、目标 2 、目标 3 转化所得最小生成树的对应判据分别表示为 z1（i）， z2（i）， z3（i）：

其中 W1 ， W2 ， W3 依次对应于低功耗、高健壮及低干扰目标的 m 维行向量权重系数，为描述权重之便，假设第 j 条链接可表示为（jin，k）。使用链接的通信距离表示节点功耗高低，即 w1 j ＝ r（jin ，jout）；由前述分析，定义 ；考虑链接 j 引起的节点度，定义为

其中 表示为避免源节点 jin 对产生干扰度重复计数而定义的取舍函数，定义为

其中 x（jin，k）表示 X 中与链接（jin，k）对应的分量。由定义可知，本质上是判断链接（jin，k）是否为当前节点的最大链接，以对该链接的干扰影响进行取舍。ωk（jin ，jout）表示节点 jin 与 k 间的通信干扰函数，定义为

《3 处理多判据最小生成树问题的遗传算法设计》

3 处理多判据最小生成树问题的遗传算法设计

设计遗传算法[11 ~ 13] 对多判据最小生成树模型进行近似最优解求解，在该应用问题中，当前状态下所有可能的生成树方案组成解空间（即群体），从群体中随机选择若干个可行解形成初始群体，遗传算法依据适应度函数（判据函数）对初始群体中的个体施加遗传操作，实现个体结构重组的迭代处理。

《3.1 编码方式》

3.1 编码方式

遗传算法需要对问题所有可能的解进行编码，每个解对应于群体中的一个个体，个体又由编码串（染色体）表示。根据生成树的结构特点，采用 prüfer 数 [10]来表示问题所有的可行解，这种编码方式能惟一表示图中所有可能的生成树。

《3.2 初始群体及适应度函数的设计》

3.2 初始群体及适应度函数的设计

根据遗传算法，从群体中随机选取规模为偶数 psize 的个体群作为初始种群，对初始种群中的个体进行配对，组成遗传的父代。采用一种基于妥协的适应值分配法将式（2）映射为遗传算法中的适应度函数，并将加权 Lp 范数[12] 进行扩展后作为距离度量方式，由此定义的后悔函数为

其中 Z *＝表示代理理想点[12] 。参数  在区间（0，1）内取值，可避免公式产生零除错误，同时也使搜索随机性的增强成为可能。参数 p 代表对较大分量（判据）的偏爱程度，p 愈大，则较大的分量对后悔值的影响愈强。若设 P 为当前种群集，＝ min｛zj（X）｜ X ∈ P ， j ＝ 1 ， 2 ， 3｝； ＝ max｛zj （X）｜ X ∈ P ， j ＝ 1 ， 2 ， 3｝。必须确保后悔值较小的个体具有较大的适应值，因此设计适应度函数表达式为

其中 rmax 和 rmin 分别表示当前种群中个体的最大后悔值和最小后悔值。

《3. 遗传算子的设计》

3. 遗传算子的设计

遗传操作模拟生物基因的遗传和变异，是一个优化搜索过程，可使问题的解迭代优化，并逼近最优解。遗传操作主要包括 4 个算子：识别、选择、变异和杂交。由于邻接覆盖图未必是一个完全图，而 prüfer 的编码方式可能导致对应的生成树并非邻接覆盖图的子图，故引入了识别算子以剔除种群中不合法的个体。选择算子建立在对群体中个体适应度进行评估的基础上，适应度函数通过调整参数 p 和  即可实现适应度变换，以限制早期竞争和加速晚期竞争，因此算法仅采用轮盘赌选择[14] 就可避免未成熟收敛现象，即个体 k 被选择概率为 Pk ＝ ，其中 Xk 表示个体 k 对应的链接状态向量。变异和遗传算子由合法个体依照预设概率进行。变异算子是改变染色体中某些基因座上的基因值从而获得新个体，算法中采用扰动变异[10] ，即依概率 Pm 选取染色体中一个随机基因并替换为另一个可行的随机值。一个 8 顶点生成树编码的变异例子如图 1a 所示。变异算子使遗传算法具有局部的随机搜索能力，当逼近最优解时，变异还可加速其收敛，使后代种群具有多样性。杂交算子是对选定的双亲交换子染色体组合 2 个新的后代个体过程，杂交后产生的子染色体具有双亲染色体的特征，算法采用二点杂交方式，即随机选取双亲中交叉子染色体的起始位置和串长，依概率 Pc 进行杂交操作，杂交例子如图 1（b）所示。

《图 1》

图 1 变异与杂交操作

Fig.1 Mutation and crossover

《4 TCM 拓扑控制方案》

4 TCM 拓扑控制方案 　 　

上述构建了符合问题特征的多判据最小生成树模型，并设计了处理该模型的遗传算法。传感器节点一般会存在于多个节点邻接覆盖图的交集中，因此在本地拓扑确定后还需进行全局调整，此时节点将选取所处的多个生成树中对其覆盖范围要求最高者。TCM 方案正是一种基于遗传算法的本地最小生成树构造策略，TCM 方案的伪代码表示如下：

1 .TCM（ G（V ，E）） 　

2 .｛do 　

3 .｛while（i ∈ V） 　

4 .｛init（ P（0））；/ *参数及种群初始化 * / 　

5 .for（k ＝ 1 ；k amount ； k ＋＋）/ * 迭代逼近最优解 * / 　

6 .｛evaluate（）；/ * 适应度评价 * / 　

7 .for（j ＝ 2 ； j psize ； j ＝ j ＋ 2）/ * 产生子代种群 * / 　

8 .｛ ＝ select（）； ＝ select（）；/ * 选择操作 * / 　

9 .crossover（ ，）； identify（）；｝/ * 父代杂交与后代识别 * / 　

10．calculate（）；/ * 计算判据向量 Z * / 　

11．if（Zmin （X） Zmin （ X0 ld ））｛X0 ＝ X ；｝/ * X0 为非劣解 * / 　

12 .｝｝ 　

13 . adjust（）；/ * 全局拓扑调整 * / 　

14 .｝ while（Δtime ＝ interval） 　

15 .｝

TCM 方案在时间间隔 interval 后会重新调整拓扑，本地的生成树抽象成规模为 psize 的种群进行遗传操作，通过 amount 次迭代逐步逼近判据的最小化状态，根据表示本地生成树结构的非劣解 X0 调整全局拓扑，从而实现 WSN 的拓扑控制。从伪代码可知，TCM 方案的时间复杂度可分为 2 阶段，第一阶段为 n 个本地多判据最小生成树的构建阶段，其时间复杂度为 O（amount·psize· ）。第二阶段是在构建之后的全局拓扑调整阶段，仅与 WSN 的规模有关，其复杂度为 O（n）。所以，TCM 的时间复杂度为 O（amount · psize ·＋ n）。通常情况传感器节点数 n 庞大，psize 和 amount 可视为常系数，且节点的邻接覆盖图内节点数相对有限，假定有 ni = （1 i n），此时 TCM 的时间复杂度 O（amount·psize ·＋ n）～ 。

《5 性能分析》

5 性能分析

《5.1 实验环境及参数》

5.1 实验环境及参数

假定有 n（n 值从 50 逐渐增至 100）个节点随机散布于 100 m × 100 m 的二维方形区域，其中分别随机选择 1 ， n/5 个不同节点作为汇聚节点和源点，（i ，j）链接单位流量费用函数 wij ＝ kr（i ，j）2 。实验中不考虑节点的移动性，并且忽略节点接收报文及处理器的能耗。实验参数如表１所示。

《5.2 实验及分析》

5.2 实验及分析

5.2.1   实验 1 　假定任意某节点 i 的能量 ei ＝ random （20 ，40）J ，TCM 中遗传算法的种群规模 psize = 4 ，其余参数同表 1 。 R&M ，LMST 和 TCM 所获拓扑的平均链接长度、平均节点度和平均链接健壮程度随 n 的变化情况见图 2 。从图 2a 可见，3 种方案的平均链接长度随 n 增长持续减小，其中 TCM 和 LMST 曲线差异极小，且趋于重合；图 2b 表明 TCM 的节点平均度值最小，且 TCM 与 LMST 随 n 变大平均度值呈小幅降势，而 R&M 表现出较为明显的上升势态；从图 2c 可见，TCM 方案所获拓扑的平均链接健壮程度远高于 LMST 和 R&M 。

《表 1》

表 1 实验参数表

Table 1 Experiment parameters table

《图 2》

图 2 不同方案生成拓扑的指标比较

Fig.2 Criterions of topologies from different schemes

5.2.2   实验 2   WSN 生命期是评价拓扑控制方案性能的首要指标，因此通过仿真实验对 R&M ， LMST ， TCM 三种拓扑控制方案的网络生命期进行比较。设定 TCM 中遗传算法的种群规模 psize ＝ 4 ，源点的初始能量为 40 J ，其他节点的初始能量为 20J 。 3 种方案随节点数目变化的性能曲线如图 3 所示。从图 3 可以看出，拓扑结构的短链接、低节点度及高健壮综合特性，使得 TCM 的性能曲线高于 LMST 和 R&M 。随节点数目增加，3 种方案的生命期均呈上升势态，这是由于节点分布密集则较多低功耗链接得以出现在拓扑中，因此延长了网络生命期。此外，TCM 与 LMST 方案的 WSN 生命期增幅随 n 增加趋于明显，而 R&M 方案趋于缓和，这是因为通信干扰对 TCM 和 LMST 的影响持续削弱，而 R&M 方案中所受干扰逐渐加剧。

《图 3》

图 3 三种拓扑控制方案性能比较

Fig.3 Performance comparison of three topology control schemes

5.2.3 　实验 3 　遗传算法的种群规模 psize 大小是影响 TCM 方案性能的重要因素之一，实验分析了在不同种群规模下 TCM 方案的性能变化情况，除 psize 外其余参数同实验 2 ，曲线变化如图 4 所示。从图 4 可见，psize 值较大的 TCM 方案具有较长的生命期。随着节点数的逐渐增加，不同种群规模下 TCM 性能差距愈加显著，这是因为节点分布密度变大，会引发本地生成树对应的可行解增多，此时较大种群规模加速非劣解搜索的优势将得到更佳体现。图 4 还表明，随 psize 增长不同曲线间的纵坐标差异趋于弱化，当 psize 取值 6 和 8 时 TCM 性能已较为接近，同时从遗传算法的伪代码可知，由 psize 增加带来的 TCM 性能优化是以时间复杂度的增大为代价的，虽然未考虑，但事实上节点处理器工作显然会消耗能量，因此在实际应用中 psize 取值应进行多方面权衡。

《图 4》

图 4 种群规模对 TCM 性能的影响

Fig.4 Effect of population scale on TCM performance

《6 结语 》

6 结语 　 　

WSN 的拓扑控制属于 NP-hard 问题[15] ，如何设计具有良好性能的近似解决方案是当前 WSN 研究的热点和难点之一。提出一种基于遗传算法的拓扑控制方案 TCM ，并通过仿真实验对该方案进行了性能分析和验证。实验表明，TCM 方案能获得低功耗、高健壮及低干扰的拓扑结构，并能有效地延长 WSN 的生命期。 TCM 能为数据的高效传输、均衡地消耗 WSN 的能量提供了良好的支撑基础，并最终能延长网络的生命期，对具有广泛应用前景的无线传感器网络的拓扑控制方案设计具有现实参考意义。