0 引言

    隨著物聯網技術的飛速發展和日益普及，6LoWPAN廣泛應用于智能家居、環境監測和樓宇自動化等領域。單網關架構的6LoWPAN存在網關瓶頸問題，且不利于大規模部署。因此，多網關系統將是實現WSN和Internet互聯的高效模式，網絡系統示意如圖1所示，其中A為根網關，B、C為部署網關。在多網關系統中，網關位置的選擇不僅影響節點間的鏈路質量和通信延遲，而且還決定了網絡整體的容量。因此，合理的網關部署是實現6LoWPAN網絡性能優化的關鍵。

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

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

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

1 網絡模型搭建

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

2 問題描述

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

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

3 多網關部署算法

3.1 算法思路

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

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

3.2 算法描述

    輸入：初始的網關節點序列（只有一個根網關）；

    輸出：完整的網關節點序列和子網分支劃分方案。

    算法步驟如下。

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

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

    (3)如果訪問至網關節點，則算法結束；否則，跳轉至步驟(1)。

3.3 情形分析

    網關部署算法根據樹型拓撲從下往上進行搜索訪問過程中，會出現3種典型情況，具體各情況的節點位置關系示意圖如圖2所示。

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

4 算法仿真

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

4.1 仿真參數

    實驗在120×120的區域內隨機放置36個節點，模擬DODAG生成樹型網絡拓撲圖。在6LoWPAN網絡中, 網關負載門限值L_threshold=30、T=5，節點負載按λ=5的泊松分布生成，鏈路質量和剩余能量綜合因子按λ=5指數分布生成。

    在以上仿真參數下，生成的6LoPWAN網絡如圖3所示，其中標識的7號節點為根網關。

4.2 網關部署方案比較

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

4.3 網關數量和負載均衡比較

    在不同節點數量的條件下隨機生成100個網絡拓撲圖，分別運行LP算法和NP算法。根據實驗所得到的數據統計，求出兩個算法所得到的網關數量K和網關負載均衡度Std的平均值，并對比分析。

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

    因此，LP算法能夠實現6LoWPAN的多網關部署，并且在利用與同等算法數量接近的網關實現更好的負載均衡。于此同時，還考慮了數據鏈路質量和網關剩余能量這兩個因素，完成了6LoPWAN多網關系統的多網關部署。

5 結論

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

參考文獻

[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網絡中基于負載均衡的分層路由算法[J].南京郵電大學學報(自然科學版)，2017，37(4)：78-83.

[4] 羅鵬，劉爭紅，鄭霖.6LoWPAN多網關設計與實現[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] 邵開麗，付輝.能耗均衡的無線傳感器網絡多Sink節點部署優化方法[J].儀表技術與傳感器，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] 劉春曉，常桂然，賈杰，等.無線網狀網中面向負載均衡的網關部署算法[J].計算機工程，2012，38(21)：107-109.

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

[14] 趙云飛，陳志剛，曾鋒.WMN中基于網關饑餓度的部署算法優化[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）