0 引言

    隨著物聯(lián)網(wǎng)技術(shù)的飛速發(fā)展和日益普及，6LoWPAN廣泛應用于智能家居、環(huán)境監(jiān)測和樓宇自動化等領(lǐng)域。單網(wǎng)關(guān)架構(gòu)的6LoWPAN存在網(wǎng)關(guān)瓶頸問題，且不利于大規(guī)模部署。因此，多網(wǎng)關(guān)系統(tǒng)將是實現(xiàn)WSN和Internet互聯(lián)的高效模式，網(wǎng)絡(luò)系統(tǒng)示意如圖1所示，其中A為根網(wǎng)關(guān)，B、C為部署網(wǎng)關(guān)。在多網(wǎng)關(guān)系統(tǒng)中，網(wǎng)關(guān)位置的選擇不僅影響節(jié)點間的鏈路質(zhì)量和通信延遲，而且還決定了網(wǎng)絡(luò)整體的容量。因此，合理的網(wǎng)關(guān)部署是實現(xiàn)6LoWPAN網(wǎng)絡(luò)性能優(yōu)化的關(guān)鍵。

    針對6LoWPAN負載均衡問題的研究，文獻[1]利用子節(jié)點根據(jù)鄰居節(jié)點的排隊率和跳距選擇父節(jié)點實現(xiàn)負載分擔，并在文獻[2]中對路由方案進行了補充和更新。文獻[3]提出一種基于負載均衡的分層路由算法，保證網(wǎng)絡(luò)負載平衡的同時提高網(wǎng)絡(luò)生存周期。在6LoWPAN多網(wǎng)的研究中，文獻[4]提出一種多網(wǎng)關(guān)系統(tǒng)方案，解決網(wǎng)關(guān)瓶頸問題并提高網(wǎng)絡(luò)吞吐量。文獻[5]在多網(wǎng)關(guān)架構(gòu)的基礎(chǔ)上，提出一種分布式動態(tài)負載平衡方案實現(xiàn)全局負載平衡。近年來基于LoRa技術(shù)的遠距離無線廣域網(wǎng)（Long Rage WAN，LoRoWAN）采用多網(wǎng)關(guān)系統(tǒng)，并且在LoRaWAN上實現(xiàn)了6LoWPAN標準。

    在WSN網(wǎng)絡(luò)的sink部署研究中，從用多sink節(jié)點代替單sink節(jié)點的網(wǎng)絡(luò)劃分方案^[6]的提出，到在多sink網(wǎng)絡(luò)中考慮布局和能耗，提出一種基于啟發(fā)式算法的部署優(yōu)化方案^[7]。為了提高多跳WSN的網(wǎng)絡(luò)生存周期，提出基于粒子群算法的多sink節(jié)點部署算法^[8]和分布式貪婪簇生成算法^[9]，而文獻[10]提出兩種基于能量的sink局部搜索策略。多網(wǎng)關(guān)部署問題研究常見于WMN網(wǎng)絡(luò)，以負載均衡為目標，通過基于權(quán)值的貪婪算法^[11]、改進雜交粒子群優(yōu)化算法^[12]和優(yōu)化類聚K-means算法^[13]完成網(wǎng)關(guān)部署。在考慮網(wǎng)關(guān)實際容量的情況下，文獻[14]在貪婪算法的基礎(chǔ)上定義饑餓度，提出一種能更好實現(xiàn)負載均衡的饑餓算法。文獻[15]以最小化網(wǎng)絡(luò)能耗為目標，提出一種基于啟發(fā)式的貪婪算法實現(xiàn)綠色WMN的網(wǎng)關(guān)部署。

    上述研究中，WSN網(wǎng)絡(luò)為星型拓撲，WMN網(wǎng)絡(luò)為網(wǎng)狀拓撲，其拓撲結(jié)構(gòu)對網(wǎng)關(guān)部署的約束性小。6LoWPAN網(wǎng)絡(luò)為樹型拓撲，網(wǎng)關(guān)部署算法需要考慮節(jié)點位置和網(wǎng)絡(luò)拓撲的關(guān)系。在6LoWPAN網(wǎng)絡(luò)中，產(chǎn)生的數(shù)據(jù)流量多跳路由經(jīng)過不同的路由器（6LoWPAN Router，6LR），在邊界路由器（6LoWPAN Border Router，6LBR）匯聚發(fā)往Internet。即使采用多網(wǎng)關(guān)系統(tǒng)，由于缺少網(wǎng)關(guān)均衡，也會導致網(wǎng)關(guān)之間負載不平衡。本文以最小化網(wǎng)關(guān)數(shù)量和網(wǎng)關(guān)間負載均衡為目標，在貪婪算法的思想上結(jié)合6LoWPAN樹型拓撲網(wǎng)絡(luò)的特殊性，提出一種基于負載的多網(wǎng)關(guān)部署算法，以最少網(wǎng)關(guān)數(shù)量實現(xiàn)網(wǎng)關(guān)負載均衡。

1 網(wǎng)絡(luò)模型搭建

    在6LoWPAN中考慮多網(wǎng)關(guān)部署問題，用圖G(V，E)表示待優(yōu)化網(wǎng)絡(luò)。節(jié)點v∈V為6LoWPAN中的節(jié)點，可為6LR或者6LBR。在6LoWPAN網(wǎng)絡(luò)中，6LR負責轉(zhuǎn)發(fā)和路由IPv6數(shù)據(jù)包；而6LBR負責6LoWPAN網(wǎng)絡(luò)和其他IP網(wǎng)絡(luò)的數(shù)據(jù)交互，即實現(xiàn)網(wǎng)關(guān)功能。設(shè)v具有一個圓形的可通信范圍，根據(jù)目標函數(shù)選擇與在該范圍內(nèi)的節(jié)點建立拓撲連接。在構(gòu)建好的拓撲結(jié)構(gòu)中，與v連接的節(jié)點分為父節(jié)點N_p(v)和子節(jié)點集N_c(v)，N(v)=N_p(v)+N_c(v)。由于6LoWPAN的DODAG樹型網(wǎng)絡(luò)拓撲的特殊性，v至多有一個父節(jié)點但可以有多個子節(jié)點或者沒有子節(jié)點。對于節(jié)點u∈N(v)，存在邊e(u，v)∈E，e(u，v)為v和u之間的雙向通信鏈路，表示節(jié)點v和u之間已經(jīng)建立拓撲連接。

2 問題描述

    研究6LoWPAN多網(wǎng)關(guān)網(wǎng)絡(luò)設(shè)計，通過合理部署網(wǎng)關(guān)，使得各網(wǎng)關(guān)間負載平衡，同時將鏈路質(zhì)量和網(wǎng)關(guān)剩余能量作為參考因素，保證網(wǎng)絡(luò)的穩(wěn)定性。網(wǎng)關(guān)部署問題就是在單網(wǎng)關(guān)架構(gòu)下的6LoWPAN網(wǎng)絡(luò)中，根據(jù)節(jié)點流量負載和綜合因子進行網(wǎng)關(guān)選擇，用最少的網(wǎng)關(guān)數(shù)量實現(xiàn)網(wǎng)關(guān)間的負載均衡。然后，根據(jù)網(wǎng)關(guān)部署的結(jié)果劃分子網(wǎng)分支，將在樹型拓撲中以同一網(wǎng)關(guān)作為根的節(jié)點劃分到一個子網(wǎng)分支。

    條件（1）表示V中任一節(jié)點有且只有一個網(wǎng)關(guān)；條件（2）表示候選網(wǎng)關(guān)需要滿足的負載門限要求；條件（3）表示選擇候選網(wǎng)關(guān)中綜合因子最大的節(jié)點作為網(wǎng)關(guān)節(jié)點；條件（4）表示網(wǎng)關(guān)的負載為子網(wǎng)分支內(nèi)所有節(jié)點和網(wǎng)關(guān)節(jié)點本身的權(quán)值之和。將6LoWPAN多網(wǎng)關(guān)部署問題具體化：以最小網(wǎng)關(guān)數(shù)量實現(xiàn)網(wǎng)關(guān)間負載均衡。通過考慮節(jié)點負載得到候選網(wǎng)關(guān)，再根據(jù)鏈路質(zhì)量和剩余能量的綜合因子，從候選網(wǎng)關(guān)中選出最優(yōu)網(wǎng)關(guān)。本文在貪婪算法的基礎(chǔ)上，結(jié)合6LoWPAN網(wǎng)絡(luò)樹型拓撲的特點，提出一種多網(wǎng)關(guān)部署算法Load-base_Placement(LP)來獲得問題的最優(yōu)解。

3 多網(wǎng)關(guān)部署算法

3.1 算法思路

    由于6LoWPAN網(wǎng)絡(luò)采用的是樹型拓撲結(jié)構(gòu)，其網(wǎng)絡(luò)中節(jié)點的流量負載具有累加特性。位于根節(jié)點和葉子節(jié)點之間的中間路由節(jié)點不僅要承擔自身流量負載，還要負責其子節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)。在樹型拓撲網(wǎng)絡(luò)中，從葉子節(jié)點至根節(jié)點流量負載累積增加。因此，算法采取從葉子節(jié)點開始沿樹型拓撲往上至根接網(wǎng)關(guān)的策略，搜索候選網(wǎng)關(guān)，并確定最佳網(wǎng)關(guān)。

    算法大致過程如下：在現(xiàn)有6LoWPAN樹型拓撲網(wǎng)絡(luò)中，根據(jù)各節(jié)點流量負載統(tǒng)計結(jié)果，進行權(quán)值化處理。從距根節(jié)點跳距最大且有較大流量負載的葉子節(jié)點開始，往上至根節(jié)點，搜索滿足流量負載條件的候選網(wǎng)關(guān)節(jié)點。根據(jù)鏈路質(zhì)量和剩余能量所構(gòu)成的評價因子，在候選網(wǎng)關(guān)選擇最佳網(wǎng)關(guān)并確定對應子網(wǎng)分支，移除該分支與網(wǎng)絡(luò)中其他節(jié)點的鏈路連接。在移除已經(jīng)確定的子網(wǎng)分支后，更新網(wǎng)絡(luò)中剩余節(jié)點的流量負載值，并再次執(zhí)行搜索，當訪問至根網(wǎng)關(guān)時算法結(jié)束。

3.2 算法描述

    輸入：初始的網(wǎng)關(guān)節(jié)點序列（只有一個根網(wǎng)關(guān)）；

    輸出：完整的網(wǎng)關(guān)節(jié)點序列和子網(wǎng)分支劃分方案。

    算法步驟如下。

    (1)訪問當前網(wǎng)絡(luò)中距根節(jié)點跳距最大且有較大流量負載的葉子節(jié)點。

    (2)對節(jié)點流量負載進行判斷，如果L(v_i)<L_threshold，則向上訪問其父節(jié)點，如果其父節(jié)點為根網(wǎng)關(guān)，則將此分支移除；如果L(v_i)>L_threshold，則向下回溯其子節(jié)點，判斷是否存在滿足L(v_i)>L_threshold-T的節(jié)點（即候選網(wǎng)關(guān)節(jié)點）。如果有，則判斷評價因子μ(v_i)并選擇μ(v)值最大的作為最佳網(wǎng)關(guān)；否則，確定該節(jié)點為網(wǎng)關(guān)。移除該網(wǎng)關(guān)分支并更新各節(jié)點流量負載值，并向上訪問其父節(jié)點。

    (3)如果訪問至網(wǎng)關(guān)節(jié)點，則算法結(jié)束；否則，跳轉(zhuǎn)至步驟(1)。

3.3 情形分析

    網(wǎng)關(guān)部署算法根據(jù)樹型拓撲從下往上進行搜索訪問過程中，會出現(xiàn)3種典型情況，具體各情況的節(jié)點位置關(guān)系示意圖如圖2所示。

    類型1：N1節(jié)點的流量負載小于L_threshold，此時將N1連同其所有子節(jié)點一起劃分到根網(wǎng)關(guān)分支；類型2：N3、N4均滿足候選網(wǎng)關(guān)流量負載條件，此時根據(jù)綜合因子μ(v)選擇鏈路質(zhì)量和剩余能量綜合因子較優(yōu)的節(jié)點為最佳網(wǎng)關(guān)；類型3：N4節(jié)點的流量負載小于L_threshold-T，同時其父節(jié)點N5流量負載大于L_threshold，此時選擇N5最為最佳網(wǎng)關(guān)。

4 算法仿真

    為了驗證算法的正確性和有效性，在MATLAB軟件平臺上進行仿真實驗。模擬構(gòu)建6LoWPAN樹型拓撲網(wǎng)絡(luò)，并將網(wǎng)絡(luò)中節(jié)點的流量負載、鏈路質(zhì)量和剩余能量因素進行數(shù)值化體現(xiàn)。在上述構(gòu)建的網(wǎng)絡(luò)中，分別運行基于流量負載的多網(wǎng)關(guān)部署算法LP和基于節(jié)點數(shù)量的Number-base_Placment(NP)算法完成網(wǎng)關(guān)部署。NP算法以節(jié)點數(shù)作為依據(jù)，劃分出樹型拓撲中滿足節(jié)點數(shù)量要求的子網(wǎng)分支，并選擇分支的根節(jié)點作為網(wǎng)關(guān)。對比兩個算法所得到的網(wǎng)關(guān)數(shù)量K和網(wǎng)關(guān)負載均衡度Var，分析多網(wǎng)關(guān)部署算法的性能優(yōu)勢。

4.1 仿真參數(shù)

    實驗在120×120的區(qū)域內(nèi)隨機放置36個節(jié)點，模擬DODAG生成樹型網(wǎng)絡(luò)拓撲圖。在6LoWPAN網(wǎng)絡(luò)中, 網(wǎng)關(guān)負載門限值L_threshold=30、T=5，節(jié)點負載按λ=5的泊松分布生成，鏈路質(zhì)量和剩余能量綜合因子按λ=5指數(shù)分布生成。

    在以上仿真參數(shù)下，生成的6LoPWAN網(wǎng)絡(luò)如圖3所示，其中標識的7號節(jié)點為根網(wǎng)關(guān)。

4.2 網(wǎng)關(guān)部署方案比較

    在相同網(wǎng)絡(luò)中，分別應用LP算法和NP算法進行網(wǎng)關(guān)部署。實驗結(jié)果如圖4和圖5所示，LP算法和NP算法將網(wǎng)絡(luò)劃分成多個分支，其中黑色標識的節(jié)點為各分支的網(wǎng)關(guān)。分析可知，LP算法最終得到6個網(wǎng)關(guān)，節(jié)點編號為：7、11、15、20、29、33。而NP算法最終也得到6個網(wǎng)關(guān)，節(jié)點編號為：7、15、18、20、27、28。結(jié)果表明，兩種算法都能實現(xiàn)6LoWPAN網(wǎng)絡(luò)的多網(wǎng)關(guān)部署。

4.3 網(wǎng)關(guān)數(shù)量和負載均衡比較

    在不同節(jié)點數(shù)量的條件下隨機生成100個網(wǎng)絡(luò)拓撲圖，分別運行LP算法和NP算法。根據(jù)實驗所得到的數(shù)據(jù)統(tǒng)計，求出兩個算法所得到的網(wǎng)關(guān)數(shù)量K和網(wǎng)關(guān)負載均衡度Std的平均值，并對比分析。

    網(wǎng)關(guān)數(shù)量比較結(jié)果如圖6所示，在相同節(jié)點數(shù)量的網(wǎng)絡(luò)中，LP算法和NP算法所得到的網(wǎng)關(guān)數(shù)量大體相近。隨著網(wǎng)絡(luò)中節(jié)點數(shù)的增加，網(wǎng)絡(luò)整體負載增加，網(wǎng)關(guān)數(shù)量隨之增加。負載均衡度的比較結(jié)果如圖7所示，在幾個不同網(wǎng)絡(luò)節(jié)點數(shù)量的網(wǎng)絡(luò)中，LP算法所得到的Std值均小于NP，具有更好的網(wǎng)關(guān)負載均衡。

    因此，LP算法能夠?qū)崿F(xiàn)6LoWPAN的多網(wǎng)關(guān)部署，并且在利用與同等算法數(shù)量接近的網(wǎng)關(guān)實現(xiàn)更好的負載均衡。于此同時，還考慮了數(shù)據(jù)鏈路質(zhì)量和網(wǎng)關(guān)剩余能量這兩個因素，完成了6LoPWAN多網(wǎng)關(guān)系統(tǒng)的多網(wǎng)關(guān)部署。

5 結(jié)論

    本文提出基于負載的網(wǎng)關(guān)部署算法LP，利用6LoWPAN樹型拓撲網(wǎng)絡(luò)的特殊性，從最深子節(jié)點出發(fā)搜索候選網(wǎng)關(guān)，根據(jù)綜合因子得到最佳網(wǎng)關(guān)。仿真實驗表明，本算法在網(wǎng)關(guān)負載均衡方面的表現(xiàn)優(yōu)勢明顯，并且所需網(wǎng)關(guān)數(shù)量與其他算法接近。在實現(xiàn)了負載均衡的同時兼顧網(wǎng)關(guān)數(shù)量，還考慮了鏈路質(zhì)量和剩余能量的額外因素。

參考文獻

[1] KIM H S，PAEK J，BAHK S.QU-RPL：queue utilization based RPL for load balancing in large scale industrial applications[C].IEEE International Conference on Sensing，Communication，and Networking.IEEE，2015：265-273.

[2] KIM H S，KIM H，PAEK J，et al.Load balancing under heavy traffic in RPL routing protocol for low power and lossy networks[J].IEEE Transactions on Mobile Computing，2017，16(4)：964-979.

[3] 姚玉坤，劉耀瑞，徐棟梁.6LoWPAN網(wǎng)絡(luò)中基于負載均衡的分層路由算法[J].南京郵電大學學報(自然科學版)，2017，37(4)：78-83.

[4] 羅鵬，劉爭紅，鄭霖.6LoWPAN多網(wǎng)關(guān)設(shè)計與實現(xiàn)[J].計算機工程與應用，2016，52(23)：148-152.

[5] HA M，KWON K，KIM D，et al.Dynamic and distributed load balancing scheme in multi-gateway based 6LoWPAN[C].IEEE International Conference on Internet of Things.IEEE Computer Society，2014：87-94.

[6] REHENA Z，ROY S，MUKHERJEE N.Topology partitioning in wireless sensor networks using multiple sinks[C].International Conference on Computer and Information Technology.IEEE，2011：251-256.

[7] 邵開麗，付輝.能耗均衡的無線傳感器網(wǎng)絡(luò)多Sink節(jié)點部署優(yōu)化方法[J].儀表技術(shù)與傳感器，2015(9)：106-110.

[8] DANDEKAR D R，DESHMUKH P R.Energy balancing multiple sink optimal deployment in multi-hop wireless sensor networks[C].Advance Computing Conference.IEEE，2013：408-412.

[9] CHATTERJEE P，DAS N.Multiple sink deployment in multi-hop wireless sensor networks to enhance lifetime[C].Applications and Innovations in Mobile Computing.IEEE，2015：48-54.

[10] BHATTACHARJEE S，AGARWAL K.Energy efficient multiple sink placement in wireless sensor networks[C].International Conference on Networking，Systems and Security，2017：1-7.

[11] WU W，LUO J，YANG M.Gateway placement optimization for load balancing in wireless mesh networks[C].International Conference on Computer Supported Cooperative Work in Design.IEEE，2009：408-413.

[12] 劉春曉，常桂然，賈杰，等.無線網(wǎng)狀網(wǎng)中面向負載均衡的網(wǎng)關(guān)部署算法[J].計算機工程，2012，38(21)：107-109.

[13] 黃書強，周繼鵬.基于聚類的無線Mesh網(wǎng)關(guān)選擇及AP分組算法[J].華南理工大學學報(自然科學版)，2011，39(4)：38-43.

[14] 趙云飛，陳志剛，曾鋒.WMN中基于網(wǎng)關(guān)饑餓度的部署算法優(yōu)化[J].中南大學學報(自然科學版)，2013(11)：4492-4498.

[15] ASHRAF U.Energy-aware gateway placement in green wireless mesh networks[J].IEEE Communications Letters，2017，21(1)：156-159.

作者信息:

何艾洲，鄭  霖，屈啟吉

（桂林電子科技大學 廣西無線寬帶通信與信號處理重點實驗室，廣西 桂林541004）