原 豪,曹亞楠

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

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

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

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

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

1 RPL路由協(xié)議

RPL主要通過一組ICMPv6[9]消息構(gòu)建網(wǎng)絡(luò)拓?fù)洹＜垂?jié)點通過目標(biāo)函數(shù)計算自己的Rank值(在DODAG中節(jié)點相對于根節(jié)點的位置)并構(gòu)建有向無環(huán)圖。該有向無環(huán)圖有效地防止了路由環(huán)路的問題。之后,節(jié)點通過目標(biāo)函數(shù)選擇最優(yōu)路由傳輸數(shù)據(jù)。且目標(biāo)函數(shù)的設(shè)置和節(jié)點Rank值的計算方法可根據(jù)網(wǎng)絡(luò)的不同需求靈活變動,從而構(gòu)建相應(yīng)的網(wǎng)絡(luò)拓?fù)?滿足相應(yīng)的應(yī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 目標(biāo)函數(shù)

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

1.3 DODAG

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

如圖1所示,Root節(jié)點和普通RPL節(jié)點隨機分布在網(wǎng)絡(luò)區(qū)域中。DODAG的構(gòu)建一般從根節(jié)點(邊界路由器或Sink節(jié)點)開始。即Root節(jié)點首先向自己的鄰居節(jié)點廣播帶有DODAG相關(guān)配置信息的DIO消息,其鄰居節(jié)點如節(jié)點1通過DIO獲得發(fā)送節(jié)點的相關(guān)信息。若節(jié)點1決定加入該DODAG,則節(jié)點1成為Root的子節(jié)點,之后節(jié)點1將自己的相關(guān)信息寫入DIO中,并向鄰居節(jié)點廣播。節(jié)點1的鄰居節(jié)點2收到來自節(jié)點1的DIO消息后,若決定加入該DODAG,則節(jié)點2更新來自節(jié)點1的DIO消息,并向自己的鄰居廣播DIO消息,并給節(jié)點1回復(fù)DAO消息。以此類推,網(wǎng)絡(luò)中的其他節(jié)點逐漸加入DODAG。若網(wǎng)絡(luò)中仍有節(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及其最新的相關(guān)改進(jìn)協(xié)議主要存在以下問題:①在路徑選擇過程中均未綜合全面考慮各方面的路由度量如候選父節(jié)點的剩余能量、ETX、端到端時延及跳數(shù)等,以至于節(jié)點不能選擇最優(yōu)路徑傳輸數(shù)據(jù),進(jìn)而在一定程度上影響網(wǎng)絡(luò)的性能。②在路徑選擇過程中,若同時考慮2個或3個路由度量時,各個路由度量的權(quán)重系數(shù)多是基于專家的個人經(jīng)驗而確定,這樣的權(quán)重系數(shù)確定方法主觀性太強,易影響網(wǎng)絡(luò)性能。③當(dāng)節(jié)點的候選父節(jié)點集合中只有一個節(jié)點時,仍然執(zhí)行偏好父節(jié)點選擇計算過程,造成不必要的額外開銷和一定延時。

2 RPL-FAHP

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

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é)點的最大初始能量和當(dāng)前剩余能量。利用式(2)可選擇剩余能量較多的節(jié)點作為偏好父節(jié)點,有效地改善網(wǎng)絡(luò)壽命,且避免網(wǎng)絡(luò)中局部節(jié)點的死亡導(dǎo)致網(wǎng)絡(luò)重建而引起更大的時延和消耗更多的能量。

(2)

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

如式(3)所示,EEDmax表示節(jié)點通過某一候選父節(jié)點(所有候選父節(jié)點中)到根節(jié)點之間的路徑的最大端到端時延;EED(i)表示節(jié)點通過候選父節(jié)點i到根節(jié)點之間路徑所需的時延。如果節(jié)點通過某一候選父節(jié)點到達(dá)根節(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)絡(luò)拓?fù)錁?gòu)建和路徑選擇時需全面綜合考慮上述4種路由度量。為此,本文提出的RPL-FAHP協(xié)議全面綜合考慮了上述4種路由度量,并提出包含上述4種路由度量的復(fù)合度量和目標(biāo)函數(shù)。

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

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

(5)

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

(6)

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

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

2.3 FAHP

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

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

假設(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)

假設(shè)第j個路由度量對應(yīng)的權(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)值對應(yīng)的候選父節(jié)點可優(yōu)先選為偏好父節(jié)點。而權(quán)重分配a=(a1,a2,a3,…,am)為一個單位矢量,aj表示第j個路由度量的權(quán)重系數(shù),該單位矢量應(yīng)滿足如下約束條件:

(9)

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

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

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

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

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

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

2.4.1FAHP實現(xiàn)步驟

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

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

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

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

圖2 層次化評價模型

標(biāo)度說明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′ 進(jìn)行行和歸一化處理,從而求得權(quán)重向量a=(a1,a2,…,am)。

(12)

2.4.2 具體實現(xiàn)

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

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

③對模糊一致性矩陣進(jìn)行行和歸一化處理,從而求得權(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ù)最小值對應(yīng)的候選父節(jié)點為偏好父節(jié)點。

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

若節(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)絡(luò)資源的消耗,改善網(wǎng)絡(luò)性能。

3 仿真實驗

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

3.1 仿真參數(shù)設(shè)置

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

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

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

(13)

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

表4 E(k,d)的參數(shù)設(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ù),進(jìn)而求出最優(yōu)偏好父節(jié)點傳輸數(shù)據(jù)。所以RPL-FAHP可明顯降低分組丟失率,改善網(wǎng)絡(luò)性能。

圖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)絡(luò)時延。

③平均端到端時延

圖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)絡(luò)性能。

圖4 平均分端到端時延

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

4 結(jié)束語

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

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