基于動態(tài)配置等價多路徑技術的無線傳感器網絡負載均衡算法研究*

王 璟,王利利,游金闊,楊 挺*

(1.國網河南省電力公司經濟技術研究院,鄭州 450052;2.天津大學電氣與自動化工程學院,天津 300072)

?

基于動態(tài)配置等價多路徑技術的無線傳感器網絡負載均衡算法研究*

王 璟1,王利利1,游金闊2,楊 挺2*

(1.國網河南省電力公司經濟技術研究院,鄭州 450052;2.天津大學電氣與自動化工程學院,天津 300072)

隨著物聯(lián)網應用的推廣,作為底層核心構件的傳感器網絡所承載傳輸業(yè)務成激增趨勢,使得窄帶寬無線信道成為了制約物聯(lián)網應用的首要因素。合理分流流量,實現(xiàn)負載均衡是提升網絡承載能力的有效方法。本文將ECMP(Equal-Cost Multipaths)技術與傳感器網絡自組織特性相融合,傳感器網絡多跳自組織特性為業(yè)務傳輸提供多條等價最短路徑,ECMP將業(yè)務均衡分擔到這些等價最短路徑上,實現(xiàn)負載均衡。理論證明傳統(tǒng)ECMP配置方法全網節(jié)點開通ECMP功能不僅會增加網絡控制信息開銷,而且在某些情況下反而會增大區(qū)域負載,形成網絡擁塞。因此,本文提出動態(tài)選擇開通ECMP算法(DC-ECMP)。算法以流入節(jié)點流量等于流出節(jié)點流量作為業(yè)務守恒約束,鏈路帶寬上限作為鏈路容量約束,以最大鏈路利用率最小化為目標函數(shù),建立多約束優(yōu)化模型。并依據(jù)最大鏈路使用率和節(jié)點度判定開通ECMP優(yōu)先級,動態(tài)選擇需開通節(jié)點,以獲取最優(yōu)網絡傳輸性能。仿真結果表明DC-ECMP算法比已有PPV算法有效降低最大鏈路使用率,消除網絡局部擁塞隱患,并且最大減少傳輸延時9.9 ms,節(jié)省網絡資源消耗4.06%。

無線傳感器網絡;負載均衡;等價多路徑;鏈路使用率

隨著物聯(lián)網應用的提升,作為底層核心構件的傳感器網絡所承載傳輸業(yè)務成激增趨勢,使得窄帶寬無線信道成為了制約物聯(lián)網應用的首要因素[1-3]。合理分流流量,實現(xiàn)負載均衡是提升網絡承載能力的有效方法。負載均衡是指將網絡中的業(yè)務流量建模成可調變量,將其按一定的規(guī)則進行分割,通過合理的路由算法并行傳遞數(shù)據(jù),實現(xiàn)網絡資源的有效利用[4-5]。

由于傳感器網絡為多跳自組織網絡,每個傳感器節(jié)點采用全向天線可與在其通信范圍內的所有鄰居節(jié)點交換數(shù)據(jù),因此任意兩節(jié)點間存在多條通信路徑[6]。將ECMP技術引入傳感器網絡,與網絡自組織特性相融合,將更好的實現(xiàn)流量分擔。ECMP為業(yè)務提供下一跳路由選擇的等價多條最短路徑,并將流量均衡分配于這些路徑中,實現(xiàn)負載均衡[7]。Dzida M在文獻[8]中將ECMP路由問題抽象為一個混合整數(shù)規(guī)劃(MIP)數(shù)學建模。田銘等學者在文獻[9]中提出了基于鏈路繁忙趨勢值的等價多路徑選擇算法。傳統(tǒng)ECMP流量分擔研究中,多是基于網絡中全部路由節(jié)點都具備ECMP功能[10]。然而,理論證明全網節(jié)點開通ECMP功能并非能達到最優(yōu)負載均衡,不僅會增加網絡控制信息開銷,而且在某些情況下反而會增大區(qū)域負載,形成網絡擁塞。因此,本文提出動態(tài)選擇開通ECMP算法,實現(xiàn)更優(yōu)負載均衡算法。

本文將流入節(jié)點流量等于流出節(jié)點流量作為業(yè)務守恒約束,無線帶寬上限作為鏈路容量約束,以最大鏈路利用率最小化為目標函數(shù),建立多約束優(yōu)化模型,采用動態(tài)選擇貪婪算法求解,以獲取最優(yōu)網絡傳輸性能。

1 問題提出

如上所述,ECMP由于能夠支持在多條最短路徑上進行流量分擔,而實現(xiàn)負載均衡,提升網絡傳輸性能。但已有模型設定所有節(jié)點都具備ECMP功能,然而其并非能使實際網絡運行達到最優(yōu)負載均衡。首先,節(jié)點運行ECMP協(xié)議將增加網絡內控制信息開銷,而且在某些情況下不僅不會分擔流量,反而會增大特定區(qū)域的通信負載,形成網絡擁塞。以圖1的拓撲為例。

圖1 節(jié)點配置ECMP網絡模型

假定網絡中各條鏈路同質,即業(yè)務通過鏈路的費用相等,各條鏈路的容量也相等,均為100 Mbit/s?，F(xiàn)節(jié)點對(A,E)間需要傳輸80 Mbit/s業(yè)務量,(A,C)間存在50 Mbit/s的業(yè)務量。如果設定網絡中所有節(jié)點都具備ECMP功能,則按照流量分擔原則,鏈路lAD將承擔105 Mbit/s的業(yè)務量,超過鏈路的帶寬上限,形成擁塞。造成高丟包率和延遲,影響網絡傳輸質量。而鏈路lAB僅承擔25 Mbit/s流量,相對空閑,造成資源浪費。如果動態(tài)調整節(jié)點開通ECMP功能,即關閉節(jié)點A該功能,則按照最短路徑原則,同時考慮到鏈路lAD和lAB利用狀態(tài),將業(yè)務(A,C)配置在最短路徑path=A→B→C,則網絡中各鏈路承擔流量在[50,80]Mbit/s,避免網絡擁塞,保證負載均衡。上述兩種情況下鏈路的負載對比表如表1。

表1 鏈路負載對比 單位:Mbit/s

通過上述分析可以看出,全部節(jié)點均配置ECMP功能并非是實現(xiàn)網絡負載最優(yōu)分擔的有效方法。本文在傳統(tǒng)ECMP模型的基礎上,結合無線傳感器網絡多跳自組織結構特性,提出動態(tài)配置ECMP實現(xiàn)網絡更優(yōu)負載均衡算法。

2 可變等價多路徑模型描述

本文在傳統(tǒng)ECMP模型的基礎上,提出動態(tài)配置ECMP模型。

問題描述:將無線傳感器網絡數(shù)學建模為有向賦權圖G=(V,E),其中V={v1,v2,…,vn}為網絡節(jié)點集;E={e1,e2,…,em}為節(jié)點間通信鏈路集。每個節(jié)點有唯一標識符,vi,i=1,…,n為通信節(jié)點,具有信息采集和數(shù)據(jù)轉發(fā)功能。V中各節(jié)點的有效傳輸距離λ0相等,則E={e|D(vj,vk)≤λ0,vj,vk∈V}。且相鄰節(jié)點vj,vk共享同一無線介質,節(jié)點的信息發(fā)射功率:

(1)

式中:α為發(fā)射功率參數(shù),依據(jù)實際傳感器節(jié)點發(fā)射模塊類型決定。

(2)

當?ei(vj,vk)∈E,M(ei)={Ca(ei),Memax(ei),μmax(ei)}為鏈路ei上量度函數(shù)集。Ca(ei):(帶寬函數(shù))鏈路ei帶寬上限;Memax(ei):(費用函數(shù))經過鏈路ei所消耗網絡費用;μmax(ei):(延時函數(shù))經過鏈路ei所需最大延時。

并且定義網絡傳輸業(yè)務矩陣F={fst|源目的節(jié)點對vs,vt間的業(yè)務量,vs,vt∈V}。則業(yè)務守恒約束和鏈路容量約束定義如下:

(3)

(4)

我們以鏈路帶寬使用率為衡量網絡是否存在擁塞的量度,定義如式(5)所示。因此優(yōu)化目標為最小化最大鏈路使用率min{max(ze)},e∈E。

(5)

3 動態(tài)配置ECMP最優(yōu)負載均衡算法

3.1 算法計算流程

由于ECMP協(xié)議會增加網絡控制信息開銷,消耗傳感器節(jié)點能量,因此在傳感器網絡流量分擔應用時設定配置節(jié)點比率η,即上限配置η×N個節(jié)點。

動態(tài)配置ECMP最優(yōu)負載均衡算法DC-ECMP每次僅選擇配置優(yōu)先級最高節(jié)點開通ECMP功能,隨后對網絡狀態(tài)進行更新,重新計算負載分擔,檢測最大鏈路使用率max(ze)是否下降,即提升網絡均衡狀態(tài),并達到設計目標。若未滿足,則在當前網絡狀態(tài)下選擇配置優(yōu)先級最高的節(jié)點。終止條件為網絡最大鏈路使用率max(ze)最小,或已達到η×N節(jié)點配置上限。動態(tài)配置策略是一種啟發(fā)式貪婪算法,在考慮網絡每次最新的負載狀態(tài)條件下進行節(jié)點選擇,以達到負載均衡效果最優(yōu)。動態(tài)配置ECMP最優(yōu)負載均衡算法的實現(xiàn)流程如下:

按最優(yōu)處方測得白藜蘆醇DPPC脂質體粉霧劑載藥量為（2.4±0.9）%，加入甘露醇載體的DPPC脂質粉霧劑再分散后的包封率為（68.6±2.1）%。驗證了凍干工藝基本不影響DPPC脂質體的結構和白藜蘆醇的包封。

圖2 DC-ECMP算法流程圖

3.2 配置ECMP優(yōu)先級計算

DC-ECMP算法中決定節(jié)點動態(tài)選擇的參數(shù)為配置ECMP優(yōu)先級。當以節(jié)點vx為出口的鏈路中存在高使用率時,則易產生擁塞[11],需要開通ECMP功能。而具有更高的節(jié)點度說明節(jié)點處于拓撲核心,并且具備更多連接鏈路分攤流量。因此本文采用最大鏈路使用率max(ze),{v(ej)=x}和節(jié)點度kx衡量ECMP優(yōu)先級,計算公式如式(6)。定義節(jié)點x的ECMP配置優(yōu)先級為:

(6)

式中:{e|v(ej)=x}表示以節(jié)點vx為出口的所有鏈路集合。

3.3 鏈路權重

鏈路權重決定了等價最短多路徑的計算結果。在此定義鏈路權重為:對于業(yè)務fst,當鏈路e為被選路徑時,鏈路權重為傳輸業(yè)務所消耗的網絡資源乘以該業(yè)務占用帶寬[12]。其數(shù)學表達式如下:

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

(7)

考慮傳感器網絡的稀缺能量問題,本文設定Memax(e)為傳輸單位byte的能耗,即Me(e)=ETx(τ,d)+ERx(τ)。其中發(fā)送能耗為:

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

(8)

接收能耗為:

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

(9)

4 算法性能評價

傳感器網絡仿真拓撲如圖3所示,設定每條鏈路傳輸容量2Mbit/s,路由信令2kbit。發(fā)送數(shù)據(jù)報速率為3packets/s,數(shù)據(jù)大小為30報文長度,每個報文為10kbit,發(fā)射功率滿足式(1)。網絡圖鏈路權值由式(7)～式(9)定義。每個節(jié)點攜帶能量為Eg(vi)=20J。

圖3 算法性能評價仿真網絡拓撲圖

圖4給出兩種算法選擇開通相同數(shù)量ECMP節(jié)點情況下的網絡鏈路的最大使用率。由圖可知,在執(zhí)行相同傳輸任務,DC-ECMP算法比PPV算法具有更好的負載分擔能力,降低網絡中鏈路最大使用帶寬。當選取節(jié)點數(shù)大于3以上,本文算法的鏈路的最大利用率平均低于PPV的7.87%,最大差值為14.58%。

圖4 網絡鏈路最大使用率

計算在開通不同數(shù)量ECMP節(jié)點情況下,平均網絡傳輸延時,如圖5所示。由運行結果可知,由于DC-ECMP選擇了更優(yōu)節(jié)點開通ECMP功能,使得業(yè)務能夠選擇更短傳輸路徑,從而降低平均網絡傳輸延時,DC-ECMP算法比PPV算法縮短延時18.5%。并且,當有較多節(jié)點可開通ECMP功能時,由于選擇裕度增大,DC-ECMP算法比PPV算法縮短延時9.9ms。

圖5 平均網絡傳輸延時

考慮傳感器網絡能量稀缺性和不易補充特點,定義網絡資源損耗為節(jié)點能耗。計算傳輸相同業(yè)務矩陣(即相同業(yè)務量和信源信宿)情況下的網絡剩余能量。由圖6可知,節(jié)點開通ECMP功能將消耗部分能量,但合理的動態(tài)配置有助于業(yè)務最優(yōu)傳輸路徑的選擇,從而減緩網絡能量消耗。DC-ECMP算法比PPV算法在不同ECMP配置條件下節(jié)省網絡能耗4.06%。

圖6 網絡資源消耗量

5 總結

針對物聯(lián)網應用中業(yè)務激增,本文研究無線傳感器網絡流量分擔和負載均衡,提出動態(tài)選擇開通ECMP算法。與傳統(tǒng)ECMP模型不同,DC-ECMP算法依據(jù)最大鏈路使用率max(ze)和節(jié)點度kx判定優(yōu)先級,動態(tài)選擇需開通ECMP節(jié)點。從而避免了全開ECMP功能增加網絡控制信息開銷,且增大區(qū)域負載,形成網絡擁塞的缺陷。算法將流入節(jié)點流量等于流出節(jié)點流量作為業(yè)務守恒約束,鏈路帶寬上限作為鏈路容量約束,以最大鏈路利用率最小化為目標函數(shù),建立多約束優(yōu)化模型,采用動態(tài)選擇貪婪算法求解,以獲取最優(yōu)網絡傳輸性能。仿真結果表明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]范一鳴,屠雄剛. 一種基于譜聚類分析的物聯(lián)網節(jié)點安全控制域劃分算法[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]顧云麗,徐昕,杜杰,等. 基于蜂群算法的無線傳感器網絡任播路由協(xié)議[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路由選擇優(yōu)化[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-)男,碩士研究生,研究方向為無線傳感器網絡可靠通信和傳輸協(xié)議;

楊 挺(1979-),男,教授/博士生導師,博士,研究方向為無線傳感器網絡組網和通信協(xié)議,通訊作者,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