基于3D-Tabu 禁忌搜索的广域环境MESH网络节点部署优化算法研究∗

王鸿鹏王 前张晓阳何 明陈海华∗

(1.南开大学人工智能学院，天津300350；2.南开大学电子信息与光学工程学院，天津300350；3.天津市光电传感器与传感网络技术重点实验室，天津300350)

随着人们环境保护意识的不断增强，类似于生态环境监测网络的广域三维环境通信网络建设需求正在与日俱增[1]。 传统的传感器节点部署算法，如遗传算法[2]、粒子群优化算法[3]等，在广域环境的应用中不能很好地融合三维地理环境。 本文在MESH 网络节点部署算法的研究[4]基础上，结合了三维地形和广域覆盖面积，提出了一个基于“3D-Tabu 禁忌搜索”算法的广域环境下MESH 网络节点部署及优化方案。该方案以WiFi MESH 网络为骨干网实现对监测区域的无线网络三维覆盖，可以应用在无人化的环境监测系统中。 在网络中部署多个传感器节点以及无人车、无人机等设备作为接入端，通过无线网络可以将传感器采集的环境因子信息、无人车和无人机上部署的摄像头采集的野生动物起居的视频和图片等实时传送回监测中心，为生态监测系统中的无人系统复杂作业任务提供网络通信支持，帮助野生自然保护区中的环境和珍稀野生动物的监测任务实现无人化和实时化。

虽然生态环境监测系统的建设具有广泛的需求，但由于广域环境下的无线通信网络建设受制于需覆盖网络面积大、天气环境恶劣、耗费成本大、应用场景可实验性低等因素，目前只有相关的综述研究和单个技术方向的研究。 而且由于广域环境下的网络不同于城市组网，其建设所蕴含的商业价值不高，相关的研究单位也比较少，因而只有很少的理论成果进行了相关的网络规划讨论。 但随着社会越来越文明化，人们也越来越重视环境保护等相关问题，因此，研究具有我国自主知识产权的广域环境自组网技术具有重要意义。

1 节点部署模型

在本文的节点部署优化中，已知条件包括应用场地的地理信息和通信基站设备的性能参数。 而候选站址节点的数量、坐标信息以及部署节点即通信基站的个数均为未知量。 本节将结合已知信息，把节点部署优化转换为数学问题，即把实际问题用数学语言进行描述建立数学模型[5-6]。

1.1 节点模型

已知每个通信基站设备具有相同的远距离通信半径R和近距离覆盖半径r[7]，MESH 节点间的最大跳数H。 为了便于求解，从获得的地图云集中等间隔抽取N个点来近似代表整个地形，用集合AS 来表示:

式中:n＝1，2，…，N，xn，yn，zn分别表示点an的坐标。 为了最优化部署通信基站和提高优化速度，本文从集合AS 中抽取一定比例的节点作为候选节点站址，用节点集合CS 来表示:

式中:m＝1，2，…M，M为候选站址节点的个数。 设集合MRS 是从集合CS 中选出的MESH 骨干网节点集合，即当前的解集合:

式中:sk，k＝1，2，…K，表示被选中的通信基站站址坐标，K为所选基站站址的个数，均为需优化变量。

1.2 网络联通模型

在搜索最优解过程中需要不停地更改选址方案，容易导致网络整体连通性得不到有效保障，所以在搜索时需要测试当前解所对应网络的连通性，即所选节点部署方案必须实现所有节点的连通。 一般地，如果网络中的任一MESH 节点通过单跳或多跳可以与网络中其他所有节点实现联通，则该网络是连通的。 反之，该节点属于失效节点，当前解对应的网络是不连通的。

定义CM 为集合MRS 的连接矩阵，用以表示当前解集合对应的节点坐标及节点间连通的关系[8]

式中:i，j＝1，2，…，K。

图1 是一个由5 个节点组成的简单骨干网，绿色区域为各个节点的通信范围，即半径为R的圆，从图1 中可以直观地看到各节点间的连接关系，其的邻接矩阵为:

由图1 可以看出，有一部分节点与其他部分节点是无法通过直接连接实现通信的，比如节点1 和节点3。 然而通过节点2，节点1 和节点3 可以实现通信，则上述两个节点之间的连接称为二次连接。同理还有三次、四次连接等。 只要能够在满足设备提供的最大跳数H内实现网络的全连接，我们就称该网络是连通的。 本文利用连接矩阵的幂次方来判定网络的联通性。 由式(4)可知，CM 是一个对称矩阵，只需关注其主对角线以下部分即可。 当CM的下三角部分全为1 时说明该网络是连通的，即单次连通网络。 当CM 的h次幂CMh的下三角元素全非零，则该网络通过h次MESH 中继可以实现网络的全连通。 在图1 的例子中，CM3矩阵的下三角元素全部非零，因而图1 所示MESH 网络可以实现全连接。 如果直到h>H还没有出现满足要求的连接矩阵，则说明该网络是不连通的，需要跳出本次搜索重新求解。

图1 WiFi MESH 二维骨干网示意图

2 评价函数

根据广域环境下的应用需求，本文设定了三个求解目标，即网络覆盖率(f1)、网络通信质量(f2)和网络建设成本(f3)。

2.1 网络覆盖率

覆盖率是MESH 网络节点规划方案中最基础的一项指标，如何能够利用最少的节点数量达到最大化的网络覆盖面积一直是节点部署算法的求解重点[9]。 地图上某一点an与通信基站sk之间的距离可表示为:

如果dnk≤r，则点an在基站sk的覆盖范围内。令Nc为被覆盖节点的总数，则网络覆盖率可表示为:

由式(8)可知，f1≤1 恒成立。 当f1＝0 时，代表此时网络覆盖率近似为0；当f1＝1 时，代表此时覆盖率近似为100%。 所以f1的值应越大越好。

2.2 网络服务质量

本文借鉴无线网络的服务质量(QoS)评价指标体系，即丢包率、延迟、可用性和带宽等参数[10]。 在设置通信参数时本文会给出充分的冗余以保证其网络的传输带宽和丢包率，所以对于这两项评级参数可以不用考虑。 接下来，本节将从通信延迟和网络可用性两方面来对网络服务质量进行近似评价。

本文主要通过用户和通信基站间的通信链路距离来间接求解网络时延。 设dn，min为当前地点an与所有通信基站之间的最短距离，即:

此外，令dn，ave为当前地点an与所有通信基站之间的平均距离，即:

本文采用最短距离与平均距离的比值作为衡量网络时延的指标:

由式(10)和式(11)可知，f21≤1 恒成立，且f21的值越小则表明当前解对应的网络通信延迟越小。

网络通信链路的可用性，指的是用户与网络连接的可靠性。 考虑到本算法所应用的领域更多的是在广域三维环境中，应考虑尽可能地将通信基站建设在海拔较高地点，从而减少遮挡、提高网络通信链路的可用性。 令当前解中所有被选节点的Z坐标平均值为Zave，而集合AS中所有节点的Z坐标平均值为ZAS，则:

表示基站所处位置海拔指标。 虽然Zave与ZAS的值并没有固定的大小关系，但f22仍是个在1 附近徘徊的数值。 综上所述，网络整体服务质量的评价函数可写成:

由于代价函数f22越大，网络通信链路的可用性越高，因而式(13)中对其负数进行最小化。 此外，式(13)中引入了一个常数，虽然不影响最优解，却使得f2基本保持为正数。 由式(13)还可以看出，网络服务质量的两个方面具有同等地位。 如有需要，可以对其进行改变。

2.3 建设成本

建设成本是实际应用推广中的一个重要因素。本文主要利用节点部署个数即通信基站个数来反映网络建设成本，在求解过程中希望网络的建设成本能够在满足各种约束的条件下实现最小化，即:

应达到最小，其中Kmax是最大部署节点数。 由式(14)可知，f3≤1 恒成立，为了使建设成本最小化，则f3的值应该尽可能小。

2.4 多目标规划求解

综上所述，本章所要求解的实际问题转化为了一个多目标规划问题[11]，其常见求解方法有评价函数法[12]、约束法[13]和分层序列法[14]等。 通过综合可行性分析，本文选取了评价函数法。 评价函数法的一般求解方式又包括线性加权法[15]、理想点法、极大值极小值法等，本文选择线性加权法与理想值法相结合的方法对三个目标函数进行求解。 综合式(8)、式(13)和式(14)，MESH 网络节点部署问题的代价函数可以写为:

式中:α1，α2，α3为三个求解目标的权重系数，而f′1是网络覆盖率的理想值。 可以看出，当网络覆盖率f1越接近其理想值f′1时表明覆盖率的结果越接近理想覆盖率，所以f′1-f1的值越小越好，理想值f′1的选取可以根据实际需要进行更改。 权重系数可根据实际具体应用场合中各个代价函数的重要性进行选择。 本文仿真实验所使用的权重系数值均为三个目标函数通过各自的变化斜率来确定。

3 3D-Tabu 禁忌搜索算法

从式(15)可以看出，MESH 网络节点部署优化问题是一个NP-Hard 问题，难以求得最优解。 禁忌(Tabu)搜索算法[16]在解决此类问题时具有良好表现，因而本文结合应用场景的特殊三维地形和广域覆盖面积提出了一种改进的3D-Tabu 禁忌搜索算法。 传统的Tabu 搜索算法通常假设MESH 网络部署节点数目K已知。 而本文提出的改进3D-Tabu 搜索算法从输入地图信息到求解出基站节点的部署方案都由算法自主抉择。

改进3D-Tabu 搜索算法流程如图2 所示，具体步骤可概括为:

Step 1 载入数据集AS、通信设备参数R和r。根据集合AS 求出部署区域的总长度L和总宽度W。 由于部署节点总数K为未知量，因而本文基于实际问题规模来求解节点部署的最优个数。 实际问题规模可表示为(Kmin，Kmax)，其中

图2 3D-Tabu 禁忌搜索算法流程图

式中:f1，min和f1，max分别表示网络覆盖率的上下限值，可以根据实际需求进行调整。 初始化K＝Kmin。 候选节点集合CS 的节点数M＝β×Kmax，β是可调节常数，通常大于1，本文平衡算法复杂度和性能，取β＝5。 求出CS，并选择K个站址作为初始部署方案。

Step 2 清空禁忌列表并初始化循环次数指针it

Step 3 初始化邻域次数指针i。

Step 4 寻找邻域解并判断当前邻域是否在禁忌列表里。 如是，则执行Step 5；反之，判断该邻域解是否是连通网络且更优。 如是，更新最优解与禁忌列表并执行Step 5；反之，直接执行Step 5。

Step 5 邻域次数指针i＝i＋1。 如果i>imax，执行Step 6；反之，执行Step 4。

Step 6 循环次数it＝it＋1.如果it>itmax，执行Step 7；反之，执行Step 3。

Step 7K＝K＋1。 如果K>Kmax，搜索结束，从历史最优解列表中找出最优解；反之，在当前最优解基础上随机增加一个站址，并执行Step 2。

4 算法的实现

4.1 参数设计

图3 为本文选取的实验区域实景彩色点云图，面积大约为17 km2。 为了简化操作，以5 m 为间隔对整个地图进行了采样，并以采样点信息近似代表整个地图。 本文共抽样了N＝5 776 个点作为集合AS 的成员。 根据AS 和地图信息可得到Kmin＝42，Kmax＝84，M＝280。 采用K-Means 聚类方法对集合AS 聚类并选择聚类中心作为候选站址集合CS。

图3 试验场地实景彩色点云图

本文实验所用通信基站设备为亿波普天公司的ZoneFree 系列产品，其节点间最大跳数H＝10，最远通信范围R＝10 km，短距离覆盖半径为300 m。 考虑到300 m 的覆盖范围在17 km2的广域环境中实现100%全覆盖耗费的资金过于巨大，本文中给每个节点增加一个半径为1 000 m 的灰色区域作为缓冲地带。 若某节点处于缓冲地带中，则认为用户是可以在有限时间内移动进入到网络覆盖区域内，所以设定覆盖范围r＝1 300 m。

根据式(15)可知f1和f3都有其理想的评价值。对于f1，令f′1＝1，即理想覆盖率为100%；对于f3，令f′3＝Kmin/Kmax＝60%，即理想节点部署个数是K的最小值。 由于f2特殊的求解方式，f2并没有固定的参考值，也无法直接主观赋予其一定的期望值。 此外，f2曲线相对于K的变化斜率约等于0，即f2不随K的变化而有明显变化趋势。 因此，本文根据三个目标函数的变化曲线斜率确定权重系数时，只需要考虑f1和f3的权重制衡关系来改变评价函数中的权重系数即可，通过计算可以得到α1＝2.1，α2＝1，α3＝1。

4.2 仿真结果

基于本文提出的改进禁忌搜索方法，上述地区的最佳部署节点个数为63 个，最低评价值f＝1.43，三个评价函数的值分别为f1＝91.4%，f2＝49.7%，f3＝75%。

上述节点部署方案的3D 效果如图4 所示。 图中的球体表示每个部署节点以自身为中心，以半径r发出的短距离覆盖信号。 从图中可以看出二维俯视覆盖率达到90%以上，完全满足应用需求[17]。 为了验证本文所提3D-Tabu 搜索算法的性能，本文对比了基于遗传算法的节点部署搜索方法。 经过大约相同时间的搜索，遗传算法得到的总体评价函数值为f＝1.55，三个评价函数的值分别为f1＝85.9%，f2＝50.5%，f3＝75%。 对比可知，本文提出的搜索算法性能更优，收敛速度更快。

图4 部署方案三维渲染图

图5中的曲线表示本文所提算法的历史最低评价函数随着部署节点个数K的变化情况。 由该图可以看出，在节点个数增加的过程中，系统评价函数呈现先降低再升高的变化趋势。 由此可以看出，随着节点部署个数的不断增加，节点部署方案的性能向着最优解方向不断优化。 但当节点部署个数超过最优个数时，系统性能开始出现下降。

图5 评价函数历史最优值

图6是图5 中最优解对应的代价函数值变化图(K＝63)，其中波动较大且密集的曲线代表的是每次搜索的实时评价值，而波动较小且比较平缓的带圆圈曲线代表的是历史最小评价值，即当前最优解的历史评价值。 由该图可以看出，在搜索过程中评价值在不断变化，搜索过程中可以接受解决方案不如当前的次优解。 该搜索过程有助于跳出局部最优解进而搜索全局最优解，避免程序一直陷入局部最优解的限制。

图6 评价值收敛情况

4.3 对比分析

在上一节的仿真实验中，目标函数的权重系数由评价函数中三个目标评价函数的斜率决定。 本小节将考察权重系数的变化对系统性能的影响。 图7中的曲线分别表示α1＝1，α1＝2.1，和α1＝3 的最小代价函数值，而α2＝α3＝1。 当α1＝1 时，三个目标评价函数具有同等权重。 由于建设成本f2的值明显大于其他两个评价函数值，因而在整体评价函数中占主要影响成分。 随着K值的增加其对应的评价值呈单调递增趋势，代价函数在搜索过程中也不会出现向最优解收敛的情况，求出的最优解只会是K取最小值得情况。

图7 权重系数α1 对评价值的影响

图8 权重系数灵敏度

当α1＝2.1 时，此时总体评价函数是将三个子目标放在同等优先级进行求解的。 随着K值的增加，对应的评价函数值先减小再增大，代价函数在搜索过程中有向最优解收敛的情况，而求出的最优解是综合衡量三个子目标代价函数之后求出的综合最优解。

当α1＝3 时，评价函数值的变化趋势与α1＝2.1时相似。 然而由于α1相对于其他两个权重值过大，导致覆盖率在整个评价函数中所占比重过大。 在未达到全覆盖时，K值越大，相应的覆盖率也越大，因而α1＝3 时的最优解中K值较大。

通过仿真结果分析可以知道，当α1＝2.1 时，评价值的变化曲线是最理想的，所求出的最终解也是对三个子评价函数进行综合权衡后的最优解。

为了考察三个权重系数对系统性能的影响及其灵敏度，本文对多个不同权重系数的系统进行了仿真实验。 三个系数(α1，α2，α3)中的一个变化时，另外两个保持为1。 由图中可以看出α2对目标评价函数的影响最为剧烈，而α1的影响最慢。 因而本文在考虑综合性能时，令α1的值相对较大，达到三个要求的基本平衡。 在实际应用中我们可以参考具体的节点部署要求，设定三个权重系数的具体比例，以满足实际系统的需要。

5 结束语

本文主要提出了一种面向广域环境动态组网的智能化基站部署优化算法。 文中首先将节点部署问题抽象为一个数学优化模型，随后提出了一种改进的3D-Tabu 禁忌搜索算法，使其能够应用于广域三维环境，实现满足各种约束条件下的无人化自动部署。 此外，本文提出的综合评价机制可以根据不同的应用需求进行修改，可以方便地推广到不同的场景。 本算法还可以根据不同的应用场景提供符合条件的最优节点部署方案而无需预先定义节点个数。