文獻(xiàn)標(biāo)識(shí)碼: A
DOI:10.16157/j.issn.0258-7998.181135
中文引用格式: 何艾洲,,鄭霖,,屈啟吉. 基于6LoWPAN多網(wǎng)關(guān)系統(tǒng)的網(wǎng)關(guān)部署算法[J].電子技術(shù)應(yīng)用,2018,,44(11):72-75,,80.
英文引用格式: He Aizhou,Zheng Lin,,Qu Qiji. Gateway deployment algorithm based on 6LoWPAN multi-gateway system[J]. Application of Electronic Technique,,2018,44(11):72-75,,80.
0 引言
隨著物聯(lián)網(wǎng)技術(shù)的飛速發(fā)展和日益普及,,6LoWPAN廣泛應(yīng)用于智能家居,、環(huán)境監(jiān)測和樓宇自動(dòng)化等領(lǐng)域。單網(wǎng)關(guān)架構(gòu)的6LoWPAN存在網(wǎng)關(guān)瓶頸問題,,且不利于大規(guī)模部署,。因此,多網(wǎng)關(guān)系統(tǒng)將是實(shí)現(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é)點(diǎn)間的鏈路質(zhì)量和通信延遲,而且還決定了網(wǎng)絡(luò)整體的容量,。因此,合理的網(wǎng)關(guān)部署是實(shí)現(xiàn)6LoWPAN網(wǎng)絡(luò)性能優(yōu)化的關(guān)鍵,。
針對(duì)6LoWPAN負(fù)載均衡問題的研究,,文獻(xiàn)[1]利用子節(jié)點(diǎn)根據(jù)鄰居節(jié)點(diǎn)的排隊(duì)率和跳距選擇父節(jié)點(diǎn)實(shí)現(xiàn)負(fù)載分擔(dān),并在文獻(xiàn)[2]中對(duì)路由方案進(jìn)行了補(bǔ)充和更新,。文獻(xiàn)[3]提出一種基于負(fù)載均衡的分層路由算法,保證網(wǎng)絡(luò)負(fù)載平衡的同時(shí)提高網(wǎng)絡(luò)生存周期。在6LoWPAN多網(wǎng)的研究中,,文獻(xiàn)[4]提出一種多網(wǎng)關(guān)系統(tǒng)方案,,解決網(wǎng)關(guān)瓶頸問題并提高網(wǎng)絡(luò)吞吐量。文獻(xiàn)[5]在多網(wǎng)關(guān)架構(gòu)的基礎(chǔ)上,,提出一種分布式動(dòng)態(tài)負(fù)載平衡方案實(shí)現(xiàn)全局負(fù)載平衡,。近年來基于LoRa技術(shù)的遠(yuǎn)距離無線廣域網(wǎng)(Long Rage WAN,LoRoWAN)采用多網(wǎng)關(guān)系統(tǒng),,并且在LoRaWAN上實(shí)現(xiàn)了6LoWPAN標(biāo)準(zhǔn),。
在WSN網(wǎng)絡(luò)的sink部署研究中,從用多sink節(jié)點(diǎn)代替單sink節(jié)點(diǎn)的網(wǎng)絡(luò)劃分方案[6]的提出,,到在多sink網(wǎng)絡(luò)中考慮布局和能耗,,提出一種基于啟發(fā)式算法的部署優(yōu)化方案[7]。為了提高多跳WSN的網(wǎng)絡(luò)生存周期,,提出基于粒子群算法的多sink節(jié)點(diǎn)部署算法[8]和分布式貪婪簇生成算法[9],,而文獻(xiàn)[10]提出兩種基于能量的sink局部搜索策略。多網(wǎng)關(guān)部署問題研究常見于WMN網(wǎng)絡(luò),,以負(fù)載均衡為目標(biāo),,通過基于權(quán)值的貪婪算法[11]、改進(jìn)雜交粒子群優(yōu)化算法[12]和優(yōu)化類聚K-means算法[13]完成網(wǎng)關(guān)部署,。在考慮網(wǎng)關(guān)實(shí)際容量的情況下,,文獻(xiàn)[14]在貪婪算法的基礎(chǔ)上定義饑餓度,提出一種能更好實(shí)現(xiàn)負(fù)載均衡的饑餓算法,。文獻(xiàn)[15]以最小化網(wǎng)絡(luò)能耗為目標(biāo),,提出一種基于啟發(fā)式的貪婪算法實(shí)現(xiàn)綠色WMN的網(wǎng)關(guān)部署。
上述研究中,,WSN網(wǎng)絡(luò)為星型拓?fù)?,WMN網(wǎng)絡(luò)為網(wǎng)狀拓?fù)?,其拓?fù)浣Y(jié)構(gòu)對(duì)網(wǎng)關(guān)部署的約束性小。6LoWPAN網(wǎng)絡(luò)為樹型拓?fù)?,網(wǎng)關(guān)部署算法需要考慮節(jié)點(diǎn)位置和網(wǎng)絡(luò)拓?fù)涞年P(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)均衡,也會(huì)導(dǎo)致網(wǎng)關(guān)之間負(fù)載不平衡,。本文以最小化網(wǎng)關(guān)數(shù)量和網(wǎng)關(guān)間負(fù)載均衡為目標(biāo),,在貪婪算法的思想上結(jié)合6LoWPAN樹型拓?fù)渚W(wǎng)絡(luò)的特殊性,提出一種基于負(fù)載的多網(wǎng)關(guān)部署算法,,以最少網(wǎng)關(guān)數(shù)量實(shí)現(xiàn)網(wǎng)關(guān)負(fù)載均衡,。
1 網(wǎng)絡(luò)模型搭建
在6LoWPAN中考慮多網(wǎng)關(guān)部署問題,用圖G(V,,E)表示待優(yōu)化網(wǎng)絡(luò),。節(jié)點(diǎn)v∈V為6LoWPAN中的節(jié)點(diǎn),可為6LR或者6LBR,。在6LoWPAN網(wǎng)絡(luò)中,,6LR負(fù)責(zé)轉(zhuǎn)發(fā)和路由IPv6數(shù)據(jù)包;而6LBR負(fù)責(zé)6LoWPAN網(wǎng)絡(luò)和其他IP網(wǎng)絡(luò)的數(shù)據(jù)交互,,即實(shí)現(xiàn)網(wǎng)關(guān)功能,。設(shè)v具有一個(gè)圓形的可通信范圍,根據(jù)目標(biāo)函數(shù)選擇與在該范圍內(nèi)的節(jié)點(diǎn)建立拓?fù)溥B接,。在構(gòu)建好的拓?fù)浣Y(jié)構(gòu)中,,與v連接的節(jié)點(diǎn)分為父節(jié)點(diǎn)Np(v)和子節(jié)點(diǎn)集Nc(v),N(v)=Np(v)+Nc(v),。由于6LoWPAN的DODAG樹型網(wǎng)絡(luò)拓?fù)涞奶厥庑?,v至多有一個(gè)父節(jié)點(diǎn)但可以有多個(gè)子節(jié)點(diǎn)或者沒有子節(jié)點(diǎn)。對(duì)于節(jié)點(diǎn)u∈N(v),,存在邊e(u,,v)∈E,e(u,,v)為v和u之間的雙向通信鏈路,,表示節(jié)點(diǎn)v和u之間已經(jīng)建立拓?fù)溥B接。
2 問題描述
研究6LoWPAN多網(wǎng)關(guān)網(wǎng)絡(luò)設(shè)計(jì),,通過合理部署網(wǎng)關(guān),,使得各網(wǎng)關(guān)間負(fù)載平衡,,同時(shí)將鏈路質(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é)點(diǎn)流量負(fù)載和綜合因子進(jìn)行網(wǎng)關(guān)選擇,用最少的網(wǎng)關(guān)數(shù)量實(shí)現(xiàn)網(wǎng)關(guān)間的負(fù)載均衡,。然后,,根據(jù)網(wǎng)關(guān)部署的結(jié)果劃分子網(wǎng)分支,將在樹型拓?fù)渲幸酝痪W(wǎng)關(guān)作為根的節(jié)點(diǎn)劃分到一個(gè)子網(wǎng)分支,。
條件(1)表示V中任一節(jié)點(diǎn)有且只有一個(gè)網(wǎng)關(guān),;條件(2)表示候選網(wǎng)關(guān)需要滿足的負(fù)載門限要求;條件(3)表示選擇候選網(wǎng)關(guān)中綜合因子最大的節(jié)點(diǎn)作為網(wǎng)關(guān)節(jié)點(diǎn),;條件(4)表示網(wǎng)關(guān)的負(fù)載為子網(wǎng)分支內(nèi)所有節(jié)點(diǎn)和網(wǎng)關(guān)節(jié)點(diǎn)本身的權(quán)值之和。將6LoWPAN多網(wǎng)關(guān)部署問題具體化:以最小網(wǎng)關(guān)數(shù)量實(shí)現(xiàn)網(wǎng)關(guān)間負(fù)載均衡,。通過考慮節(jié)點(diǎn)負(fù)載得到候選網(wǎng)關(guān),,再根據(jù)鏈路質(zhì)量和剩余能量的綜合因子,從候選網(wǎng)關(guān)中選出最優(yōu)網(wǎng)關(guān),。本文在貪婪算法的基礎(chǔ)上,,結(jié)合6LoWPAN網(wǎng)絡(luò)樹型拓?fù)涞奶攸c(diǎn),提出一種多網(wǎng)關(guān)部署算法Load-base_Placement(LP)來獲得問題的最優(yōu)解,。
3 多網(wǎng)關(guān)部署算法
3.1 算法思路
由于6LoWPAN網(wǎng)絡(luò)采用的是樹型拓?fù)浣Y(jié)構(gòu),,其網(wǎng)絡(luò)中節(jié)點(diǎn)的流量負(fù)載具有累加特性。位于根節(jié)點(diǎn)和葉子節(jié)點(diǎn)之間的中間路由節(jié)點(diǎn)不僅要承擔(dān)自身流量負(fù)載,,還要負(fù)責(zé)其子節(jié)點(diǎn)的數(shù)據(jù)轉(zhuǎn)發(fā),。在樹型拓?fù)渚W(wǎng)絡(luò)中,從葉子節(jié)點(diǎn)至根節(jié)點(diǎn)流量負(fù)載累積增加,。因此,,算法采取從葉子節(jié)點(diǎn)開始沿樹型拓?fù)渫现粮泳W(wǎng)關(guān)的策略,搜索候選網(wǎng)關(guān),,并確定最佳網(wǎng)關(guān),。
算法大致過程如下:在現(xiàn)有6LoWPAN樹型拓?fù)渚W(wǎng)絡(luò)中,根據(jù)各節(jié)點(diǎn)流量負(fù)載統(tǒng)計(jì)結(jié)果,,進(jìn)行權(quán)值化處理,。從距根節(jié)點(diǎn)跳距最大且有較大流量負(fù)載的葉子節(jié)點(diǎn)開始,往上至根節(jié)點(diǎn),,搜索滿足流量負(fù)載條件的候選網(wǎng)關(guān)節(jié)點(diǎn),。根據(jù)鏈路質(zhì)量和剩余能量所構(gòu)成的評(píng)價(jià)因子,在候選網(wǎng)關(guān)選擇最佳網(wǎng)關(guān)并確定對(duì)應(yīng)子網(wǎng)分支,,移除該分支與網(wǎng)絡(luò)中其他節(jié)點(diǎn)的鏈路連接,。在移除已經(jīng)確定的子網(wǎng)分支后,,更新網(wǎng)絡(luò)中剩余節(jié)點(diǎn)的流量負(fù)載值,并再次執(zhí)行搜索,,當(dāng)訪問至根網(wǎng)關(guān)時(shí)算法結(jié)束,。
3.2 算法描述
輸入:初始的網(wǎng)關(guān)節(jié)點(diǎn)序列(只有一個(gè)根網(wǎng)關(guān));
輸出:完整的網(wǎng)關(guān)節(jié)點(diǎn)序列和子網(wǎng)分支劃分方案,。
算法步驟如下,。
(1)訪問當(dāng)前網(wǎng)絡(luò)中距根節(jié)點(diǎn)跳距最大且有較大流量負(fù)載的葉子節(jié)點(diǎn)。
(2)對(duì)節(jié)點(diǎn)流量負(fù)載進(jìn)行判斷,,如果L(vi)<Lthreshold,,則向上訪問其父節(jié)點(diǎn),如果其父節(jié)點(diǎn)為根網(wǎng)關(guān),,則將此分支移除,;如果L(vi)>Lthreshold,則向下回溯其子節(jié)點(diǎn),,判斷是否存在滿足L(vi)>Lthreshold-T的節(jié)點(diǎn)(即候選網(wǎng)關(guān)節(jié)點(diǎn)),。如果有,則判斷評(píng)價(jià)因子μ(vi)并選擇μ(v)值最大的作為最佳網(wǎng)關(guān),;否則,,確定該節(jié)點(diǎn)為網(wǎng)關(guān)。移除該網(wǎng)關(guān)分支并更新各節(jié)點(diǎn)流量負(fù)載值,,并向上訪問其父節(jié)點(diǎn),。
(3)如果訪問至網(wǎng)關(guān)節(jié)點(diǎn),則算法結(jié)束,;否則,,跳轉(zhuǎn)至步驟(1)。
3.3 情形分析
網(wǎng)關(guān)部署算法根據(jù)樹型拓?fù)鋸南峦线M(jìn)行搜索訪問過程中,,會(huì)出現(xiàn)3種典型情況,,具體各情況的節(jié)點(diǎn)位置關(guān)系示意圖如圖2所示。
類型1:N1節(jié)點(diǎn)的流量負(fù)載小于Lthreshold,,此時(shí)將N1連同其所有子節(jié)點(diǎn)一起劃分到根網(wǎng)關(guān)分支,;類型2:N3、N4均滿足候選網(wǎng)關(guān)流量負(fù)載條件,,此時(shí)根據(jù)綜合因子μ(v)選擇鏈路質(zhì)量和剩余能量綜合因子較優(yōu)的節(jié)點(diǎn)為最佳網(wǎng)關(guān),;類型3:N4節(jié)點(diǎn)的流量負(fù)載小于Lthreshold-T,同時(shí)其父節(jié)點(diǎn)N5流量負(fù)載大于Lthreshold,,此時(shí)選擇N5最為最佳網(wǎng)關(guān),。
4 算法仿真
為了驗(yàn)證算法的正確性和有效性,在MATLAB軟件平臺(tái)上進(jìn)行仿真實(shí)驗(yàn)。模擬構(gòu)建6LoWPAN樹型拓?fù)渚W(wǎng)絡(luò),,并將網(wǎng)絡(luò)中節(jié)點(diǎn)的流量負(fù)載,、鏈路質(zhì)量和剩余能量因素進(jìn)行數(shù)值化體現(xiàn)。在上述構(gòu)建的網(wǎng)絡(luò)中,,分別運(yùn)行基于流量負(fù)載的多網(wǎng)關(guān)部署算法LP和基于節(jié)點(diǎn)數(shù)量的Number-base_Placment(NP)算法完成網(wǎng)關(guān)部署,。NP算法以節(jié)點(diǎn)數(shù)作為依據(jù),劃分出樹型拓?fù)渲袧M足節(jié)點(diǎn)數(shù)量要求的子網(wǎng)分支,,并選擇分支的根節(jié)點(diǎn)作為網(wǎng)關(guān),。對(duì)比兩個(gè)算法所得到的網(wǎng)關(guān)數(shù)量K和網(wǎng)關(guān)負(fù)載均衡度Var,分析多網(wǎng)關(guān)部署算法的性能優(yōu)勢,。
4.1 仿真參數(shù)
實(shí)驗(yàn)在120×120的區(qū)域內(nèi)隨機(jī)放置36個(gè)節(jié)點(diǎn),,模擬DODAG生成樹型網(wǎng)絡(luò)拓?fù)鋱D。在6LoWPAN網(wǎng)絡(luò)中, 網(wǎng)關(guān)負(fù)載門限值Lthreshold=30,、T=5,,節(jié)點(diǎn)負(fù)載按λ=5的泊松分布生成,鏈路質(zhì)量和剩余能量綜合因子按λ=5指數(shù)分布生成,。
在以上仿真參數(shù)下,,生成的6LoPWAN網(wǎng)絡(luò)如圖3所示,其中標(biāo)識(shí)的7號(hào)節(jié)點(diǎn)為根網(wǎng)關(guān),。
4.2 網(wǎng)關(guān)部署方案比較
在相同網(wǎng)絡(luò)中,分別應(yīng)用LP算法和NP算法進(jìn)行網(wǎng)關(guān)部署,。實(shí)驗(yàn)結(jié)果如圖4和圖5所示,,LP算法和NP算法將網(wǎng)絡(luò)劃分成多個(gè)分支,其中黑色標(biāo)識(shí)的節(jié)點(diǎn)為各分支的網(wǎng)關(guān),。分析可知,,LP算法最終得到6個(gè)網(wǎng)關(guān),節(jié)點(diǎn)編號(hào)為:7,、11,、15、20,、29,、33。而NP算法最終也得到6個(gè)網(wǎng)關(guān),,節(jié)點(diǎn)編號(hào)為:7,、15、18,、20,、27、28,。結(jié)果表明,,兩種算法都能實(shí)現(xiàn)6LoWPAN網(wǎng)絡(luò)的多網(wǎng)關(guān)部署,。
4.3 網(wǎng)關(guān)數(shù)量和負(fù)載均衡比較
在不同節(jié)點(diǎn)數(shù)量的條件下隨機(jī)生成100個(gè)網(wǎng)絡(luò)拓?fù)鋱D,分別運(yùn)行LP算法和NP算法,。根據(jù)實(shí)驗(yàn)所得到的數(shù)據(jù)統(tǒng)計(jì),,求出兩個(gè)算法所得到的網(wǎng)關(guān)數(shù)量K和網(wǎng)關(guān)負(fù)載均衡度Std的平均值,并對(duì)比分析,。
網(wǎng)關(guān)數(shù)量比較結(jié)果如圖6所示,,在相同節(jié)點(diǎn)數(shù)量的網(wǎng)絡(luò)中,LP算法和NP算法所得到的網(wǎng)關(guān)數(shù)量大體相近,。隨著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)的增加,,網(wǎng)絡(luò)整體負(fù)載增加,網(wǎng)關(guān)數(shù)量隨之增加,。負(fù)載均衡度的比較結(jié)果如圖7所示,,在幾個(gè)不同網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量的網(wǎng)絡(luò)中,LP算法所得到的Std值均小于NP,,具有更好的網(wǎng)關(guān)負(fù)載均衡,。
因此,LP算法能夠?qū)崿F(xiàn)6LoWPAN的多網(wǎng)關(guān)部署,,并且在利用與同等算法數(shù)量接近的網(wǎng)關(guān)實(shí)現(xiàn)更好的負(fù)載均衡,。于此同時(shí),還考慮了數(shù)據(jù)鏈路質(zhì)量和網(wǎng)關(guān)剩余能量這兩個(gè)因素,,完成了6LoPWAN多網(wǎng)關(guān)系統(tǒng)的多網(wǎng)關(guān)部署,。
5 結(jié)論
本文提出基于負(fù)載的網(wǎng)關(guān)部署算法LP,利用6LoWPAN樹型拓?fù)渚W(wǎng)絡(luò)的特殊性,,從最深子節(jié)點(diǎn)出發(fā)搜索候選網(wǎng)關(guān),,根據(jù)綜合因子得到最佳網(wǎng)關(guān)。仿真實(shí)驗(yàn)表明,,本算法在網(wǎng)關(guān)負(fù)載均衡方面的表現(xiàn)優(yōu)勢明顯,,并且所需網(wǎng)關(guān)數(shù)量與其他算法接近。在實(shí)現(xiàn)了負(fù)載均衡的同時(shí)兼顧網(wǎng)關(guān)數(shù)量,,還考慮了鏈路質(zhì)量和剩余能量的額外因素,。
參考文獻(xiàn)
[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ò)中基于負(fù)載均衡的分層路由算法[J].南京郵電大學(xué)學(xué)報(bào)(自然科學(xué)版),,2017,37(4):78-83.
[4] 羅鵬,,劉爭紅,,鄭霖.6LoWPAN多網(wǎng)關(guān)設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用,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é)點(diǎn)部署優(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)中面向負(fù)載均衡的網(wǎng)關(guān)部署算法[J].計(jì)算機(jī)工程,,2012,,38(21):107-109.
[13] 黃書強(qiáng),周繼鵬.基于聚類的無線Mesh網(wǎng)關(guān)選擇及AP分組算法[J].華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版),,2011,,39(4):38-43.
[14] 趙云飛,陳志剛,曾鋒.WMN中基于網(wǎng)關(guān)饑餓度的部署算法優(yōu)化[J].中南大學(xué)學(xué)報(bào)(自然科學(xué)版),,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.
作者信息:
何艾洲,,鄭 霖,,屈啟吉
(桂林電子科技大學(xué) 廣西無線寬帶通信與信號(hào)處理重點(diǎn)實(shí)驗(yàn)室,廣西 桂林541004)