基于蚁群算法的WSNs 节点有障环境中部署优化研究*

樊宽刚，么晓康，苏建华

(1.江西理工大学 机电工程学院，江西 赣州341000;2.中国科学院 自动化研究所 复杂系统与智能科学国家重点实验室，北京100190)

0 引 言

如何有效利用能量是无线传感器网络(wireless sensor networks，WSNs)研究关键问题之一［1］。为节约节点能量，许多研究者针对WSNs 能耗展开研究。文献［2］提出利用收集数据转发路径最短和有效数据时空相关感知收集算法。文献［3］提出构建感知方向使网络寿命最大化多项式时间算法和有效延长网络寿命圆周生成算法。文献［4］提出基于数据获取效率为评价网络标准的桥梁监测WSNs 节点布置方法。文献［5］设计自供电低功耗无线传感器节点并提出均匀分簇自适应路由协议。文献［6］提出基于网格和虚拟力导向蚁群算法高效路由策略。文献［7］提出在农田传感网络中计算无线节点最佳传输半径计算方法。上述文献主要研究WSNs 路由算法，能量控制策略或自供电等来实现无线节点能量供给优化。但上述没有具体研究WSNs 节点有障碍物情况下节点静态部署问题。

本文根据上述节点部署不足之处，针对WSNs 节点在有障碍物二维地理环境中静态位置优化问题，在建立无线信道衰减模型基础上，提出一种基于Dijkstra 算法和蚁群算法相结合的WSNs 节点静态优化部署策略。

1 工程背景

根据部署无线传感节点实际环境，本文提出两种有障碍部署环境。一种是狭长弯曲空间(图1(a))，一种是障碍物块状分散构成空间(图1(b))，图1(a)有障环境主要解决节点部署位置是近似共面狭长空间节点部署优化问题，如矿井巷道、隧道以及高楼林立弯曲街道等。图1(b)有障环境主要为解决节点部署位置平面上阻挡物为不连续块状空间节点部署优化问题，如多栋散状分布高楼、矿井工作面巷道复杂多交叉处等。

图1 节点部署环境Fig 1 Environment of node deployment

2 无线信道能耗衰减模型

本文将按梯度层次场数据传递［8］引入WSNs，同时给出假设:1)所有节点同构，部署前有相同能量，部署后固定;2)节点有相同传输半径;3)位置坐标测量可得;4)节点采用多跳方式通信;5)采用等距布置。

Heinzelman W B 等人提出了无线信道能耗自由空间和多路径衰减模型［9］。基于理论和测试的无线信号传播模型，信道平均接收信号功率随距离变化呈对数衰减。对于任意发射机和接收机距离，平均大尺度路径损耗［9］如公式(1)所示

式中 n 为路径损耗指数，体现距离长度对路径损耗影响程度。建筑物内视距传播路径损耗指数［10］n=1.6～1.8，数值计算取n=1.7，则

式中 ERec(k，d)，ETrd(k，d)为在收、发距离为d 时传输k比特数据能耗，Eelec为一个比特数据在无线传感器节点中进行信号数字编码调制电子器件所消耗能量，εfx为距离衰减放大器系数，d0为收发能耗判断阈值，表示为

式中 L 为无线传输损耗，hTrd，hRec为发送和接收天线高度，λ 为电磁波波长。设Edata为一个节点融合单位比特需要能量，则经过特定节点转发融合m 个节点k 比特需要能量为

网络节点总跳数Hsum－L和各个节点梯度层次数Li关系如下

其中，N 为网络节点数。由式(2)～式(5)得无线传感节点信道能耗衰减两个模型:

1)当R≤d0时，不考虑数据融合，链上所有传感器给簇首发送y 比特数据能耗Ef

2)当R≤d0时，考虑数据融合，一次传感网内完全融合压缩所需能量E，式(7)中yh和yd分别为包头、数据比特数

3 WSNs 节点静态部署策略

3.1 节点静态部署策略实现步骤

1)对WSNs 节点部署环境简化拆分。2)部署环境平面图，建立相应信道衰减模型。3)利用无线信道衰减模型确定传输半径。4)对类似图1 节点部署环境，进行相邻线段可视分割(如图2(a))和MAKLINK 图形［11］分割(如图2(b))，运用蚁群算法和Dijkstra 算法［12］进行仿真计算。5)分析仿真结果，确定节点个数，进行节点实际部署。

图2 图形分割方法Fig 2 Partition method of figure

3.2 基于蚁群算法的静态WSNs 节点部署

本文选用属于蚁群优化(ant colony optimization，ACO)算法的蚁周系统［13］。

1)评价函数:线传感节点在有碍环境中优化部署，最终目标是减少WSNs 通信能耗，实际为达到节点通信路径最短，因此，选爬行路程长度作为评价参数，建立评价函数为

式中 n 为总行走步数，ek蚂蚁第k 步选择节点，dekek+1为蚂蚁走过相邻点间路径长度。

2)概率选择策略:蚂蚁选择下一点采用伪随机比例规则，则一只位于i 点蚂蚁选择下一个节点j 的选择转移规则如下

式中 allowedk为蚂蚁k 下一步允许选择点集合，α 和β 分别反映蚂蚁爬行过程中所积累信息素和启发信息相对重要性，τ(i，u)为边(i，u)上信息素强度，η(i，u)为边(i，u)能见度，q 为［0，1］区间均匀分布随机数，q0为参数(0≤q0≤1)，J 为根据方程式(9)给出概率分布选出一个随机变量，)为蚂蚁k 转移概率，j 为未经过节点。

3)禁忌判断规则禁忌向量实现，防止蚂蚁重复过点。

4)信息素更新策略:在蚁周系统中，信息素更新公式(11)给出

式中 Δτij(t+n)为在时刻(t，t+n)的循环中路径(i，j)的信息素的增量，ρ 为信息素蒸发系数。算法流程如图3。

图3 ACO 算法节点路径部署优化流程图Fig 3 Flow chart of node path deployment optimization based on ACO algorithm

4 仿真实验与分析

4.1 对于图1(a)环境的仿真

部署环境中网络相邻节点之间距离l 最大35 m，频段2.4 GHz，参数设置L=1，hTra=0.4 m，hRec=0.4 m，得d0=40.192 m。对式(6)和式(7)参数值如表1。坐标范围162 m×162 m。传感器节点坐标(7，16)m，簇首坐标(73，162)m。对图进行相邻线段可视分割并对图每个线段进行最小0.25 m 分割，获取分割点坐标。生成具有禁忌作用距离权值矩阵，用Matlab 编写程序。蚁群算法参数设置:α=1，β=2，ρ=0.3，Q=30，k=100，m=30，q0=0.85。

表1 能耗模型参数值Tab 1 Parameters of energy consumption model

从图4 中可得所提ACO 算法优化效果较好。从图5 中可得基于蚁群算法收敛性良好，能很好解决这类问题。将中心线位置部署和蚁群算法优化部署进行比较，由表2，相比普通位置部署，蚁群算法优化后，在传输能耗上节约18.23%。

图4 节点在狭长空间中部署线路图Fig 4 Path of node deployment in long and narrow space

图5 蚁群算法平均路线长度收敛曲线Fig 5 Convergence curve of average path length of ACO algorithm

表2 普通部署和ACO 算法优化部署对比Tab 2 Contrast between common deployment and optimized deployment of ACO algorithm

4.2 对于图1(b)环境节点部署仿真

仿真坐标范围为165 m×165 m。传感器节点坐标(155.5，7)m，簇首坐标(11.5，148)m。对有障碍物空间进行MAKLINK 图论方法分割。使用Dijkstra 算法在可行性路径基础上再次优化WSNs 节点部署位置线路图(如图6)。使用蚁群算法在Dijkstra 优化基础上更进一步优化蚁群算法，参数设置:α=1，β=5，ρ=0.3，Q=30，k=300，m=30，q0=0.88。通过仿真计算求得Dijkstra 算法解为226.12 m，通过蚁群算法得评价函数的解w=213.881 3 m。从图7 可以看出优化结果更好，图8 表明此算法收敛性良好。从表3 中可以看出:Dijkstra 与蚁群算法结合比直接使用Dijkstra 算法在路径长度上有5.41%提高，在传输能耗上有0.32%节约。表2 和表3 说明通过此优化策略可以达到WSNs 节点的更好的部署，并达到节约能耗目的。

图6 Dijkstra 算法节点部署初步规划线路Fig 6 Initial planning route of node deployment based on Dijkstra algorithm

图7 基于Dijkstra-ACO 算法的节点部署线路图Fig 7 Path graph of node deployment based on Dijkstra-ACO algorithm

图8 Dijkstra-ACO 算法平均路线长度收敛曲线Fig 8 Convergence curve of average path length based on Dijkstra-ACO algorithm

5 结 论

本文主要研究WSNs 节点在有障碍物环境中优化部署方案，提出了一种基于无线信道能耗衰减模型、蚁群算法和Dijkstra 算法的无线传感节点在有障环境中具体优化部署新方法。能很好实现节点部署线路规划设计，达到了节约WSNs 能量目的。该方法具有较好的实践应用领域，可将两种有障简化模型综合应用于矿井巷道、公路铁路隧道、狭长山谷、大型建筑物等的等水平无线传感器节点部署优化。

表3 Dijkstra 和Dijkstra-ACO 优化部署结果对比Tab 3 Results contrast of optimized deployment by Dijkstra and Dijkstra-ACO algorithm

［1］ 王 雪，丁 梁，王 晟，等.层次分簇的无线传感网络多级优化测量［J］.机械工程学报，2009(4):1－7.

［2］ Villas L A，Boukerche A，GuidoniD L，et al.An energy－aware spatio－temporal correlation mechanism to perform efficient data collection in wireless sensor networks［J］.Computer Communications，2013，36:1054－1066.

［3］ André Rossi，Alok Singh，Marc Sevaux.Lifetime maximization in wireless directional sensor network［J］.European Journal of Operational Research，2013，231:229－241.

［4］ 周广东，李爱群.大跨桥梁监测无线传感网络节点布置方法研究［J］.振动工程学报，2011(4):405－411.

［5］ 吴 寅.采用环境能量的自供电WSNs 关键技术研究［D］.南京:南京航空航天大学，2013:2－10.

［6］ 朱绍文，纪志成，王 艳，等.基于Grid－VFACO 的数字化车间WSNs 路由算法［J］.传感器与微系统，2014，33(1):134－136.

［7］ 肖德琴，王景利，罗锡文.大规模农田传感器网络通信能耗模型［J］.计算机科学，2009(8):75－78.

［8］ 朱红松，孙利民，徐勇军，等.基于精细化梯度的WSNs 汇聚机制及分析［J］.软件学报，2007(5):1138－1151.

［9］ Heinzelman W B，Chandrakasan Anantha P，Balakrishnan Hari.An application－specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660－670.

［10］拉帕波特.无线通信原理与应用［M］.北京:电子工业出版社，2012:95－113.

［11］Tan Guanzheng，He Huan，Sloman A.Ant colony system algorithm for real－time globally optimal path planning of mobile robot－s［J］.Acta Automatica Sinica，2007，33(3):279－285.

［12］樊平毅.网络信息论［M］.北京:清华大学出版社，2009:48－50.

［13］Dorigo M，Maniezzo V，Colorni A.Positive feedback as a search strategy［R］.Italy:IRIDIA，Politecnico di Milano，1991.