基于动态配置等价多路径技术的无线传感器网络负载均衡算法研究*

王 璟,王利利,游金阔,杨 挺*

(1.国网河南省电力公司经济技术研究院,郑州 450052;2.天津大学电气与自动化工程学院,天津 300072)



基于动态配置等价多路径技术的无线传感器网络负载均衡算法研究*

王 璟1,王利利1,游金阔2,杨 挺2*

(1.国网河南省电力公司经济技术研究院,郑州 450052;2.天津大学电气与自动化工程学院,天津 300072)

随着物联网应用的推广,作为底层核心构件的传感器网络所承载传输业务成激增趋势,使得窄带宽无线信道成为了制约物联网应用的首要因素。合理分流流量,实现负载均衡是提升网络承载能力的有效方法。本文将ECMP(Equal-Cost Multipaths)技术与传感器网络自组织特性相融合,传感器网络多跳自组织特性为业务传输提供多条等价最短路径,ECMP将业务均衡分担到这些等价最短路径上,实现负载均衡。理论证明传统ECMP配置方法全网节点开通ECMP功能不仅会增加网络控制信息开销,而且在某些情况下反而会增大区域负载,形成网络拥塞。因此,本文提出动态选择开通ECMP算法(DC-ECMP)。算法以流入节点流量等于流出节点流量作为业务守恒约束,链路带宽上限作为链路容量约束,以最大链路利用率最小化为目标函数,建立多约束优化模型。并依据最大链路使用率和节点度判定开通ECMP优先级,动态选择需开通节点,以获取最优网络传输性能。仿真结果表明DC-ECMP算法比已有PPV算法有效降低最大链路使用率,消除网络局部拥塞隐患,并且最大减少传输延时9.9 ms,节省网络资源消耗4.06%。

无线传感器网络;负载均衡;等价多路径;链路使用率

随着物联网应用的提升,作为底层核心构件的传感器网络所承载传输业务成激增趋势,使得窄带宽无线信道成为了制约物联网应用的首要因素[1-3]。合理分流流量,实现负载均衡是提升网络承载能力的有效方法。负载均衡是指将网络中的业务流量建模成可调变量,将其按一定的规则进行分割,通过合理的路由算法并行传递数据,实现网络资源的有效利用[4-5]。

由于传感器网络为多跳自组织网络,每个传感器节点采用全向天线可与在其通信范围内的所有邻居节点交换数据,因此任意两节点间存在多条通信路径[6]。将ECMP技术引入传感器网络,与网络自组织特性相融合,将更好的实现流量分担。ECMP为业务提供下一跳路由选择的等价多条最短路径,并将流量均衡分配于这些路径中,实现负载均衡[7]。Dzida M在文献[8]中将ECMP路由问题抽象为一个混合整数规划(MIP)数学建模。田铭等学者在文献[9]中提出了基于链路繁忙趋势值的等价多路径选择算法。传统ECMP流量分担研究中,多是基于网络中全部路由节点都具备ECMP功能[10]。然而,理论证明全网节点开通ECMP功能并非能达到最优负载均衡,不仅会增加网络控制信息开销,而且在某些情况下反而会增大区域负载,形成网络拥塞。因此,本文提出动态选择开通ECMP算法,实现更优负载均衡算法。

本文将流入节点流量等于流出节点流量作为业务守恒约束,无线带宽上限作为链路容量约束,以最大链路利用率最小化为目标函数,建立多约束优化模型,采用动态选择贪婪算法求解,以获取最优网络传输性能。

1 问题提出

如上所述,ECMP由于能够支持在多条最短路径上进行流量分担,而实现负载均衡,提升网络传输性能。但已有模型设定所有节点都具备ECMP功能,然而其并非能使实际网络运行达到最优负载均衡。首先,节点运行ECMP协议将增加网络内控制信息开销,而且在某些情况下不仅不会分担流量,反而会增大特定区域的通信负载,形成网络拥塞。以图1的拓扑为例。

图1 节点配置ECMP网络模型

假定网络中各条链路同质,即业务通过链路的费用相等,各条链路的容量也相等,均为100 Mbit/s。现节点对(A,E)间需要传输80 Mbit/s业务量,(A,C)间存在50 Mbit/s的业务量。如果设定网络中所有节点都具备ECMP功能,则按照流量分担原则,链路lAD将承担105 Mbit/s的业务量,超过链路的带宽上限,形成拥塞。造成高丢包率和延迟,影响网络传输质量。而链路lAB仅承担25 Mbit/s流量,相对空闲,造成资源浪费。如果动态调整节点开通ECMP功能,即关闭节点A该功能,则按照最短路径原则,同时考虑到链路lAD和lAB利用状态,将业务(A,C)配置在最短路径path=A→B→C,则网络中各链路承担流量在[50,80]Mbit/s,避免网络拥塞,保证负载均衡。上述两种情况下链路的负载对比表如表1。

表1 链路负载对比 单位:Mbit/s

通过上述分析可以看出,全部节点均配置ECMP功能并非是实现网络负载最优分担的有效方法。本文在传统ECMP模型的基础上,结合无线传感器网络多跳自组织结构特性,提出动态配置ECMP实现网络更优负载均衡算法。

2 可变等价多路径模型描述

本文在传统ECMP模型的基础上,提出动态配置ECMP模型。

问题描述:将无线传感器网络数学建模为有向赋权图G=(V,E),其中V={v1,v2,…,vn}为网络节点集;E={e1,e2,…,em}为节点间通信链路集。每个节点有唯一标识符,vi,i=1,…,n为通信节点,具有信息采集和数据转发功能。V中各节点的有效传输距离λ0相等,则E={e|D(vj,vk)≤λ0,vj,vk∈V}。且相邻节点vj,vk共享同一无线介质,节点的信息发射功率:

(1)

式中:α为发射功率参数,依据实际传感器节点发射模块类型决定。

(2)

当∀ei(vj,vk)∈E,M(ei)={Ca(ei),Memax(ei),μmax(ei)}为链路ei上量度函数集。Ca(ei):(带宽函数)链路ei带宽上限;Memax(ei):(费用函数)经过链路ei所消耗网络费用;μmax(ei):(延时函数)经过链路ei所需最大延时。

并且定义网络传输业务矩阵F={fst|源目的节点对vs,vt间的业务量,vs,vt∈V}。则业务守恒约束和链路容量约束定义如下:

(3)

(4)

我们以链路带宽使用率为衡量网络是否存在拥塞的量度,定义如式(5)所示。因此优化目标为最小化最大链路使用率min{max(ze)},e∈E。

(5)

3 动态配置ECMP最优负载均衡算法

3.1 算法计算流程

由于ECMP协议会增加网络控制信息开销,消耗传感器节点能量,因此在传感器网络流量分担应用时设定配置节点比率η,即上限配置η×N个节点。

动态配置ECMP最优负载均衡算法DC-ECMP每次仅选择配置优先级最高节点开通ECMP功能,随后对网络状态进行更新,重新计算负载分担,检测最大链路使用率max(ze)是否下降,即提升网络均衡状态,并达到设计目标。若未满足,则在当前网络状态下选择配置优先级最高的节点。终止条件为网络最大链路使用率max(ze)最小,或已达到η×N节点配置上限。动态配置策略是一种启发式贪婪算法,在考虑网络每次最新的负载状态条件下进行节点选择,以达到负载均衡效果最优。动态配置ECMP最优负载均衡算法的实现流程如下:

按最优处方测得白藜芦醇DPPC脂质体粉雾剂载药量为（2.4±0.9）%，加入甘露醇载体的DPPC脂质粉雾剂再分散后的包封率为（68.6±2.1）%。验证了冻干工艺基本不影响DPPC脂质体的结构和白藜芦醇的包封。

图2 DC-ECMP算法流程图

3.2 配置ECMP优先级计算

DC-ECMP算法中决定节点动态选择的参数为配置ECMP优先级。当以节点vx为出口的链路中存在高使用率时,则易产生拥塞[11],需要开通ECMP功能。而具有更高的节点度说明节点处于拓扑核心,并且具备更多连接链路分摊流量。因此本文采用最大链路使用率max(ze),{v(ej)=x}和节点度kx衡量ECMP优先级,计算公式如式(6)。定义节点x的ECMP配置优先级为:

(6)

式中:{e|v(ej)=x}表示以节点vx为出口的所有链路集合。

3.3 链路权重

链路权重决定了等价最短多路径的计算结果。在此定义链路权重为:对于业务fst,当链路e为被选路径时,链路权重为传输业务所消耗的网络资源乘以该业务占用带宽[12]。其数学表达式如下:

w(e,s,t)=fst×Memax(e)

(7)

考虑传感器网络的稀缺能量问题,本文设定Memax(e)为传输单位byte的能耗,即Me(e)=ETx(τ,d)+ERx(τ)。其中发送能耗为:

ETx(k,d)=ETx-elec(τ)+ETx-amp(τ,d)=Eelec×τ+εamp×τ×dα

(8)

接收能耗为:

ERx(k)=ERx-elec(τ)=Eelec×τ

(9)

4 算法性能评价

传感器网络仿真拓扑如图3所示,设定每条链路传输容量2Mbit/s,路由信令2kbit。发送数据报速率为3packets/s,数据大小为30报文长度,每个报文为10kbit,发射功率满足式(1)。网络图链路权值由式(7)～式(9)定义。每个节点携带能量为Eg(vi)=20J。

图3 算法性能评价仿真网络拓扑图

图4给出两种算法选择开通相同数量ECMP节点情况下的网络链路的最大使用率。由图可知,在执行相同传输任务,DC-ECMP算法比PPV算法具有更好的负载分担能力,降低网络中链路最大使用带宽。当选取节点数大于3以上,本文算法的链路的最大利用率平均低于PPV的7.87%,最大差值为14.58%。

图4 网络链路最大使用率

计算在开通不同数量ECMP节点情况下,平均网络传输延时,如图5所示。由运行结果可知,由于DC-ECMP选择了更优节点开通ECMP功能,使得业务能够选择更短传输路径,从而降低平均网络传输延时,DC-ECMP算法比PPV算法缩短延时18.5%。并且,当有较多节点可开通ECMP功能时,由于选择裕度增大,DC-ECMP算法比PPV算法缩短延时9.9ms。

图5 平均网络传输延时

考虑传感器网络能量稀缺性和不易补充特点,定义网络资源损耗为节点能耗。计算传输相同业务矩阵(即相同业务量和信源信宿)情况下的网络剩余能量。由图6可知,节点开通ECMP功能将消耗部分能量,但合理的动态配置有助于业务最优传输路径的选择,从而减缓网络能量消耗。DC-ECMP算法比PPV算法在不同ECMP配置条件下节省网络能耗4.06%。

图6 网络资源消耗量

5 总结

针对物联网应用中业务激增,本文研究无线传感器网络流量分担和负载均衡,提出动态选择开通ECMP算法。与传统ECMP模型不同,DC-ECMP算法依据最大链路使用率max(ze)和节点度kx判定优先级,动态选择需开通ECMP节点。从而避免了全开ECMP功能增加网络控制信息开销,且增大区域负载,形成网络拥塞的缺陷。算法将流入节点流量等于流出节点流量作为业务守恒约束,链路带宽上限作为链路容量约束,以最大链路利用率最小化为目标函数,建立多约束优化模型,采用动态选择贪婪算法求解,以获取最优网络传输性能。仿真结果表明DC-ECMP算法比已有PPV算法有效降低最大链路使用率,消除网络局部拥塞隐患,并且减少传输延时和网络资源消耗,提升网络传输性能。

[1] Chakraborty A,Rout R R,Chakrabarti A,et al. On Network Lifetime Expectancy With Realistic Sensing and Traffic Generation Model in Wireless Sensor Networks[J]. IEEE Sensors Journal,2013,13(7):2771-2779.

[2]Han T,Ansari N. Offloading Mobile Traffic via Green Content Broker[J]. IEEE Internet of Things Journal,2014,1(2):161-170.

[3]范一鸣,屠雄刚. 一种基于谱聚类分析的物联网节点安全控制域划分算法[J]. 传感技术学报,2014,27(5):1004-1699.

[4]Kashiwazaki H,Kobayashi S,Kawai S,et al. An Adaptive Approach for Network Traffic Load Balancing by Using One-Way Delay[C]//IEEE/IPSJ 12th International Symposium on Applications and the Internet,2012:345-350.

[5]Venkatesan S. Joint Load Balancing and Interference Coordination Can Double Heterogeneous Network Capacity[C]//IEEE 24th International Symposium on Personal Indoor and Mobile Radio Communications,2013:1957-1961.

[6]顾云丽,徐昕,杜杰,等. 基于蜂群算法的无线传感器网络任播路由协议[J]. 传感技术学报,2013,26(4):564-569.

[7]HoPPs C E. Analysis of an Equal Cost Multi-Path Algorithm[S]. RFC2992,2000.

[8]Dzida M,Zagozdzon M,Pioro M,et al. Optimization of the Shortest-Path Routing with Equal-Cost Multi-Path Load Balancing[C]//IEEE International Conference on Transparent Optical Networks,2006:9-12.

[9]田铭,兰巨龙,朱宣勇. 一种基于链路繁忙趋势值的等价多路径选择算法[J]. 信息工程大学学报,2010,11(2):190-195.

[10]Jaroenrat K,Chimmanee S,Charnkeitkong P. Algorithms for IP Networks Design with ECMP Routing Enable[C]//IEEE the 7th International Conference on Computing and Convergence Technology,2012:420-425.

[11]Utsumi S,Zabir S M S. Utilization-Based Congestion Control:Improvement of Friendliness with TCP over Wireless Links[C]//IEEE 26th International Conference on Advanced Information Networking and Applications,2012:215-220.

[12]金琼,周世纪,彭燕妮. 基于改进遗传算法的QoS路由选择优化[J]. 计算机应用,2005,25(2):256-258.

Dynamic Configure Equal Cost Multi-Paths to Achieve Load Balance in Wireless Sensor Networks*

WANGJing1,WANGLili1,YOUJinkuo2,YANGTing2*

(1.State Grid Henan Electric Power Company,Economic Research Institute,Zhengzhou 450052,China;2.School of Electrical Engineering and Automation,Tianjin University,Tianjin 300072,China)

With the development of Internet of Things(IoTs),wireless sensor networks,as the infrastructure of IoTs,should bear more and more various transmission services. The narrow wireless bandwidth becomes the first restrictive factors. Shunting flow to achieve load balance is the effective way to improve the bearing capacity of communication network. This paper integrated Equal-Cost Multi-Paths(ECMP)technique and WSN’s self-organized characteristics,in which the self-organized connection and multi-hops transmission model of WSN provide more than one shortest paths from traffic source to the destination sensor node,and then ECMP can equally apportioned traffic on these available equal cost multi-paths to stabilize huge traffic. It proved that the traditional ECMP model,configured all of nodes with ECMP function,will increase the overhead expenses,and even make heavier traffic load in some special cases. To solve these problems,this paper proposed the dynamic configuration ECMP algorithm-DC-ECMP. In the algorithm,it defined the traffic volume conservation constraint and the wireless transmitting bandwidth upper bound constraint,made the minimizing the maximum link utilization rate as objective function,and establish the multi-constraint optimization model. Using the maximum link utilization rate and node’s degree to calculate the priority of configuration ECMP function,each node can be dynamic configuration and achieve the optimal network’s transmitting performance. In our evaluation with simulations,the performance of DC-ECMP is measured and compared with PPV algorithms. Based on the experimental results,DC-ECMP outperforms existing algorithms in reduce the maximum link utilization rate,short the transmitting latency 9.9 ms,and save the networks’ resource consumption 4.06%.

wireless sensor networks;load balance;equal cost multi-path;link utilization rate

王 璟(1973-),女,高级工程师,副院长,研究方向为智能电网灵活可靠通信技术研究与应用;

王利利(1984-),男,博士,工程师,研究方向为智能配电网信息采集和通信技术研究;

游金阔(1990-)男,硕士研究生,研究方向为无线传感器网络可靠通信和传输协议;

杨 挺(1979-),男,教授/博士生导师,博士,研究方向为无线传感器网络组网和通信协议,通讯作者,yangting@tju.edu.cn。

项目来源:国际科技合作专项项目(2013DFA11040);国家自然科学基金项目(61172014);天津市自然科学基金重点项目(12JCZDJC21300)

2014-11-04 修改日期:2015-01-12

C:6150P

10.3969/j.issn.1004-1699.2015.05.023

TN915

A

1004-1699(2015)05-0752-05