基于模糊層次分析法的RPL路由優(yōu)化協(xié)議

原 豪,曹亞楠

(1.中國人民解放軍61846部隊,河北 涿州 072750;2.北京郵電大學網(wǎng)絡體系構(gòu)建與融合北京市重點實驗室,北京 100876)

低功耗有損網(wǎng)絡LLNs(Low-Power and Lossy Networks)[1-2]是一種廣泛應用于城市網(wǎng)絡、智能電網(wǎng)等不同領域的網(wǎng)絡。LLNs中的節(jié)點在存儲能力、能耗及處理能力等方面受限。節(jié)點之間的鏈路不穩(wěn)定。為此,IETF(Internet Engineering Task Force,),提出了專門應用于該類網(wǎng)絡的路由協(xié)議—RPL(Routing Protocol for Low-power and Lossy Networks)。

RPL是一種距離矢量路由協(xié)議[3]。它根據(jù)目標函數(shù)構(gòu)建有向無環(huán)圖DODAG(Destination Oriented Directed Acyclic Graph)[4]。之后再根據(jù)相關約束條件和目標函數(shù)計算出最優(yōu)路徑。目前,關于RPL的研究在拓撲構(gòu)建和路由選擇時均未綜合全面考慮各個方面的路由度量[5](如候選父節(jié)點的剩余能量、ETX(Expected Number of Retransmissions)、端到端時延及跳數(shù)等)。此外,也有學者提出考慮個別的路由度量,以不同的權(quán)重系數(shù)側(cè)重不同的路由度量以評估候選父節(jié)點(鄰居節(jié)點)成為偏好父節(jié)點的可能性(如文獻[6-7])。但各個路由度量的權(quán)重系數(shù)多是基于專家的個人經(jīng)驗,主觀性太強。

可見現(xiàn)有的對RPL的改進仍存在缺陷。為解決上述問題,本文提出基于模糊層次分析法的RPL路由協(xié)議—RPL-FAHP(RPL Based on Fuzzy Analytic Hierarchy Process,RPL-FAHP)。RPL-FAHP在節(jié)點選擇偏好父節(jié)點(下一跳節(jié)點)時全面綜合考慮候選父節(jié)點的剩余能量、ETX、端到端時延及跳數(shù)。并構(gòu)建新的復合路由度量及目標函數(shù)。同時采用模糊層次分析法[8]確定復合度量中各個路由度量的權(quán)重系數(shù)。節(jié)點根據(jù)新提出的復合路由度量和目標函數(shù)構(gòu)建網(wǎng)絡拓撲結(jié)構(gòu)和選擇路由,進而有效的改善網(wǎng)絡各方面的性能。

本文后續(xù)部分內(nèi)容安排如下:第1節(jié)介紹低功耗有損網(wǎng)絡路由協(xié)議RPL;第2節(jié)詳述新提出的RPL-FAHP協(xié)議并對其進行性能分析;第3節(jié)進行仿真分析;最后第4節(jié)總結(jié)全文并簡介未來工作。

1 RPL路由協(xié)議

RPL主要通過一組ICMPv6[9]消息構(gòu)建網(wǎng)絡拓撲。即節(jié)點通過目標函數(shù)計算自己的Rank值(在DODAG中節(jié)點相對于根節(jié)點的位置)并構(gòu)建有向無環(huán)圖。該有向無環(huán)圖有效地防止了路由環(huán)路的問題。之后,節(jié)點通過目標函數(shù)選擇最優(yōu)路由傳輸數(shù)據(jù)。且目標函數(shù)的設置和節(jié)點Rank值的計算方法可根據(jù)網(wǎng)絡的不同需求靈活變動,從而構(gòu)建相應的網(wǎng)絡拓撲,滿足相應的應用要求。以下將詳述RPL路由協(xié)議。

1.1 ICMPv6

RPL中用到的ICMPv6消息主要有DIO(DODAG Information Object)、DAO(Destination Advertisement Object)、DIS(DODAG Information Solicitation)及DAO-ACK(Destination Advertisement Object Acknowledgement)等。表1簡單介紹了這幾類ICMPv6消息。

表1 RPL控制消息

1.2 目標函數(shù)

目標函數(shù)(Objective Function,OF)[10-12]定義了低功耗有損網(wǎng)絡中拓撲構(gòu)建和路徑選擇的規(guī)則,如“最小ETX”。OF可根據(jù)不同的應用場景設計不同的規(guī)則,滿足不同的優(yōu)化標準。OF主要規(guī)定了RPL節(jié)點的以下3個規(guī)則:①怎樣獲取和更新路由度量信息;②如何計算自己的Rank值;③怎樣選擇偏好父節(jié)點。

1.3 DODAG

有向無環(huán)圖(DODAG)[13-14]中所有節(jié)點以類似于樹狀的拓撲結(jié)構(gòu)連接,所有路徑均指向DODAG的根(Root)節(jié)點。其構(gòu)建過程如下:

如圖1所示,Root節(jié)點和普通RPL節(jié)點隨機分布在網(wǎng)絡區(qū)域中。DODAG的構(gòu)建一般從根節(jié)點(邊界路由器或Sink節(jié)點)開始。即Root節(jié)點首先向自己的鄰居節(jié)點廣播帶有DODAG相關配置信息的DIO消息,其鄰居節(jié)點如節(jié)點1通過DIO獲得發(fā)送節(jié)點的相關信息。若節(jié)點1決定加入該DODAG,則節(jié)點1成為Root的子節(jié)點,之后節(jié)點1將自己的相關信息寫入DIO中,并向鄰居節(jié)點廣播。節(jié)點1的鄰居節(jié)點2收到來自節(jié)點1的DIO消息后,若決定加入該DODAG,則節(jié)點2更新來自節(jié)點1的DIO消息,并向自己的鄰居廣播DIO消息,并給節(jié)點1回復DAO消息。以此類推,網(wǎng)絡中的其他節(jié)點逐漸加入DODAG。若網(wǎng)絡中仍有節(jié)點未收到來自其他節(jié)點發(fā)送的DIO消息,但該節(jié)點想加入該DODAG,如節(jié)點4。則節(jié)點4可主動向自己的鄰居廣播DIS消息以請求加入DODAG。DODAG中的節(jié)點如節(jié)點2收到節(jié)點4的DIS消息后,會向節(jié)點4發(fā)送DIO消息以便節(jié)點4加入DODAG。

圖1 DODAG的簡單構(gòu)建過程

1.4 現(xiàn)有RPL路由協(xié)議存在的問題

RPL及其最新的相關改進協(xié)議主要存在以下問題:①在路徑選擇過程中均未綜合全面考慮各方面的路由度量如候選父節(jié)點的剩余能量、ETX、端到端時延及跳數(shù)等,以至于節(jié)點不能選擇最優(yōu)路徑傳輸數(shù)據(jù),進而在一定程度上影響網(wǎng)絡的性能。②在路徑選擇過程中,若同時考慮2個或3個路由度量時,各個路由度量的權(quán)重系數(shù)多是基于專家的個人經(jīng)驗而確定,這樣的權(quán)重系數(shù)確定方法主觀性太強,易影響網(wǎng)絡性能。③當節(jié)點的候選父節(jié)點集合中只有一個節(jié)點時,仍然執(zhí)行偏好父節(jié)點選擇計算過程,造成不必要的額外開銷和一定延時。

2 RPL-FAHP

基于上文所述RPL路由協(xié)議及其最新的相關改進協(xié)議存在的問題,本文提出一種新的適用于低功耗有損網(wǎng)絡的路由協(xié)議—RPL-FAHP。RPL-FAHP主要包括以下內(nèi)容:①在進行路徑選擇時全面綜合的考慮了候選父節(jié)點的剩余能量、ETX、端到端時延及跳數(shù)4個方面的路由度量。更加全面的分析網(wǎng)絡中各個節(jié)點的性能,選出相對最優(yōu)的節(jié)點為偏好父節(jié)點(下一跳節(jié)點)。②構(gòu)造包含上述4種路由度量的復合路由度量和目標函數(shù)。③提出采用模糊層次分析法確定復合路由度量中各個路由度量的權(quán)重系數(shù)。這樣的權(quán)重系數(shù)確定方法更加客觀、切合網(wǎng)絡實際情況,更好的改善網(wǎng)絡性能。④當候選父節(jié)點數(shù)為1時,提出新的改進方法,進一步減少網(wǎng)絡資源消耗,改善網(wǎng)絡性能。

2.1 RPL-FAHP考慮的路由度量

①跳數(shù)HC(Hop Count)

跳數(shù)是指候選父節(jié)點到根節(jié)點之間的跳數(shù)。如式(1)所示,HCmax表示所有候選父節(jié)點中到根節(jié)點的最大跳數(shù);HC(i)表示候選父節(jié)點i到根節(jié)點所需的跳數(shù)。到根節(jié)點所需最小跳數(shù)的候選父節(jié)點將被選為偏好父節(jié)點。

(1)

②節(jié)點剩余能量RE(Residual Energy)

如式(2)所示,E0(i)和Enow(i)分別表示節(jié)點的最大初始能量和當前剩余能量。利用式(2)可選擇剩余能量較多的節(jié)點作為偏好父節(jié)點,有效地改善網(wǎng)絡壽命,且避免網(wǎng)絡中局部節(jié)點的死亡導致網(wǎng)絡重建而引起更大的時延和消耗更多的能量。

(2)

③端到端時延EED(End-to-End Delay)

如式(3)所示,EEDmax表示節(jié)點通過某一候選父節(jié)點(所有候選父節(jié)點中)到根節(jié)點之間的路徑的最大端到端時延;EED(i)表示節(jié)點通過候選父節(jié)點i到根節(jié)點之間路徑所需的時延。如果節(jié)點通過某一候選父節(jié)點到達根節(jié)點所需的時延最小,則選該候選父節(jié)點為偏好父節(jié)點。

(3)

④ETX

ETX表示在鏈路上成功傳輸數(shù)據(jù)分組所需的傳輸(重傳)次數(shù)。如式(4)所示,ETXmax表示節(jié)點從某一候選父節(jié)點到根節(jié)點的路徑所需的最大ETX;ETX(i)表示節(jié)點從候選父節(jié)點i到根節(jié)點所需的ETX。若節(jié)點從某一候選父節(jié)點到根節(jié)點的路徑具有最小ETX,則選該候選父節(jié)點為偏好父節(jié)點。

(4)

上述4種路由度量對路徑選擇均有重要影響,因此,在網(wǎng)絡拓撲構(gòu)建和路徑選擇時需全面綜合考慮上述4種路由度量。為此,本文提出的RPL-FAHP協(xié)議全面綜合考慮了上述4種路由度量,并提出包含上述4種路由度量的復合度量和目標函數(shù)。

2.2 構(gòu)建復合路由度量及目標函數(shù)

如式(5)所示,F(i)為復合路由度量,其中a1,a2,a3,a4為權(quán)重系數(shù)(用于調(diào)整各個路由度量在復合度量中的重要程度),n表示候選父節(jié)點總數(shù)。

(5)

如式(6)所示,OF為構(gòu)建的目標函數(shù)。

(6)

根據(jù)式(5)和式(6),在選擇偏好父節(jié)點時綜合考慮節(jié)點剩余能量、端到端時延、跳數(shù)及ETX。進而選出最優(yōu)節(jié)點為偏好父節(jié)點,有效地改善網(wǎng)絡性能。

由式(5)和式(6)可知權(quán)重系數(shù)在偏好父節(jié)點的選擇過程中尤為關鍵。不同的權(quán)重系數(shù)可導致不同的選擇結(jié)果。現(xiàn)有的關于復合度量的權(quán)重系數(shù)的確定多是基于專家的個人經(jīng)驗,主觀性太強。為此本文提出的RPL-FAHP協(xié)議采用模糊層次分析法確定復合度量中各個路由度量的權(quán)重系數(shù)。RPL-FAHP結(jié)合各候選父節(jié)點評價的層次結(jié)構(gòu)、模糊一致性矩陣及層次分析法對各個路由度量的權(quán)重因子進行定性和定量的分析,實現(xiàn)各個路由度量最優(yōu)的權(quán)重分配方案,進而選擇最優(yōu)的候選父節(jié)點為偏好父節(jié)點,有效地改善網(wǎng)絡性能。

2.3 FAHP

層次分析法AHP(Analytic Hierarchy Process)[15]是一種簡捷、實用的定性與定量分析相結(jié)合的決策方法,其關鍵在于以一定標度把人的主觀感覺數(shù)量化。它通過把復雜問題中的各種因素劃分為相互聯(lián)系的有序?qū)哟?然后依據(jù)一定的客觀現(xiàn)實判斷,把專家意見和分析的客觀判斷結(jié)果直接有效地結(jié)合起來,將同一層次元素兩兩比較的重要性進行定量描述;最后利用數(shù)學方法計算所有元素的相對權(quán)重的排序向量。

模糊層次分析法FAHP(Fuzzy Analytic Hierarchy Process)是在傳統(tǒng)的層次分析法基礎上,考慮到人們對復雜事物判斷的模糊性,引入模糊一致性矩陣的決策方法。模糊層次分析法很好地解決了AHP判斷矩陣的一致性問題。本文在具體采用模糊層次分析法確定各個路由度量權(quán)重系數(shù)之前,首先作如下假設:

假設第i(i=1,2,3…n)個候選父節(jié)點的第j(j=1,2,3,4)個路由度量的歸一化值為xij(1≤i≤n,1≤j≤m,m=4),則各個候選父節(jié)點的各個路由度量的歸一化值的樣本集可寫為{xij|i=1,2,…,n;j=1,2,…,m},可記為矩陣形式,稱為初始判決矩陣,如式(7)所示。

(7)

假設第j個路由度量對應的權(quán)重系數(shù)為aj(j=1,2 …m),稱f(i)(i=1,2…n)為候選父節(jié)點的綜合評價函數(shù),由路由度量的權(quán)重與路由度量歸一化值xij加權(quán)求和得出,如式(8)所示。

(8)

通過對各個路由度量合理的權(quán)重分配a=(a1,a2,a3,…,am),得到所有候選父節(jié)點的綜合評價值f(i)(i=1,2…n)。則具有最小(或最大)f(i)值對應的候選父節(jié)點可優(yōu)先選為偏好父節(jié)點。而權(quán)重分配a=(a1,a2,a3,…,am)為一個單位矢量,aj表示第j個路由度量的權(quán)重系數(shù),該單位矢量應滿足如下約束條件:

(9)

可見偏好父節(jié)點的選擇為一個約束尋優(yōu)問題,即在給定初始判決矩陣X且滿足式(9)的約束條件下用FAHP求解各路由度量的權(quán)重系數(shù),進而計算出n個候選父節(jié)點的綜合評價值f(i),則偏好父節(jié)點即為minf(i)(或maxf(i))對應的節(jié)點。

本文的綜合評價函數(shù)采用式(5),且根據(jù)式(6)選擇偏好父節(jié)點,即選擇綜合評價函數(shù)最小值對應的候選父節(jié)點為偏好父節(jié)點。以下將詳細介紹采用FAHP法求解復合路由度量中各個路由度量的權(quán)重系數(shù)的過程。

2.4 FAHP確定權(quán)重系數(shù)

定義1設矩陣R=(rij)n×m,若有0≤rij≤1,則稱矩陣R是模糊矩陣。

定義2設矩陣R=(rij)n×m,若有rij+rji=1,則稱矩陣R是模糊互補矩陣。

定義3設有模糊矩陣R=(rij)n×m,若對任意k,有rij=rik-rjk+0.5,則稱矩陣R是模糊一致性矩陣。

2.4.1FAHP實現(xiàn)步驟

①構(gòu)建評價層次分析模型

本文建立3層評價層次結(jié)構(gòu),如圖2所示。

②計算圖2中準則層的準則權(quán)重,確定權(quán)重相量

步驟1 建立模糊判斷矩陣R=(rij)n×n,rij表示本層次中第i個元素與第j個元素之間模糊關系的相關度(即相對重要程度)。為了能夠定量地描述任意兩個路由度量之間的相對重要程度,本文采用表2所示的0.1～0.9標度法[8]。

圖2 層次化評價模型

標度說明0.5兩元素相比較,同等重要0.6兩元素相比,一個元素比另一個元素稍微重要0.7兩元素相比,一個元素比另一個元素明顯重要0.8兩元素相比,一個元素比另一個元素重要得多0.9兩元素相比,一個元素比另一個元素極端重要0.1～0.4反比較;若元素ri與元素rj比較得到評判rij,則元素rj與元素ri比較得到的評判是rji=1-rij

步驟2 求解模糊一致性矩陣。

為避免矩陣變化中的一致性檢驗,首先按照式(10)對判斷矩陣R求行和:

(10)

再利用式(11)做變換,

(11)

從而得到模糊一致性矩陣R′。

步驟3 利用式(12),對模糊一致性矩陣R′ 進行行和歸一化處理,從而求得權(quán)重向量a=(a1,a2,…,am)。

(12)

2.4.2 具體實現(xiàn)

①構(gòu)建模糊判斷矩陣R:

②求解模糊一致性矩陣R′:

③對模糊一致性矩陣進行行和歸一化處理,從而求得權(quán)重向量a=(a1,a2,…,am):

a=[0.221 875 0.290 625 0.240 625 0.246 875]

按照該權(quán)重系數(shù)分配方案計算各個候選父節(jié)點的綜合評價值。即將該權(quán)重系數(shù)帶入式(5),即可求得各個候選父節(jié)點的綜合評價值。再由式(6),即可選出偏好父節(jié)點。即選擇綜合評價函數(shù)最小值對應的候選父節(jié)點為偏好父節(jié)點。

2.5 候選父節(jié)點數(shù)為1時改進處理方法

若節(jié)點只有一個候選父節(jié)點,則該節(jié)點首先等待一段時間以便接收來自其他節(jié)點的DIO消息,以判斷是否還有其他節(jié)點會成為自己的候選父節(jié)點。之后若該節(jié)點的候選父節(jié)點數(shù)量大于等于2,則該節(jié)點通過執(zhí)行RPL-FAHP算法選擇偏好父節(jié)點。若該節(jié)點的候選父節(jié)點數(shù)量仍為1,則該節(jié)點無需執(zhí)行RPL-FAHP算法,直接將這一個候選父節(jié)點選為自己的偏好父節(jié)點。這樣可在一定程度上減少網(wǎng)絡資源的消耗,改善網(wǎng)絡性能。

3 仿真實驗

本文將RPL-FAHP與最新經(jīng)典的RPL路由協(xié)議(0.8×ETX+0.2×RE和0.6×HC+0.4×RE)通過 OPNET14.5 仿真軟件平臺進行性能比較。考察的性能參數(shù)主要有:平均分組丟失率、平均端到端時延及網(wǎng)絡壽命等。

3.1 仿真參數(shù)設置

節(jié)點隨機分布在500 m×500 m的網(wǎng)絡環(huán)境中。數(shù)據(jù)分組的到達服從泊松分布。節(jié)點的初始能量是0.75 J～1 J之間的隨機值。當節(jié)點的剩余能量小于其初始能量的5%時,認為節(jié)點死亡。其他相關的關鍵參數(shù)如表3所示。

表3 仿真參數(shù)設置

表3中E(k,d)[16]可由式(13)計算得出。

(13)

式(13)中的相關參數(shù)如表4所示。

表4 E(k,d)的參數(shù)設置

3.2 仿真結(jié)果分析

①平均分組丟失率

圖3顯示了RPL-FAHP、0.8×ETX+0.2×RE和0.6×HC+0.4×RE在不同節(jié)點密度下的平均分組丟失率。可見在不同節(jié)點密度下RPL-FAHP的平均分組丟失率均明顯低于0.8×ETX+0.2×RE和0.6×HC+0.4×RE。表明RPL-FAHP通過綜合考慮各方面的路由度量,并采用FAHP確定各路由度量最優(yōu)的權(quán)重系數(shù),進而求出最優(yōu)偏好父節(jié)點傳輸數(shù)據(jù)。所以RPL-FAHP可明顯降低分組丟失率,改善網(wǎng)絡性能。

圖3 平均分組丟失率

②平均端到端時延

圖4顯示了RPL-FAHP、0.8×ETX+0.2×RE和0.6×HC+0.4×RE在不同節(jié)點密度下的平均端到端時延。可見在不同節(jié)點密度下RPL-FAHP的平均端到端時延均明顯低于0.8×ETX+0.2×RE和0.6×HC+0.4×RE。表明RPL-FAHP可明顯降低網(wǎng)絡時延。

③平均端到端時延

圖5可看出:在不同節(jié)點密度情況下,RPL-FAHP平均存活的節(jié)點數(shù)大于0.8×ETX+0.2×RE和0.6×HC+0.4×RE。表明RPL-FAHP綜合考慮各個路由度量,全面綜合評價候選父節(jié)點,從而選擇最優(yōu)節(jié)點為偏好父節(jié)點,改善網(wǎng)絡性能。

圖4 平均分端到端時延

圖5 平均存活節(jié)點數(shù)

4 結(jié)束語

為使低功耗有損網(wǎng)絡路由協(xié)議(RPL)在拓撲構(gòu)建及路由選擇時綜合全面考慮各方面的路由度量,且更加客觀的確定各個路由度量的權(quán)重系數(shù),本文提出一種新的基于模糊層次分析法的RPL路由協(xié)議—RPL-FAHP。RPL-FAHP在選擇偏好父節(jié)點時同時考慮節(jié)點剩余能量,端到端時延、跳數(shù)及ETX共4種路由度量;并構(gòu)建新的復合路由度量和目標函數(shù);同時采用模糊層次分析法更加客觀的確定復合路由度量中各個路由度量的權(quán)重系數(shù)。進而求得各個候選父節(jié)點的綜合評價函數(shù)值。最小的綜合評價函數(shù)值對應的候選父節(jié)點即為偏好父節(jié)點。仿真實驗表明RPL-FAHP在分組丟失率、平均端到端時延、網(wǎng)絡壽命等方面均優(yōu)于現(xiàn)有的較新的典型的算法(0.8×ETX+0.2×RE和0.6×HC+0.4×RE)。

在未來的工作中,擬通過研究學習其他的權(quán)重系數(shù)確定方法進一步優(yōu)化路由度量的權(quán)重系數(shù),構(gòu)建更加合適的復合度量和目標函數(shù)進一步優(yōu)化低功耗有損網(wǎng)絡的性能。