陳蘇海，黨向盈

(1.徐州工程學(xué)院 信電工程學(xué)院，江蘇 徐州 221000；2.中國礦業(yè)大學(xué) 信息與控制學(xué)院，江蘇 徐州 221000)

0 引 言

低功耗有損網(wǎng)絡(luò)(low power and lossy networks，LLN)[1-5]通過網(wǎng)關(guān)或者邊界路由器直接與互聯(lián)網(wǎng)進行數(shù)據(jù)交互，使得LLN擁有較好的互操作性和靈活性。因此，LLN在工業(yè)控制、智能家居和醫(yī)療保健等領(lǐng)域擁有較好的應(yīng)用前景。考慮到LLN廣泛的應(yīng)用場景，國際互聯(lián)網(wǎng)工程任務(wù)組提出了一種適用于LLN網(wǎng)絡(luò)的IPv6路由協(xié)議(IPv6 based routing protocol for LLN，RPL)[6,7]。

當(dāng)前，學(xué)術(shù)界已對單路徑RPL路由協(xié)議展開大量研究。文獻[8]僅將傳輸跳數(shù)作為選擇最優(yōu)父節(jié)點的路由度量，而未考慮無線鏈路質(zhì)量，可能導(dǎo)致網(wǎng)絡(luò)中鏈路質(zhì)量不佳的節(jié)點被選作為父節(jié)點，從而使數(shù)據(jù)包的丟包率上升，增大節(jié)點的能耗。為了避免將無線鏈路不佳的節(jié)點選作父節(jié)點，文獻[9]中將數(shù)據(jù)包的期望傳輸次數(shù)作為選擇父節(jié)點的判據(jù)，卻忽略了節(jié)點的剩余能量，極有可能將剩余能量不足的節(jié)點選作當(dāng)前父節(jié)點，從而加快了此類節(jié)點的能量消耗速率，縮短了網(wǎng)絡(luò)生存時間。為了避免將剩余能量不足的節(jié)點選作父節(jié)點，文獻[10]中將節(jié)點的剩余能量作為選擇父節(jié)點的路由判據(jù)，可能導(dǎo)致無線鏈路質(zhì)量較差而擁有充足剩余能量的節(jié)點被選作為父節(jié)點，增加了其子節(jié)點丟包重傳的次數(shù)，從而降低了網(wǎng)絡(luò)吞吐量和增加了節(jié)點能耗。為了避免文獻[9]和文獻[10]中存在的問題，文獻[11]中綜合考慮了節(jié)點剩余能量和無線鏈路質(zhì)量。然而，由于文獻[11]未將節(jié)點當(dāng)前緩存占用率考慮在內(nèi)，一旦遇到突發(fā)緊急情況需要傳輸大量數(shù)據(jù)時，容易產(chǎn)生網(wǎng)絡(luò)擁塞，從而嚴重影響數(shù)據(jù)的傳輸。文獻[12]僅將節(jié)點的緩存占用率作為路由度量，而未考慮節(jié)點間的無線鏈路質(zhì)量，從而加劇了節(jié)點丟包重傳的能耗。

上述針對單路徑RPL路由協(xié)議的研究主要存在以下兩個方面的不足：①在網(wǎng)絡(luò)拓撲初始化的過程中，路由度量的選擇過于單一，無法有效地實現(xiàn)網(wǎng)絡(luò)負載均衡，從而不能延長網(wǎng)絡(luò)壽命；②在選擇最優(yōu)父節(jié)點的過程中，僅僅考慮一跳范圍內(nèi)的數(shù)據(jù)傳輸代價而未考慮整條路徑上的數(shù)據(jù)傳輸代價影響了最優(yōu)父節(jié)點的選擇，導(dǎo)致無法有效地提升網(wǎng)絡(luò)各方面的性能。

為了盡可能地解決上述所存在的問題，本文提出了一種基于負載均衡的單路徑LLN路由協(xié)議(load balance-based single path routing protocol for LLN，LB-RPL)，并對該協(xié)議的具體操作過程進行了詳實的分析以及對該協(xié)議的網(wǎng)絡(luò)性能進行了模擬仿真對比和驗證。

1 RPL路由構(gòu)建原理

在創(chuàng)建面向目的地有向無循環(huán)圖(destination oriented directed acyclic graph，DODAG)的過程中，RPL路由協(xié)議制定了3種常用的控制消息：DODAG信息對象消息(DODAG information object，DIO)、面向目的地有向無循環(huán)圖請求消息(DODAG information solicitation，DIS)以及面向目的地有向無循環(huán)圖目的地通告消息(destination advertisement object，DAO)。DIO消息的主要功能是為了創(chuàng)建上行路由和維護網(wǎng)絡(luò)拓撲的連通性，由sink節(jié)點發(fā)起；在DODAG構(gòu)建過程中，DAO消息主要用于回應(yīng)DIO消息，從而完成下行路由的構(gòu)建；DIS消息主要用于路由請求，鏈路故障節(jié)點或是新節(jié)點均可通過廣播DIS消息可以主動請求加入到DODAG中。DODAG構(gòu)建流程如圖1所示。

圖1 DODAG構(gòu)建流程

DODAG的構(gòu)建具體步驟如下：①sink節(jié)點向其鄰居節(jié)點周期性的廣播DIO消息；②sink節(jié)點的鄰居節(jié)點A成功接收到sink節(jié)點廣播的DIO消息之后，將sink節(jié)點作為父節(jié)點，并回復(fù)包含自身路由前綴信息的DAO消息；③節(jié)點A重復(fù)sink節(jié)點的操作過程，節(jié)點B重復(fù)節(jié)點A的操作過程；④由于節(jié)點C在一段時間內(nèi)未接收到其鄰居節(jié)點廣播的DIO消息，于是主動廣播DIS消息；⑤節(jié)點B接收到節(jié)點C廣播的DIS消息后，向節(jié)點C單播一個DIO消息；⑥節(jié)點C接收到DIO消息后，向節(jié)點B回復(fù)一個DAO消息；⑦節(jié)點A和節(jié)點B轉(zhuǎn)發(fā)該DAO消息直至根節(jié)點，至此DODAG構(gòu)建完成。

2 LB-RPL路由協(xié)議

針對LLN中現(xiàn)有單路徑路由協(xié)議在網(wǎng)絡(luò)拓撲構(gòu)建過程中考慮的路由度量過于單一，以及在選擇最優(yōu)父節(jié)點時僅依據(jù)一跳范圍內(nèi)的數(shù)據(jù)傳輸代價而無法有效地均衡節(jié)點能耗和延長網(wǎng)絡(luò)壽命等問題，LB-RPL路由協(xié)議中主要提出了以下3種優(yōu)化策略：①在備選父節(jié)點的選擇過程中，對選擇備選父節(jié)點的條件進行限制，從而選出合適的最優(yōu)父節(jié)點；②在路由度量值的計算過程中，綜合考慮多種路由度量，避免單一路由度量對網(wǎng)絡(luò)性能所帶來的影響；③在選擇最優(yōu)父節(jié)點的過程中，考慮整條路徑上的數(shù)據(jù)傳輸代價，最終選擇數(shù)據(jù)傳輸代價相對較小的備選父節(jié)點作為最優(yōu)父節(jié)點。

2.1 備選父節(jié)點的選擇

在DODAG的構(gòu)建過程中，為了降低單一路由度量對最優(yōu)父節(jié)點的選擇所產(chǎn)生的影響，在選擇備選父節(jié)點時需滿足以下3個限制條件：第一，節(jié)點與其備選父節(jié)點之間的無線鏈路質(zhì)量應(yīng)高于預(yù)設(shè)的鏈路質(zhì)量閾值，從而避免選擇無線鏈路質(zhì)量較差的節(jié)點作為父節(jié)點。在本文中，無線鏈路質(zhì)量低于0.7的節(jié)點將不能作為備選父節(jié)點；第二，為了使節(jié)點的能耗均衡，剩余能量較低的節(jié)點(低于能量閾值)不能作為備選父節(jié)點。在本文中能量閾值為節(jié)點初始能量的20%；第三，備選父節(jié)點的緩存占用率應(yīng)低于預(yù)設(shè)的網(wǎng)絡(luò)擁塞閾值，從而避免選擇高負載的節(jié)點作為父節(jié)點。在本文中網(wǎng)絡(luò)擁塞閾值設(shè)定為節(jié)點最大緩存的80%。

在網(wǎng)絡(luò)拓撲初始化過程中，網(wǎng)絡(luò)中每個節(jié)點為了獲知彼此之間的內(nèi)存空間占用情況、剩余能量和鏈路質(zhì)量，分別將上述3種信息添加到周期性廣播的DIO消息中。因此，節(jié)點在選擇備選父節(jié)點時，只需依次判斷其鄰居節(jié)點的上述3種信息是否滿足要求。若滿足要求，則將該鄰居節(jié)點作為備選父節(jié)點；反之，則將該DIO消息丟棄。圖2所示為LB-RPL路由協(xié)議選擇備選父節(jié)點的流程。

圖2 備選父節(jié)點的選擇

2.2 路由度量值的計算

在網(wǎng)絡(luò)構(gòu)建過程中，當(dāng)節(jié)點獲知其所有備選父節(jié)點信息之后，計算與各個備選父節(jié)點之間的路由度量值。在路由度量值的計算過程中，為了有效地避免選擇單一路由度量對網(wǎng)絡(luò)性能所產(chǎn)生的不良影響，因此需要將多種路由度量進行有效地融合。下面以網(wǎng)絡(luò)中的節(jié)點i為例，對多種路由度量有效融合的實際操作步驟如下：

步驟1 根據(jù)節(jié)點i的當(dāng)前剩余能量計算其期望壽命，從而有利于避免潛在子節(jié)點選擇剩余能量非最佳的備選父節(jié)點作為最優(yōu)父節(jié)點。節(jié)點當(dāng)前期望壽命[13]可由如下幾個過程獲?。?/p>

(1)統(tǒng)計節(jié)點i的數(shù)據(jù)包發(fā)送速率，如式(1)所示。其中，Tgen(i)表示節(jié)點i的數(shù)據(jù)包發(fā)送速率，Tj表示其子節(jié)點j的數(shù)據(jù)包發(fā)送速率

(1)

(2)計算節(jié)點i將在一段時間內(nèi)所收集的數(shù)據(jù)包成功發(fā)送至其最優(yōu)父節(jié)點k大致所需要發(fā)送的平均次數(shù)，如式(2)所示。其中，ETX(i,k)表示節(jié)點i成功發(fā)送單個數(shù)據(jù)包到達其最優(yōu)父節(jié)點k大致所需要發(fā)送的平均次數(shù)

Ni=Ti×ETX(i,k)

(2)

(3)計算節(jié)點i將在一段時間內(nèi)所收集的數(shù)據(jù)包成功發(fā)送至其最優(yōu)父節(jié)點k大致所耗費的時間，如式(3)所示。其中，data_rate表示節(jié)點i的數(shù)據(jù)包傳輸速率

(3)

(4)計算節(jié)點i將在一段時間內(nèi)所收集的數(shù)據(jù)包成功發(fā)送至其最優(yōu)父節(jié)點k的能量大致消耗速率，如式(4)所示。其中，Ptx(i)被定義為節(jié)點i的數(shù)據(jù)包發(fā)送功率

(4)

(5)最后，依據(jù)節(jié)點i的當(dāng)前剩余能量以及能量消耗速率便可計算出其期望壽命，如式(5)所示。其中，Eres(i)表示節(jié)點i當(dāng)前剩余能量

(5)

步驟2 計算節(jié)點i的緩存占用率，從而有利于避免節(jié)點i的下游節(jié)點選擇高負載的備選父節(jié)點作為最優(yōu)父節(jié)點

(6)

式中：buffer_occupancyi反映了節(jié)點i的緩存空間被占用的情況，buffer_size被定義為節(jié)點i的緩存空間大小。

步驟3 在LLN網(wǎng)絡(luò)創(chuàng)建過程中，節(jié)點i根據(jù)所統(tǒng)計子節(jié)點發(fā)回的DAO消息的個數(shù)便可獲得當(dāng)前處于連接狀態(tài)的子節(jié)點數(shù)量，從而有利于避免節(jié)點i的下游節(jié)點選擇子節(jié)點數(shù)量較多的備選父節(jié)點作為最優(yōu)父節(jié)點。

步驟4 節(jié)點i將其期望壽命、緩存占用率和當(dāng)前子節(jié)點數(shù)量相關(guān)度量信息添加到DIO消息中，并廣播攜帶上述度量信息的DIO消息。

步驟5 節(jié)點i的鄰居節(jié)點從接收到的DIO消息中提取出節(jié)點i的期望壽命、緩存占用率以及其當(dāng)前子節(jié)點數(shù)量后，根據(jù)式(7)計算與節(jié)點i之間的路由度量值，路由度量值的大小能夠反映出節(jié)點的數(shù)據(jù)傳輸代價，即路由度量值越大，節(jié)點的傳輸代價相對越小

(7)

2.3 最優(yōu)父節(jié)點選擇策略

在DODAG的構(gòu)建過程中，在選擇最優(yōu)父節(jié)點時綜合考慮整條路徑的數(shù)據(jù)傳輸代價。通過計算整條傳輸路徑上的總度量值大小判斷備選父節(jié)點的優(yōu)先級。總度量值越大，備選父節(jié)點的優(yōu)先級越高，最終選擇優(yōu)先級最高的備選父節(jié)點作為最優(yōu)父節(jié)點。最優(yōu)父節(jié)點選擇策略的具體操作步驟為：

步驟1 當(dāng)sink節(jié)點發(fā)起DODAG的構(gòu)建時，其一跳范圍內(nèi)的鄰居節(jié)點N選擇根節(jié)點作為最優(yōu)父節(jié)點，并計算出度量值，且將度量值的大小添加到周期性廣播的DIO消息中。

步驟2 節(jié)點M接收到其鄰居節(jié)點周期性廣播的DIO消息后，根據(jù)備選父節(jié)點選擇策略選出備選父節(jié)點。

步驟3 節(jié)點M根據(jù)DIO消息中攜帶的相關(guān)信息計算與所有備選父節(jié)點之間的度量值，然后根據(jù)式(8)計算每條路徑上的總度量值

(8)

式中：Metric(M→N→sink)表示節(jié)點M通過其備選父節(jié)點N到達sink節(jié)點的總度量值，φ表示節(jié)點M的網(wǎng)絡(luò)深度值。

步驟4 節(jié)點M根據(jù)計算所得的每條路徑上的總度量值的大小選擇最優(yōu)父節(jié)點，即選擇總度量值最大的備選父節(jié)點作為最優(yōu)父節(jié)點。如果計算得到一個節(jié)點擁有兩個總度量值相同的備選父節(jié)點，則選擇度量值方差較小的備選父節(jié)點作為最優(yōu)父節(jié)點。

步驟5 節(jié)點M將當(dāng)前總度量值添加到周期性廣播的DIO消息中，其下游節(jié)點接收到該DIO消息后重復(fù)節(jié)點M的處理過程，直至網(wǎng)絡(luò)構(gòu)建完成。

如圖3所示，節(jié)點I有兩個備選父節(jié)點D和E，即節(jié)點I到sink節(jié)點有兩條路徑，分別為I→D→A→sink和I→E→B→sink。而這兩條路徑的總的度量值分別為17和15，根據(jù)最優(yōu)父節(jié)點選擇策略，則節(jié)點I選擇備選節(jié)點D作為最優(yōu)父節(jié)點。

圖3 基于LB-RPL路由協(xié)議的網(wǎng)絡(luò)拓撲構(gòu)建

3 實驗及結(jié)果分析

使用OPNET14.5仿真工具進行平臺的搭建和仿真，將本文提出的LB-RPL路由協(xié)議與RPL-OF0[8]和ETX-RPL[9]路由協(xié)議從以下4個方面進行對比和分析，分別為數(shù)據(jù)包投遞率、網(wǎng)絡(luò)生存時間、平均端到端傳輸時延和根節(jié)點平均吞吐量。

3.1 仿真環(huán)境及參數(shù)設(shè)置

在300 m×300 m的模擬仿真場景中創(chuàng)建網(wǎng)絡(luò)規(guī)模大小分別為10、30、50、70、90和110的LLN網(wǎng)絡(luò)，且每個場景中的所有節(jié)點均隨機放置。除此之外，網(wǎng)絡(luò)中每個節(jié)點均工作在存儲模式下，且初始能量相同。在網(wǎng)絡(luò)創(chuàng)建初期，所有節(jié)點均采用靜態(tài)模型，即位置一旦被確定將不再進行改變。仿真中用到的其它參數(shù)見表1。

表1 主要仿真參數(shù)

3.2 統(tǒng)計量定義

(1)數(shù)據(jù)包投遞率

數(shù)據(jù)包投遞率(packet delivery ratio，PDR)被定義為從源節(jié)點成功傳輸?shù)礁?jié)點的數(shù)據(jù)包數(shù)量與源節(jié)點發(fā)送數(shù)據(jù)包的比值，計算公式為

(9)

式中：Pi表示成功到達根節(jié)點的數(shù)據(jù)包數(shù)量，Dj表示源節(jié)點發(fā)送的數(shù)據(jù)包數(shù)量。

(2)網(wǎng)絡(luò)生存時間

網(wǎng)絡(luò)生存時間是指在網(wǎng)絡(luò)拓撲初始化之后網(wǎng)絡(luò)中出現(xiàn)第一個能量耗盡的節(jié)點所耗費的時間，計算公式為

TL=Td-T0

(10)

式中：Td表示網(wǎng)絡(luò)中出現(xiàn)第一個能量耗盡節(jié)點的時刻，T0表示網(wǎng)絡(luò)開始運行的時刻。

(3)平均端到端時延

平均端到端時延被定義為所有從源節(jié)點成功傳輸?shù)竭_根節(jié)點的所有數(shù)據(jù)包的端到端傳輸時延總和與數(shù)據(jù)包個數(shù)的比值，計算公式為

(11)

式中：Ti表示第i個數(shù)據(jù)包到達根節(jié)點的傳輸時延，Dj表示第j個源節(jié)點成功傳輸?shù)竭_根節(jié)點的數(shù)據(jù)包數(shù)量。

(4)根節(jié)點平均吞吐量

根節(jié)點平均吞吐量被定義為在一定時間內(nèi)根節(jié)點成功接收到的總的數(shù)據(jù)包比特數(shù)，計算公式為

(12)

式中：ps表示成功到達根節(jié)點的數(shù)據(jù)包比特數(shù)，T表示網(wǎng)絡(luò)運行的時間。

3.3 仿真結(jié)果分析

3.3.1 數(shù)據(jù)包投遞率

由圖4可知，3種路由協(xié)議的PDR均隨著網(wǎng)絡(luò)規(guī)模的擴大呈下降趨勢。但是，LB-RPL路由協(xié)議的PDR明顯高于RPL-OF0和ETX-RPL路由協(xié)議，分析其主要原因有以下兩點：①在DODAG構(gòu)建的過程中，LB-RPL路由協(xié)議在計算度量值的過程中綜合考慮了多種路由判據(jù)，譬如鏈路質(zhì)量、節(jié)點緩存占用率和中繼節(jié)點當(dāng)前子節(jié)點數(shù)量，能夠最大化地實現(xiàn)負載均衡，從而有效地降低了節(jié)點因高負載而導(dǎo)致的丟包數(shù)量；②LB-RPL路由協(xié)議在選擇最優(yōu)父節(jié)點的過程中依據(jù)整條路徑的數(shù)據(jù)傳輸代價，能夠有效地降低數(shù)據(jù)包從源節(jié)點到達sink節(jié)點整條路徑上的丟包概率。

圖4 數(shù)據(jù)包投遞率

3.3.2 網(wǎng)絡(luò)生存時間

從圖5中可以發(fā)現(xiàn)，隨著網(wǎng)絡(luò)規(guī)模的擴大，RPL-OF0、ETX-RPL和LB-RPL路由協(xié)議的網(wǎng)絡(luò)生存時間均逐漸降低，但LB-RPL路由協(xié)議的網(wǎng)絡(luò)生存時間明顯高于RPL-OF0和ETX-RPL路由協(xié)議。分析其主要原因有以下3點：①在選擇備選父節(jié)點的過程中，LB-RPL路由協(xié)議將節(jié)點當(dāng)前剩余能量和節(jié)點當(dāng)前緩存占用率進行了有效地融合，其中考慮節(jié)點當(dāng)前剩余能量能夠避免將剩余能量不足的節(jié)點選作為備選父節(jié)點，而考慮節(jié)點的緩存占用率，能夠延長高負載節(jié)點的能耗；②LB-RPL路由協(xié)議在計算度量值的過程中綜合考慮多種路由判據(jù)能夠有效地提高數(shù)據(jù)包的投遞率，從而降低了數(shù)據(jù)包因丟包而重傳的能耗；③LB-RPL路由協(xié)議依據(jù)整條路徑的數(shù)據(jù)傳輸代價進行最優(yōu)父節(jié)點的選擇，能夠有效地降低整條路徑上的節(jié)點能耗。

圖5 網(wǎng)絡(luò)生存時間

3.3.3 平均端到端時延

圖6表明，LB-RPL路由協(xié)議的平均端到端時延在隨著網(wǎng)絡(luò)規(guī)模的擴大的過程中均低于RPL-OF0和ETX-RPL路由協(xié)議。分析其主要原因有以下3點：①在網(wǎng)絡(luò)拓撲的組建過程中，LB-RPL路由協(xié)議將節(jié)點當(dāng)前緩存占用率有效地考慮到其中，能夠有效地降低重負載節(jié)點出現(xiàn)的概率，從而縮短了排隊時延；②LB-RPL路由協(xié)議通過結(jié)合多種路由判據(jù)能夠最大化地實現(xiàn)網(wǎng)絡(luò)負載均衡，提高了數(shù)據(jù)包的投遞率，從而降低了節(jié)點因丟包重傳而耗費的時間；③在選擇最優(yōu)父節(jié)點的過程中，LB-RPL路由協(xié)議依據(jù)整條路徑的數(shù)據(jù)傳輸代價能夠有效地降低數(shù)據(jù)整體端到端傳輸時延。

圖6 平均端到端時延

3.3.4 根節(jié)點平均吞吐量

由圖7可知，根節(jié)點的平均吞吐量隨著網(wǎng)絡(luò)規(guī)模的擴大均逐漸增大，其中LB-RPL路由協(xié)議的根節(jié)點平均吞吐量明顯高于RPL-OF0和ETX-RPL路由協(xié)議。分析其主要原因在于LB-RPL路由協(xié)議在DODAG的構(gòu)建過程中將多種路由判據(jù)有效結(jié)合能夠最大化地均衡網(wǎng)絡(luò)負載，降低了數(shù)據(jù)包的丟包率；其次，在計算路由度量值的過程中，LB-RPL路由協(xié)議將節(jié)點當(dāng)前緩存占用率考慮其中，從而對數(shù)據(jù)包的排隊時延有縮減趨勢，以及降低了數(shù)據(jù)包因緩存而導(dǎo)致丟包重傳的次數(shù)，故其根節(jié)點平均吞吐量相比較于RPL-OF0和ETX-RPL路由協(xié)議有所提高。

圖7 根節(jié)點平均吞吐量

4 結(jié)束語

本文針對LLN中現(xiàn)有單路徑RPL路由協(xié)議在DODAG構(gòu)建過程中，僅考慮一跳范圍之間的數(shù)據(jù)傳輸代價而未考慮整條路徑上的傳輸代價，導(dǎo)致不能有效地均衡節(jié)點能耗以及延長網(wǎng)絡(luò)壽命等問題，提出一種基于負載均衡的單路徑LLN路由協(xié)議(LB-RPL)。該協(xié)議從3個方面進行了改進：首先，在選擇備選父節(jié)點的過程中對無線鏈路質(zhì)量、節(jié)點剩余能量和緩存占用率進行限制；其次，在度量值的計算過程中將多種路由判據(jù)有效地結(jié)合，旨在避免單一路由判據(jù)對網(wǎng)絡(luò)性能產(chǎn)生的影響；最后，依據(jù)整條路徑上的數(shù)據(jù)傳輸代價進行最優(yōu)父節(jié)點的選擇。仿真結(jié)果表明，LB-RPL路由協(xié)議在均衡節(jié)點能耗方面有一定的改善，且能夠有效地延長網(wǎng)絡(luò)生存時間以及相應(yīng)地提高數(shù)據(jù)傳輸?shù)目煽啃?。在未來的工作中，我們將研究LLN中基于負載均衡的多路徑RPL路由協(xié)議。