蚁群算法在WSN节点定位算法中的应用*

俞志根 , 姚春风

(1.湖州职业技术学院 机电工程分院, 浙江 湖州 313000； 2.湖州市公安局 信息通讯处, 浙江 湖州 313000)

WSN(无线传感器网络)[1]技术是21世纪最为核心的先进技术之一，必将影响到人们生活的方方面面。目前它已经进入应用研究阶段，在应用中有待突破的关键技术有节点定位技术、节点资源管理及网络安全技术等，而节点定位问题是WSN应用中需要解决的一个最基本的问题，是近年来的研究热点。虽然，可用GPS全球定位系统进行节点定位，但由于GPS只适用于室外，且成本较高，对于室内的小型WSN自组网还是不适用的，而WSN正是大量的这种室内小型自组网，故大多数情况下用GPS进行节点定位并不适合。现在，WSN节点定位技术主要有基于测距的定位技术和无需测距的定位技术两大类。前者如三边测量法、三角测量法或最大似然估计法等；后者有质心法、凸规划算法、APIT算法等[2]，但定位精度都不高，相对定位误差很难达到±40 %以上。

本文基于三边测量定位技术[3]，在移动信标节点的移动路径优化上引入了蚁群算法，以获得一条沿发射位置移动的最佳路径。移动信标节点沿这一最佳路径移动时能使信标节点起到最好的无线信号发射效果，产生最大覆盖范围，让普通节点能更好地接收定位信号，获得与信标节点的距离参数，然后再由三边测量定位法等数学方法得到普通节点的空间位置，实现WSN节点的定位。由于用蚁群算法优化了移动路径，不仅减少了信标节点的数量，降低了节点能耗，而且大大提高了节点定位的精度，迭代次数70次时的相对定位误差就能达到10 %左右。

1 蚁群算法及其特点

1.1 蚁群算法的演进

1.1.1 蚂蚁系统 蚁群算法[4]最初是由意大利学者M.Dorigo于1991年提出的，是一种基于蚂蚁觅食习惯的新型优化算法，它引入人工蚂蚁的概念，利用信息素对行动路径进行最优控制。蚁群在寻找食物时依靠相互之间信息素的传递，实现了所有蚂蚁都走最短的路径到达目标地，其核心是最优路径的选择问题。后由意大利学者M.Dorigo、V.Maniezzo和A.Colomi进行深入研究，提出了基于蚂蚁觅食行为的优化算法，也称为第一代蚁群算法(蚂蚁系统)，主要有以下几个重要概念：

(1)转换概率。蚂蚁系统是一种概率寻优方法，蚂蚁通过留在路径上的信息素浓度，利用转换概率的高低来确定下一个路径方向的选择。转换概率由下式表示：

(1)

式中：τij(t)是路径节点i、j在时间t的信息素浓度，η(i,j)为期望值，是节点i、j间距的倒数，Jk(i)是节点i处的蚂蚁k没有访问过的临近节点的集合，α、β为两个系数，用以决定信息素浓度与距离间的相对重要性。

(2)信息素蒸发率。与蚁群觅食相似，蚁群留在地上的信息素具有挥发性，会越来越少。人工蚂蚁系统为了防止信息素的局部积聚，需要它不断地蒸发，以促使人工蚂蚁探索各种可能的路径。另外，是为了让人工蚂蚁对曾经取得的可行解经过设定时间后能及时遗忘，有利于获得新的更好的求解。当然，信息素蒸发太快将不利于获得求解经验，不利于人工蚂蚁系统的求解效率，因此，在人工蚂蚁系统中要设置适当的信息素蒸发率。

(3)节点信息素的更新。蚂蚁会在自己路过的地方留下一定的信息素，留有信息素的路径称为信息素路径，以与没有蚂蚁路过或信息素已经挥发的路径作出区分。人工蚂蚁系统需要对各个节点的信息素进行不断更新，以保持其寻优能力，各个节点信息素的更新公式为：

(2)

其中：τij(t+i)与τij(t)是节点i与j节点在时间t及t+1时的信息素浓度。

(3)

其中:Lk为蚂蚁k所走过路径L的总长度，Q为0到1之间的一个随机值，ρ为信息素蒸发系数，0<ρ<1。

1.1.2 蚁群系统 1996年，Dorigo和Gambardella又对蚂蚁系统作了进一步改进，形成了较为成熟的蚁群系统[5]。提出了状态转移规则、全局更新规则和局部信息素更新规则，使其在进行优化时更为合理。

在原蚂蚁系统中，人工蚂蚁采用随机比例规则，完全依靠转换概率来选择路径。而在蚁群系统中，人工蚂蚁依据状态转移规则，采取伪随机比例规则。这一决策规则具有双重功能：可以利用先验知识，也可以进行有倾向性的探索。状态转移规则的数学模型如下：

(4)

上式中：q和q0是[0-1]之间的随机取值参数；J为属于Jk(i)的某一节点，选择方式是由基于AS的转换概率随机选取的。

蚁群系统与原来的人工蚂蚁系统在全局更新上也有不同，原人工蚂蚁系统的全局更新规则每次会对所有人工蚂蚁都进行更新，因此，最优解的搜索效率较低。为了使人工蚂蚁的搜索行为很快集中到最优路径上来，新的蚁群系统全局更新规则规定每次循环后只对最优路径的信息素进行增强，这就使人工蚂蚁的搜索行为能够较快地集中到最优路径附近，从而提高蚁群算法的效率。蚁群算法的全局更新规则如(5)和(6)式：

τ(i,j)=(1-α)τ(i,j)+αΔτ(i,j)

(5)

(6)

(5)式中的α是一个根据蚁群系统特征给定的常数；(6)式中的Lgb是全局最优解的路径长度。

局部信息素更新规则是指在蚁群系统中，人工蚂蚁在构造路径的同时进行局部更新的规划，数学模型如(7)式：

τ(i,j)=(1-ρ)τ(i,j)+vτ0

(7)

(7)式中ρ是信息素的挥发系数，τ0是蚁群的实际信息素浓度，τ0=(NLnn)-1，N为系统节点总数，Lnn为求解的总路径距离。

1.2 蚁群算法的特点及应用

蚁群算法主要有以下几方面的特点：一是具有较强的鲁棒性。可应用于静态、动态等各种最佳路径的优化问题，且只需稍作修改，就可用于各种优化算法；二是能够进行分布式计算。因它是一种基于种群的进化算法，具有本质并行性，故能进行分布式计算；三是具有较强的融合性。蚁群算法很容易与其它各种启发式算法相融合，进一步提高算法的各种性能；四是蚁群算法具有很强的优化能力。因为算法中的正反馈原理有利于加快进化过程，且它是一种本质并行算法，不同个体之间不断进行信息交流和传递，因此，能更快地得到优化结果。

蚁群算法可应用于静态组合优化问题中的二次分配问题、车间任务调度问题、车辆路线问题[6]及动态组合优化中的有向连接网络和无连接网络系统路由问题，也可应用于求解连续空间优化问题，还可应用在管线敷设问题及机构同构判定问题等许多需要优化计算的场合。

2 用蚁群算法优化WSN节点定位算法的原理分析

WSN节点定位方法可分为基于测距和无需测距两大类[7]。前一种方法定位精度较高，但实现起来较复杂，成本较高，后一种反之。为了得到较高的定位精度，本文以第一类定位方法为基础研究引入蚁群优化算法，以进一步提高定位精度。

在基于测距的定位方法中，WSN中的节点分为普通节点和信标节点两类，一般可通过接收信号强度(RSSI)[8]测量普通节点到信标节点的距离或角度信息，再用三边测量法就可对普通节点进行定位[9]。信标节点的数量和布置对这种定位方法的定位精度有很大的影响，虽然，采用较多的信标节点能提高网络节点的定位精度，但会使成本上升。因此，本文根据文献[10]提出的基于移动信标进行节点定位的思想，为了得到信标节点的最佳移动路径，提出用三重优化覆盖的方法来选取最少的发射位置，并引入蚁群算法对信标移动路径进行优化，以获取最佳移动路径，从而实现WSN信标节点的数量和移动路径的最佳优化，以提高普通节点的定位精度。

3.1 移动信标发射位置、数量和坐标的计算

移动信标的发射位置、数量和坐标的计算可采用三边测量法并结合三重覆盖法进行，文献[11][12]对此进行了详细研究，算法模型和步骤如下：

当只考虑一重覆盖ROI(感兴趣区域)时，需要信标节点的发射位置数量由(8)式计算：

(8)

采用等距三重优化覆盖时由(9)式计算：

(9)

一般ROI形状为矩形，故可由ROI的各顶点坐标得到信标发射位置坐标，计算步骤是：

第一步，信标节点发射位置数量的计算，由(10)式计算每行中信标节点发射位置的数量，由(11)计算所需的信标节点行数，总数为两者的乘积；

第二步，信标节点发射位置坐标的计算，由(12)式计算奇数行的发射位置横坐标，(13)计算偶数行的发射位置横坐标，由(14)式计算纵坐标。

NodeNum_Line=A/r

(10)

(11)

Xij=(j-1)r

(12)

Xij=A-(J-1)r

(13)

(14)

式中A为ROI的长度，B为其宽，r为信号有效半径，i为行号，j列号。

3.2 蚁群算法对移动信标移动路径的优化

在得到了ROI中的移动信标发射位置和数量后，最重要的问题是如何使移动信标的移动路径最合理高效，为此，可引入蚁群算法对移动路径进行最优化，以获得最佳移动路径。可采用蚁群算法中的TSP问题求解方法，将WSN中的移动信标节点当成是TSP问题中的城市，进行旅行路径优化，算法流程为：

第一步：系统初始化

设NC=0；设置路径(r，s)的信息素浓度初值：τ(r，s)=τ0，Δτ(r，s)=0；m只蚂蚁在n个信标节点上随机布置，禁忌表置空：tabuk=φ；

第二：最佳路径的求解

二是真抓实干，求真务实。一抓经营模式，巩固农资经营基础。二抓项目建设，增强企业发展动力。三抓融资渠道，增加资金供给规模。四抓应收账款，保障资金运行安全。五抓风险防控，坚守安全发展底线。要加强风险管控，在集团管控上要创新管理模式，规范管理行为。在基础管理上要照章办事，认真贯彻落实。在风险管理上要做到准确识别、科学研判、有效控制风险。在全面预算管理上要做到“先算后花，先算后干，过程监控，结果考核”，提高企业运行的质量。

for(i=1；i≤n；i++)

for(k=l；k≤m；k++){

将蚂蚁k所在的初始传感节点添加到tabuk中；

If(k未完成指定任务且tabuk未满)

第三步 全局更新

for(k=l；k≤m；k++)

{

If(N次迭代最优解无明显改进)

{按式(4)更新ρ值；}

按式(5)、(6)对最优路径进行全局更新；

}

第四步 输出最优解

If(不满足终止条件){清空所有k的禁忌表；对每条路径(r，s)，置Δτ(r，s)=0；且Nc=Nc+l；返回第二步；}

否则 返回最优解；

通过这一算法就可得到一条经过优化了的信标节点移动路径，信标节点按照这条路径移动到每一个信号发射点，普通节点通过RSSI技术测得与信标节点之间的距离，然后使用三边测量定位法即可定位普通节点，这种新的WSN节点定位方法称为基于蚁群算法的WSN节点定位方法。

3 基于蚁群算法的WSN节点定位仿真试验

为了验证以上的路径优化算法，本文建立了一个由200个节点组成的仿真WSN，先用等距三重优化算法获得移动信标发射位置的数量和坐标后，引入蚁群算法对移动路径进行优化，并将信标节点的移动路径设定为经优化后的最优路径移动，最后，普通节点的位置由三边测量算法获得，仿真结果表明，信标节点沿经蚁群算法优化后的最佳路径移动能提高普通节点的定位精度，使定位的相对误差控制在15 %以内。具体的仿真过程如下：

3.1 仿真参数设定

仿真试验参数设定：WSN节点总数设为200个，均布在15×15的正方形网格区域内；信标节点密度φ=12.5%，即信标节点数目Nanchor=25，普通节点数Nnon-anchor=175。节点随机分布在规定区域内；节点的通信半径R=2.0，网络连通度connectivity=12.2；另外，设定未知节点具有测量自身到邻节点距离的能力，且测距无误差；而且，所有节点在布撒之后均不作移动。

仿真工具用MATLAB9.0版软件，在高配计算机(2G内存，双核PⅣ)上进行仿真运算，蚁群算法参数的取值如下：蚂蚁数目K=10N，初始步长λ(0)=0.1；步长缩减系数ξ=0.96；信息素浓度设为τ0=0.15，挥发率设为ρ=0.618；迭代60次后将重新初始化信息素浓度。这些参数的设置还缺乏严格的理论依据，只能由经验取得。

3.2 仿真结果分析

具体的仿真结果如图1，图中的实心正方形表示信标节点，共有25个；空心圆表示普通节点的实际位置，共有170个；星形表示经过蚁群算法优化后得到的普通节点的计算位置。由图可知，经蚁群算法优化后能比较准确地计算出大部分普通节点的位置，证明蚁群算法在WSN节点定位中能起到提高定位精确度的作用，是一种较有前途的定位算法新方法。

图2是节点定位误差及其标准差与算法迭代次数之间的关系曲线，由图可知，在10次迭代次数以前，定位误差及其标准差下降，说明这种优化算法具有良好的收敛性。当对定位精度要求不高时，可适当减少迭代次数，以缩短算法运行时间。在前述仿真参数条件和机器配置下，算法运行时间在60分钟以内。如要获得较高的定位精度，则需要较多的迭代次数，由图可知，迭代次数60次时的相对定位误差为10%，能满足大多数WSN的定位要求。

图1 算法结束时节点实际位置与估计位置示意图 图2 定位误差及其标准差与迭代次数的关系

4 结 语

通过在WSN节点的三边测量定位算法中引入蚁群算法，对移动信标节点的移动路径进行优化，建立了蚁群算法模型和流程。并在15×15的区域内分布200个WSN节点的条件下进行了仿真试验研究，结果表明这是一种更加有效的WSN节点定位算法，能使WSN节点定位相对误差提高到10%以内，具有良好的应用前景。

参考文献：

[1] Ren F.Wireless Sensor Networks[J].Journal of Software,2003,14,(7):1282-1291.

[2] Bulusu N. Heidemann J, Estrin D.GPS2 Less Low Cost Outdoor Localization for Very Small Devices[J].IEEE Personal Communications, 2000,7,(5):28-34.

[3] Niculescu D, Nath B.DV Based Positioning in Ad Hoc Networks[J].Journal of Telecommunication Systems, 2003,22,(l):267-268.

[4] 马 良,项培军.蚂蚁算法在组合优化中的应用[J].管理科学学报,2001,4(2):32-36.

[5] Akyildiz I F, Su W, Sankarasubramaniam Y, et al.Wireless Sensor Network:A Survey[J].Computer Networks, 2003, 38(4):393-422.

[6] 侯立文,蒋馥.一种基于蚂蚁算法的交通分配方法及其应用[J].上海交通大学学报,2001,35,(6):486- 490.

[7] Wang FB, Shi L, Ren FY.Self-localization Systems and Algorithms for Wireless Sensor Networks[J].Journal of Software, 2005,16(5):857-868.

[8] 杜 敏.基于RSSI的无线传感器网络定位技术研究及应用[D].长沙:湖南大学出版社,2009:23.

[9] Niculescu D, Nath B.Position and Orientation in Ad Hoe Networks[J].Ad Hoe Networks, 2004,2(2):133-151.

[10] Sichitiu ML, Ramadurai V.Localization of Wireless sensor Networks with a Mobile Beacon[A].In: Proc.Of the IEEE Int’l Conf. on Mobile Ad-hoe and Sensor Systems[C].IEEE Computer Society, 2004:174-183.

[11] Zhang HH, Hou JC.Maintaining Sensing Coverage and Connectivity in Large Sensor Networks[J].Wireless Ad Hoe and Sensor Networks, 2005,l(1):89-93.

[12] 李石坚,徐从富,杨旸,等.面向传感器节点定位的移动信标路径获取[J].软件学报,2008,19(2):455-467.