基于多目标优化函数的无线传感器网络负载均衡路由协议

张 健

(安徽三联学院 计算机工程学院，安徽 合肥 230001)

基于多目标优化函数的无线传感器网络负载均衡路由协议

张 健

(安徽三联学院 计算机工程学院，安徽 合肥 230001)

针对目前无线传感器网络路由协议在延长网络生存期和提高网络整体性能等方面存在的缺陷，以平衡网络中节点能量消耗、延长网络生存期为优化目标，提出了一种基于多目标优化函数路由协议。该协议将节点可用能量、路由跳数和节点之间物理距离等参数引入到路由选择函数中，以实现最优路径的建立和对无线传感器网络性能的综合优化。NS2仿真结果表明，与传统的定向扩散协议相比，数据发送成功率提高了15.3%，网络能量利用率提升了9.7%，网络生存期延长约12%，在无线传感器网络中具有显著的优越性。

无线传感器网络；多目标优化函数；能量效率；路由跳数；网络生存期

无线传感器网络[1]是由大量传感器节点组成的无线自组织网络，是当前国内外备受关注的新兴研究领域。由于无线传感器网络节点的自身特性使得对协议的制定提出了很大的挑战，提高节点能量效率是研究人员设计协议的首要目的[2]。本文提出一种以平衡网络中节点能量消耗、延长网络生存期等为优化目标的多优化函数路由协议。该协议将节点之间物理距离、节点到源节点的路由跳数和节点当前可用能量等变量引入到路由选择函数中，以实现最优路径的建立，并针对无线信道的特点在数据传输过程中应用了功率控制技术，从而提高了整个网络性能的稳定性，实现了对无线传感器网络性能的综合优化[3]。

1 无线传感器网络覆盖感知模型

本研究构建的无线传感器网络覆盖感知模型包括无线传感器网络覆盖技术和网络模型，其中无线传感器网络所研究的覆盖技术的目的：

(1)使待监测区域中的每一个节点都至少在一个传感器节点的覆盖范围内。

(2)在保证覆盖要求的基础上，同时减少网络节点消耗、延长网络寿命。

网络模型假定：V是所有传感器节点的集合，L是网络中逻辑链路的集合构成一个无向连通图G=(V，L)； 触发事件发生时，覆盖区域内被唤醒的节点集合S，显然有S⊂V； 为将无向连通图G变成双向连通，需对节点之间形成的边进行增删。

文中采用的符号说明如下。

H(i)：覆盖区域内节点i到达源节点s的跳数；N-(i)：覆盖区域内节点i的上一跳邻居集合，即任给j∈N-(i)，有H(j)=H(i)-1；N+(i)：覆盖区域内节点的下一跳邻居集合，即任给j∈N+(i)，有H(j)=H(i)+1；D(i,j)：覆盖区域内节点i和节点j之间的物理距离；E(j)：覆盖区域内节点j的当前可用能量；Q(i,j)：覆盖区域内节点i和节点j之间链路的质量函数，该值越大，链路质量越好；L(i)：覆盖区域内节点i最优上一跳矢量，方向指向上一跳节点N-(i)，大小为两者之间的物理距离。

假设给定G=(V,L)，S和基站B，问题抽象为如何在触发事件源位置和基站B之间寻找最优路径及数据采用何传输方式，以确保数据传输可靠性、提高能量效率，进而延长网络生存期[4]。

2 多目标优化函数路由协议设计

针对传统协议的不足，设计了多目标优化函数路由协议。下面将详细介绍源节点选取和最优路径建立的过程。

2.1 源节点的选取机制

当某个触发事件发生时，覆盖区域内被唤醒的节点集合S形成后，源节点的选取步骤如下：

(1)事件源发生后，S中的节点会广播标示本节点ID和信号强度值的简短报文。信号强度的大小可由节点的传感器模块获知。

(2)S中的每个节点将接收到的简短报文中的信号强度值和自己信号强度值进行比较。如果节点接收到的信号强度值小于自己的信号强度值，则该节点继续广播标示自己的ID和信号强度值的简短报文，反之，该节点停止广播自己的简短报文。经过一段时间后，感知到最强信号的节点不再收到标示更强信号强度的报文，这时该节点被选作源节点s[4-5]。

2.2 最优路径的建立过程

本协议中，最优路径是源节点s在网络中通过扩散探测报文逐跳建立起来；然后基站B通过增强包向源节点s反向确认后，最优路径才最终建立起来[4,6]。

(1)广播探测报文。源节点s在网络中通过广播方式扩散初始探测报文， 其IP报文头部格式如表1所示。

表1 初始探测报文IP报文头部格式

TTL为报文的生存时间，即路径的最大跳数长度，报文每经过一次转发，TTL值减1[4,7]。

从源节点s接收到初始探测报文后，任一中转节点i(非基站)将自己的ID、到源节点的跳数、可用能量等信息添加在初始探测报文的附加IP头部内，生成扩展探测报文，其IP报文头部格式如表2所示。

表2 扩展探测报文的IP报文头部格式

在完成估测D(i,s)后，中转节点i将生成的扩展探测报文转发给下一跳邻居节点，下一跳邻居节点在接收到扩展探测报文后也要生成自己的扩展探测报文和估测到源节点s物理距离，然后再向下一跳节点转发其扩展探测报文，以此类推，直到报文转发到基站B或者转发失败[9]。

(2)建立最优路径。下一跳节点在收到上一跳节点转发过来的扩展探测报文后，就获得了上一跳节点的信息和物理距离大小。因此最优上一跳矢量L(i)可以通过下一跳节点来综合比较其上一跳邻居节点的信息和物理距离大小来获得[10-11]，也可以通过链路的质量函数Q(i,j)最大值来确定路径中的每个节点的最优上一跳矢量。

因此，通过最优上一跳矢量的确定和扩展探测报文的逐跳传输完成，网络中的最优路径初步建立起来。

(3)增强最优路径。当从源节点s基站B的最优路径建立后，基站B沿着最优路径反向向上一跳邻居节点以较小的时间间隔周期性地转发增强包。同样，最优路径上的任一节点i将其增强包转发给最优上一跳节点，任一节点i的增强包IP报文头部格式如表3，增强包中SNRi表示节点i希望最优上一跳节点发送给自己的信噪比的值，信噪比越大，表明信道状态越好。当源节点s接收到最优下一跳节点转发来的增强包后，最优路径最终确立[14-15]。

表3 增强包IP报文头部格式

(4)功率控制技术。最优路径最终确立后，节点之间进行数据转发。本协议较之传统路由协议，优点主要体现在节点的发送功率不是恒定不变，而是随着信道状态的改变而改变，以提高数据传输的能量效率。信道状态与发送功率大小成反比关系，即当信道状态较好时，节点降低发送功率以减少能耗；反之，节点提高发送功率以确保数据传输可靠性。其实，在增强包中所包含的节点所期望的信噪比等信息是实现功率控制的重要参数。考虑无线信道的特性，节点在周期性地收到增强包后会更新自己的发送功率大小[16]。

3 协议仿真

使用NS2(NetworkSimulatorversion2，ns-allinone-2.34)仿真该协议和定向扩散路由协议[10]，并从数据发送成功率、节点当前可用能量、节点死亡比率3方面进行比较和性能分析。

仿真场景设计采取在300m×300m的网络覆盖面积，设置了30个传输半径为100m的传感器节点。当路由事件发生时，首先采取源节点选取机制选定源节点，该源节点周期性地(源节点等待时间为60s)广播探测报文(70B)，仿真时间进行500s。

(1)数据包发送成功率分析

从图1中可以看出，多目标优化函数路由协议的数据包发送成功率一直高于定向扩散路由协议。通过计算可以得到多优化函数的端到端数据包发送成功率可以比定向扩散协议高出15.3%。一方面，由于链路的质量函数Q的应用，使得节点之间的物理距离D(i,j)减小，有利于提高节点之间的数据发送成功率；另一方面，功率控制技术的应用，对信道状态较差时，调整数据发送功率，有利于提高节点间的数据发送成功率。

(2)网络可用能量分析

图2仿真结果显示随着网络运行时间的推移，网络的可用能量随之减少。在多目标优化函数协议和定向扩散协议中，同一个触发事件均可以唤醒多个节点，在被唤醒节点数量较少时，多目标优化函数的源选取机制并不明显。随着时间推移，当被唤醒节点数量达到一定数值时，多目标优化函数协议发送的探测报文比定向扩散协议发送的少很多，有效地实现了节能，网络能量利用率提升9.7%。

(3)网络死亡节点比率分析

图3仿真结果显示，随着时间的推移，多目标优化函数路由协议的节点死亡比率明显小于定向扩散协议，特别是在采用功率控制技术，使得网络生存期延长约12%。因为功率控制技术有效的减少了数据传输过程中的能量消耗，从而延长网络生存期。

4 总结

本文提出了一种多目标优化函数的无线传感网络负载均衡路由协议。该协议将节点可用能量、路由跳数和节点之间物理距离等参数引入到路由选择函数中，以实现最优路径的建立，实现了对无线传感器网络性能的综合优化，并采用了功率控制技术，有效地提高了数据传输过程中的能量效率，达到网络整体性能优化。通过仿真实验，证明了本文提出的优化算法与传统定向扩散算法相比，在平衡网络能量消耗和延长网络生存期方面更优。下一步工作可以围绕路由协议的服务质量支持和降低算法的复杂度来开展，在降低能量消耗和服务质量间达到平衡，实现全局最优路由策略。

[1]S. H. Kim. Location-free semi-directional flooding for on-demand routing in low-rate wireless mesh networks[C]. Proc. of the 20th International Conference on Computer Communications and Networks: IEEE Press, 2011.

[2] 冯维. 基于离子群算法求解多目标函数优化[D]. 长春: 吉林大学, 2010.

[3] T. F. Shih, H. C. Yen. Location-aware routing protocol with dynamic adaptation of request zone for mobile ad hoc networks[J]. Wireless Networks, 2008, 14(1): 321-333.

[4] 周晓芳. 无线传感器网络中路由协议的跨层设计研究[D]. 合肥: 中国科学技术大学, 2010.

[5] K. K. Lee, S. H. Kim, H. S. Park. An effective broadcast strategy for route discovery in the zigBee network[C]. Proc. of the 10th International Conference on Advanced Communication Technology: IEEE Press, 2008.

[6] 陈乐瑞, 孔金生. 基于改进遗传算法的网络路由优化研究[J]. 计算机应用与软件, 2013, 30(4): 135-137.

[7] 周晓芳, 屈玉贵. 一种基于多优化函数的跨层定向扩散路由协议[J]. 中国科学技术大学学报, 2009, 39(8): 798-803.

[8] 陶志勇, 路笋．基于ZigBee的修正加权质心定位算法研究与实现[J]. 计算机应用与软件, 2014, 31(1): 123-126．

[9] 张培军, 李晓霞, 姬志强. 基于MATLAB遗传工具箱的多目标函数优化[J]. 航海工程, 2009, 38(1): 49-51.

[10] 许建真, 姚丽洁, 袁桂敏．一种基于LEACH协议的簇头选择改进算法[J]．计算机应用与软件, 2012, 29(11): 262-263, 268．

[11] 王淑华，陈国定，赵国炳．一种无线传感器网络能耗模型及有效性分析[J]．计算机应用与软件，2011，28(2)：215-217．

[12] 张俊虎, 彭辉, 邵峰晶．移动传感器网络路由协议的多跳数据传输及能耗性能分析[J]. 计算机应用与软件, 2011, 28(11): 202-206．

[13] 杨云, 李斌, 高峰, 等．无线传感器网络簇内优化的最小跳数路由算法[J]．计算机应用与软件, 2010, 27(2): 31-46．

[14] 刘少卿. 无线传感器网络负载均衡路由协议研究[D]. 镇江: 江苏大学, 2010.

[15] 任建华，李元诚，杨洪. 基于路径宽度的Zigbee网络路由算法优化[J]. 计算机工程，2014, 40(1): 117-120.

Load Balancing Routing Protocol for Wireless Sensor Networks Based on Multi-object Optimization Function

ZHANG Jian

(School of Computer Engineering, Anhui Sanlian University, Hefei 230001, China)

To avoid the deficiencies of present wireless sensor network routing Protocol in extending network lifetime and improving network performance, a routing algorithm based on multi-object optimization functions is proposed to achieve the optimization goals of balancing network node energy consumption and extending network lifetime. Optimum path is set up by introducing parameters like available energy of nodes, routing hops and physical distance between nodes into routing selection function. In this way, the integrated optimization of wireless sensor network performance is achieved. We conduct a NS2 emulation experiment and the result shows, our proposed algorithm have achieved higher transmission reliability, lower energy consumption and much longer network lifetime. Compared with traditional directed diffusion algorithms, the rate of data transmission success raises by 15.3%, utilization ratio of network energy by 9.7%, and network lifetime by 12%. Generally our proposed method has more advantages in wireless sensor networks.

wireless sensor networks, multi-object optimization functions, energy efficiency, routing hops, network lifetime

2015-03-05

安徽省教育厅高等学校省级自然科研项目(KJ2013B090)。

张健，男，安徽泗县人，硕士，安徽三联学院计算机工程学院讲师，研究方向为无线传感器网络。

时间：2016-1-5 13:01 网络出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160105.1301.009.html

TP301.6

A

1007-4260(2015)04-0033-04

10.13757/j.cnki.cn34-1150/n.2015.04.009