基于加权路由思想的无线自组织网络生存时间优化算法研究*

刘半藤,周 莹,陈友荣

(1.浙江树人大学信息科技学院,杭州 310015;2.浙江大学控制学院,杭州 310058)



基于加权路由思想的无线自组织网络生存时间优化算法研究*

刘半藤1,2*,周 莹1,陈友荣1

(1.浙江树人大学信息科技学院,杭州 310015;2.浙江大学控制学院,杭州 310058)

在无线自组织网络中,网络生存时间是衡量网络性能的重要指标之一。分析影响网络生存时间的众多因素后,提出了一种工作量加权路由模型以提高无线自组织网络的生存时间。在网络信息传输的过程中,综合每条链路的业务工作量对网络链路进行加权,建立距离加权传输数学模型。该模型通过降低工作较为繁忙节点的信息转发概率,从而到达均衡节点能耗的目的。最后,采用MATLAB进行数值仿真,结果显示本文提出的路由算法可以有效延迟网络生存时间,均衡网络节点的能耗。

生存时间;瓶颈节点;路由策略

无线自组织网络是一种不需要固定设备支持的新型无线通信网络。网络中各节点即用户终端自行组网,非邻接两节点间的通信依靠其他节点的转发实现,从而组成一个多跳无线网络。由于无线自组织网络具有高度的灵活性、抗毁性等,使得无线自组织网络在抢险救灾、战场监控、环境监测、医疗卫生等领域具有重要的实用价值和广阔的应用前景[1]。由于无线自组织网络中的节点通常采用电池来供应能量。在实际应用中,节点电源在一段时间内不可更新,从而使得网络的生存时间与节点的能量消耗密切相关。因此,设计一种算法均衡整个网络能量消耗,延长网络生存时间显得至关重要。文献[2]提出,可以将网络生存时间定义为从网络初始时刻开始到网络中第1个节点由于能量耗尽退出网络时刻为止所经历的时间。文献[3]中,作者指出网络能耗与网络路由策略息息相关,通过恰当地设置路由策略搜索准则可以降低网络能耗,提高网络生存时间。

近年来,国内外专家学者针对能量路由开展了广泛的研究。如文献[4]中,作者提出了一种基于最小传送能量的路由算法。该算法选择具有最小传输能量消耗的路径将数据包从源节点发送到目的节点,这种算法具有较好的能量有效性。但是由于能量有效的路径上承担过大的负载,容易造成能量有效的路由路径提前死亡,从而其网络生存时间并不高。文献[5]中,作者提出了一种的能量均衡路由协议。在该协议中,通过在剩余能量大于某一阈值的节点集合中选择具有最小传输能量消耗的节点作为信息传输的下一跳节点。这样可以平衡整个网络的能量传输消耗,避免最短路由上的节点过早消耗尽能量,以实现一定程度上的能量消耗均衡性。文献[6]中,作者提出了一种图论算法,该算法试图通过计算每一条路由的剩余能量水平,然后排除任何剩余能量水平高于最低能量路径若干倍的路由,由于算法的性能取决于依靠经验参数,因此算法并不能总是给出最优的解决方案。文献[7]中,针对网络中某些关键节点过度消耗能量,致使网络节点能耗分布不均,影响网络的性能的缺陷,提出了一种基于博弈论的均衡路由协议,设计基于可靠度和节点的剩余能量的选择路径,解决节点能耗不均的问题,同时鼓励节点参与协作。实验结果表明,该协议提高了节点能量的利用率和节点生存时间,提高了网络的稳定性。分析现有节能方法存在的不足之处,本文提出了一种工作量加权路由模型以提高无线自组织网络的生存时间。

1 网络节点业务量均衡的优化模型

(1)

(2)

因此,传输矩阵和连通矩阵之间需要满足如下关系:

C≥X

(3)

假设无线自组织网络中,业务通信随机产生。每个源节点都可以随机地挑选网络中的其他节点作为信息发送的目的节点。因此,本文采用期望的方式计算网络生存时间。当网络中节点两两之间需要通信时,节点i的工作量ti计算方式如下:

(4)

为了尽量延长无线自组织网络的生存时间,则将工作量最多的节点进行优化,最优化数学模型可表示为[9]:

Z=minmaxti

(5)

由图论知识[10]可知:在一次信息传输过程中,源节点只发送一次信息,目的节点只接受一次信息,而每个中间节点需要转发一次信息。于是,可得到如下约束条件:

(6)

综上所述,无线自组织网络的最长生存时间数学模型整理如下:

(7)

该模型充分考虑到要均衡一个全过程中各节点的工作量,求解该模型可得到最优网络信息传输方案(即X=(xij)N×N)。但是,对于每一对给定源节点和目的节点,需要检索所有路径导致该模型的计算量庞大,无法在短时间内求解[11]。因此,本文基于该模型的分析过程,考虑网络加权路由模型,以求在模型计算量上有所改进,使得求解结果逼近最优。

2 网络加权路由数学模型

wij(k)=f(ni(k),nj(k),nmax(k))=

(8)

式中:nmax(k)表示在第k次信息发送过程中,网络中所有节点中的最大值,即:

(9)

由于网络生存时间的限制,要求网络中任一节点的状态k≤K。ni(k)可以由以下递推式关系式得到:

(10)

因此,从源节点s向目的节点d的加权距离路由模型如下:

(11)

3 仿真分析

为了深入分析本文提出的工作量加权路由算法对于无线自组织网络生存时间产生的影响,本节采用MATLAB软件对算法进行数值仿真。在一个300 m×300 m的矩形无线自组织网络区域内,随机散布着80个网络节点,每个节点的通信半径为50 m,网络的拓扑结构如图1所示。采用DSR路由协议[12],网络中每个节点的工作量如图2所示。

图1 网络拓扑结构示意图

图2 网络节点工作量示意图

由上图可知,在DSR路由协议中各节点的工作量分布十分不均衡,编号为59的节点工作量高达1 511。而生存时间取决于工作量最大的瓶颈节点,少数节点的过度使用对延长网络生存时间是十分不利的。所以,DSR并不是最优的无线自组织网络路由模型。在无线自组织网络中,网络的生存时间才是关键。然而在DSR模型中,存在过度地选择 最短的路径传输数据,导致该路径能量消耗过快,最终造成某些节点过早失效使得网络 瘫痪的情况。由图3可知,当β=0.99时,结果较为稳定。

在按照加权模型需要选取系数β的最佳取值,通过对系数β进行灵敏度分析以确定它的取值。借助 MATLAB软件,按以上求解流程求得与每个β取值相应的单个节点最大工作量,结果如图3所示。

图3 β灵敏度分析示意图

图4 两种算法的瓶颈节点能量变化图

假设无线自组织网络中每个节点的初始剩余能量均与“1”,每个节点在每次处理信息时消耗0.001。无线自组织网络节点两两之间通信时,网络瓶颈节点的能量变化如图4所示,网络中节点工作量分布状况如图5所示。

图5 两种算法工作量变化图

由图4、图5可以发现,基于工作量加权的路由算法可以有效地降低瓶颈节点工作量,延长网络生存时间。

4 结束语

分析影响网络生存时间的众多因素后,本文提出了一种工作量加权路由模型以提高无线自组织网络的生存时间。在网络信息传输的过程中,综合每条链路的业务工作量对网络链路进行加权,建立最小代价传输数学模型。该模型通过降低工作较为繁忙节点的信息转发概率,从而到达均衡节点能耗、延长网络生存时间的目的。

[1] Chirihane G,Zibouda A,Mohamed B. An Adaptive Clustering Approach to Dynamic Load Balancing and Energy Efficiency in Wireless Sensor Networks[J]. Energy,2016,114(1):647-662.

[2] Miguel S,Javier G,Baldomero C P. Multipath QoS-Driven Routing Protocol for Industrial Wireless Networks[J]. Journal of Network

and Computer Applications,2016,74:121-132.

[3] Vrinda G,Rajoo P. An Improved Energy Aware Distributed Unequal Clustering Protocol for Heterogeneous Wireless Sensor Networks[J]. Engineering Science and Technology,an International Journal,2016,19(2):1050-1058.

[4] Zhang Deyu,Chen Zhigang,Zhou Haibo,et al. Energy-Balanced Cooperative Transmission Based on Relay Selection and Power Control in Energy Harvesting Wireless Sensor Network[J]. Computer Networks,2016,104(20):189-197.

[5] 黄浩军,尹浩,陈和平,等. 无线Ad Hoc网络能量感知地理路由协议研究进展[J]. 软件学报,2014(5):1061-1084.

[6] 彭铎,黎锁平,杨喜娟,等. 一种能量高效的无线传感器网络非均匀分簇路由协议[J]. 传感技术学报,2014,(12):1687-1691.

[7] 蒋文贤.压缩感知的能量异构WSN分簇路由协议[J]. 传感技术学报,2013(6):894-900.

[8] Fatih D,Hakki B,Ibrahim K. An Adaptive,Energy-Aware and Distributed Fault-Tolerant Topology-Control Algorithm for Heterogeneous Wireless Sensor Networks. Ad Hoc Networks,2016,44:104-117.

[9] Hao Xiaochen,Liu Weijing,Yao Ning,et al. Distributed Topology Construction Algorithm to Improve Link Quality and Energy Efficiency for Wireless Sensor Networks[J]. Journal of Network and Computer Applications,Available online 22 April,2016.

[10] Huang Gaofei,Tu Wanqing. Optimal Resource Allocation in Wireless-Powered OFDM Relay Networks[J]. Computer Networks,2016,104:94-107.

[11] Zhao Feng,Wei Lina,Chen Hongbin. Optimal Time Allocation for Multi-Antenna Wireless Powered Heterogeneous Sensor Network Communications Under Imperfect CSI. Signal Processing,2016,126:159-164.

[12] 余旭涛,毕光国,王霄峻,等. Ad Hoc网络按需路由协议的改进[J]. 计算机学报,2004,27(6):838-844.

刘半藤(1984-),男,汉族,杭州余姚人,工科硕士,讲师,主要研究方向为无线传感网络,信息融合技术,hupo3@sina.com。

Research on the Routing Algorithm Optimizing Lifetime of Wireless Ad Hoc Networks*

LIUBanteng1,2*,ZHOUYing1,CHENYourong1

(1.College of Information Science and Technology,Zhejiang Shuren University,Hangzhou 310015,China;2.College of Control Science and Engineering,Zhejiang University,Hangzhou 310058,China)

Saving energy has been a hot issue in the field of wireless ad hoc networks. After analyzing the characteristics of network lifetime,this paper proposed a weighted-routing algorithm optimizing lifetime of wireless ad hoc networks. In the process of information transmission,the load of each link was considered to build the optimal model. This algorithm would reduce the transmission probability of the busy link,so as to achieve the balance node energy consumption,prolong the lifetime of the network.

lifetime of network;bottleneck node;routing strategy

项目来源:浙江省自然科学基金项目(LY15F030004);国家自然科学基金项目(61501403);浙江省公益性技术应用研究计划项目(2016C33038);浙江树人大学校级科研项目(2104A11001)

2016-06-12 修改日期:2016-10-24

TP393

A

1004-1699(2017)03-0463-04

C:7230

10.3969/j.issn.1004-1699.2017.03.021