基于期望壽命的能量均衡RPL研究

黃 欣 趙志剛

1(廣西農(nóng)業(yè)職業(yè)技術(shù)學(xué)院信息與機電工程系 廣西 南寧 530007)2(廣西大學(xué)計算機與電子信息學(xué)院 廣西 南寧 530004)

0 引 言

近年來，隨著物聯(lián)網(wǎng)技術(shù)[1]的飛速發(fā)展，其覆蓋的領(lǐng)域包括智能家居[2]、醫(yī)療保健[3]、環(huán)境監(jiān)測[4]和智能電網(wǎng)[5]等。為了滿足物聯(lián)網(wǎng)的廣泛應(yīng)用需求，低功耗有損網(wǎng)絡(luò)LLN(Low power and lossy networks)便被提上了日程。但是，由于組成LLN的無線傳感器節(jié)點在處理能力、存儲空間和能量均受到一定限制，且節(jié)點間的無線鏈路的穩(wěn)定性較差，因而LLN通常具有丟包率較高和網(wǎng)絡(luò)拓撲穩(wěn)定性較差的特點。此外，LLN可應(yīng)用于一些特殊的應(yīng)用場景中，譬如森林防火和荒漠環(huán)境監(jiān)測等，由于放置在上述場景中的無線傳感器節(jié)點數(shù)量眾多，頻繁地更換無線傳感器節(jié)點的電池變得尤為困難。因此，如何最大化地延長網(wǎng)絡(luò)中無線傳感器節(jié)點的使用壽命，尤其是如何均衡網(wǎng)絡(luò)中能量瓶頸節(jié)點的能耗速率具有極高的研究價值。

為了促進LLN的廣泛應(yīng)用，國際互聯(lián)網(wǎng)工程任務(wù)組制定了一種應(yīng)用于LLN的標(biāo)準(zhǔn)路由協(xié)議，即基于Ipv6的低功耗有損網(wǎng)絡(luò)路由協(xié)議RPL[6]。RPL是一種距離矢量路由協(xié)議，通過使用目標(biāo)函數(shù)來構(gòu)建路由度量，從而根據(jù)所構(gòu)建的路由度量來創(chuàng)建面向目的地的有向無環(huán)圖DODAG(Destination oriented directed acyclic graph)。DODAG的構(gòu)建由根節(jié)點發(fā)起，通過周期性廣播DODAG信息對象消息DIO(DODAG information object)至上而下完成DODAG的創(chuàng)建，同時對DODAG的結(jié)構(gòu)進行不定期維護。其中，DIO消息的發(fā)送由“Trickle”定時器[7]控制，即動態(tài)地控制DIO消息的發(fā)送間隔。

目前，學(xué)術(shù)界已對RPL展開了大量研究，譬如在負載均衡[8]、路由修復(fù)[9]和網(wǎng)絡(luò)安全[10]等方面。在對RPL進行能量優(yōu)化的研究中，YOO H等[11]僅將節(jié)點剩余能量消耗速率作為路由度量構(gòu)建DODAG，而未考慮節(jié)點間無線鏈路的可靠性，從而無法全面地提高網(wǎng)絡(luò)壽命。仇英輝等[12]提出了一種基于普通節(jié)點負載均衡的RPL路由協(xié)議，該協(xié)議首先對網(wǎng)絡(luò)中的所有節(jié)點當(dāng)前剩余能量進行等級劃分，然后依據(jù)對節(jié)點當(dāng)前剩余能量劃分的等級結(jié)果對節(jié)點的通信半徑進行一定調(diào)節(jié)，從而實現(xiàn)網(wǎng)絡(luò)負載均衡，但增加了數(shù)據(jù)傳輸跳數(shù)。姚玉坤等[13]為了解決LLN網(wǎng)絡(luò)擁塞的問題，提出了一種集中式網(wǎng)絡(luò)擁塞控制路由協(xié)議。在該協(xié)議中，其路由判據(jù)復(fù)合了多種路由度量，譬如無線鏈路質(zhì)量、緩存占用率、中繼節(jié)點當(dāng)前子節(jié)點個數(shù)以及節(jié)點剩余能量，能夠在有效降低網(wǎng)絡(luò)擁塞發(fā)生概率的同時在一定程度上均衡節(jié)點能耗速率。何王吉等[14]提出一種帶有電量估算策略的能量均衡RPL。EB-RPL構(gòu)造了一種復(fù)合期望傳輸次數(shù)和節(jié)點剩余能量的路由度量，并設(shè)計了一種基于能量消耗速率的父節(jié)點電量估算策略，以便于節(jié)點作出正確的路由選擇，進而實現(xiàn)能量均衡。

上述研究雖然在一定程度上能夠延長網(wǎng)絡(luò)壽命，但是，由于在構(gòu)建DODAG的過程中節(jié)點均未考慮其備選父節(jié)點上一跳節(jié)點的期望壽命，以至于會使得節(jié)點作出錯誤的路由選擇，從而無法有效地減輕能量瓶頸節(jié)點的負載和延長能量瓶頸節(jié)點的使用壽命。

通常，僅由單一路由判據(jù)所構(gòu)建的LLN無法滿足廣泛的應(yīng)用需求，因此，本文在構(gòu)建LLN時，在同時兼顧鏈路的可靠性和數(shù)據(jù)傳輸?shù)臅r效性的基礎(chǔ)上，將節(jié)點的當(dāng)前剩余能量也考慮在其中。基于此，本文設(shè)計了一種基于期望壽命的能量均衡RPL。此外，本文的主要工作將從以下三個方面進行展開：

(1) 構(gòu)造一種復(fù)合路由判據(jù)，包括傳輸跳數(shù)、期望傳輸次數(shù)和節(jié)點期望壽命，同時，節(jié)點在選擇最優(yōu)父節(jié)點時需綜合考慮其備選父節(jié)點及備選父節(jié)點上一跳節(jié)點的期望壽命。

(2) 提出一種“節(jié)點間期望壽命信息通告”策略，即在不增加額外控制開銷的前提下，將節(jié)點的傳輸跳數(shù)與節(jié)點的期望壽命進行編碼，并將編碼后的值添加到DIO消息中的Rank字段中，節(jié)點間通過周期性廣播的DIO消息進行期望壽命的通告，以便節(jié)點作出正確的路由選擇。

(3) 采用contiki 2.7仿真平臺中的Cooja仿真器對ELT-EB-RPL在不同發(fā)包速率下的性能進行了對比分析。

1 問題描述

圖1所示為采用ELT作為作為路由度量所創(chuàng)建的網(wǎng)絡(luò)拓撲圖，該拓撲圖呈樹形結(jié)構(gòu)以便于數(shù)據(jù)的匯聚傳輸。在RPL中，節(jié)點的Rank等級反映出了節(jié)點在網(wǎng)絡(luò)拓撲中相對于根節(jié)點的距離，即節(jié)點相對于根節(jié)點越遠，其Rank等級越高，大致呈正比關(guān)系；通常，節(jié)點的Rank等級等價于節(jié)點到根節(jié)點的數(shù)據(jù)傳輸跳數(shù)。此外，為了規(guī)避路由環(huán)路的產(chǎn)生以便使得網(wǎng)絡(luò)產(chǎn)生震蕩現(xiàn)象，節(jié)點在加入DODAG中的過程中只能選擇Rank等級比自身低的節(jié)點作為父節(jié)點。

在現(xiàn)有研究中，節(jié)點在選擇最優(yōu)父節(jié)點時往往僅考慮其一跳范圍內(nèi)的路由度量，從而會導(dǎo)致當(dāng)下所選擇的最優(yōu)父節(jié)點并非最優(yōu)。以圖1中的節(jié)點R為例，其備選父節(jié)點D和E的期望壽命分別為76和89，在通常情況下，節(jié)點R會選擇備選父節(jié)點E作為最優(yōu)父節(jié)點。然而，節(jié)點E的最優(yōu)父節(jié)點B當(dāng)前的期望壽命為32，且明顯低于節(jié)點D的最優(yōu)父節(jié)點A的期望壽命68。一旦節(jié)點R選擇其備選父節(jié)點E作為最優(yōu)父節(jié)點，將會加快能量瓶頸節(jié)點B的能耗速率，從而加快了能量瓶頸節(jié)點B的死亡速率。

為了能夠有效延長網(wǎng)絡(luò)壽命，關(guān)注網(wǎng)絡(luò)中能量瓶頸節(jié)點的生存時間顯得尤為重要，可以進一步理解為如何使得網(wǎng)絡(luò)中Rank等級相同的節(jié)點的能量能夠均衡消耗，譬如圖1中的節(jié)點A和B。此外，為了滿足實際應(yīng)用場景的需求，在實現(xiàn)能量均衡消耗的前提下，必須同時保證節(jié)點間無線鏈路的可靠性，從而避免不必要的丟包重傳能耗。

為了解決上述問題，本文提出了一種基于期望壽命的能量均衡RPL，即在計算路由判據(jù)的過程中將傳輸跳數(shù)、節(jié)點間數(shù)據(jù)包的期望傳輸次數(shù)以及節(jié)點的期望壽命多種度量有效結(jié)合，且在選擇父節(jié)點時綜合考慮節(jié)點備選父節(jié)點及其備選父節(jié)點上一跳節(jié)點的期望壽命，從而能夠在保證網(wǎng)絡(luò)中的數(shù)據(jù)被可靠傳輸?shù)耐瑫r降低能量瓶頸節(jié)點的能耗速率。

2 基于期望壽命的能量均衡RPL

2.1 復(fù)合路由判據(jù)的構(gòu)建

在RPL中，可以采用單一的路由度量作為路由判據(jù)創(chuàng)建DODAG，譬如傳輸跳數(shù)、無線鏈路質(zhì)量和節(jié)點剩余能量等。然而，上述方式往往會造成所創(chuàng)建的網(wǎng)絡(luò)拓撲結(jié)構(gòu)過于單一，無法滿足不同的應(yīng)用需求。因此，為了有效地實現(xiàn)能量均衡的目的，ELT-EB-RPL在綜合考慮無線鏈路的可靠性以及數(shù)據(jù)傳輸?shù)臅r效性的基礎(chǔ)上同時考慮了節(jié)點的期望壽命。因為節(jié)點的當(dāng)前期望壽命能夠反映出節(jié)點的當(dāng)前剩余能量狀態(tài)以及負載情況。此外，每個節(jié)點在選擇最優(yōu)父節(jié)點時還需綜合考慮其備選父節(jié)點以及其備選父節(jié)點上一跳節(jié)點的期望壽命，旨在避開擁有較低期望壽命父節(jié)點的備選父節(jié)點被其他節(jié)點選作為父節(jié)點，從而達到有效延長網(wǎng)絡(luò)生存時間的目的。復(fù)合路由判據(jù)的創(chuàng)建具體過程如下：

首先，根據(jù)節(jié)點當(dāng)前剩余能量、傳輸功率和數(shù)據(jù)包傳輸速率等相關(guān)參數(shù)計算節(jié)點當(dāng)前期望壽命[13]。期望壽命的公式如下：

(1)

式中：ELT(m)表示節(jié)點m的期望壽命，Eres(m)表示節(jié)點m當(dāng)前剩余能量，Tm表示在一定時間內(nèi)，節(jié)點m需要向其上游節(jié)點傳輸?shù)臄?shù)據(jù)量，Ptx(m)表示節(jié)點m的當(dāng)前傳輸功率，Drate(m)表示節(jié)點m的發(fā)包率，ETX(m,Pm)表示節(jié)點m的父節(jié)點Pm成功接收到其發(fā)送的每一個數(shù)據(jù)包所需大概傳輸次數(shù)，其公式如下：

(2)

式中：ρ(m,Pm)為節(jié)點m和節(jié)點Pm之間的鏈路質(zhì)量。

其次，節(jié)點將其當(dāng)前期望壽命值通過周期性廣播的DIO消息通告給其鄰居節(jié)點和潛在子節(jié)點。

然后，此節(jié)點的鄰居節(jié)點或潛在子節(jié)點接收到上述DIO消息后便可獲知其期望壽命信息，并判斷是否需要調(diào)整通告的期望壽命，其調(diào)整標(biāo)準(zhǔn)如下：

ELT(m)=min(ELT(Pm),ELT(m))

(3)

式中：ELT(Pm)表示節(jié)點m的父節(jié)點Pm的期望壽命。調(diào)整節(jié)點通告期望壽命的目的在于如果節(jié)點m的父節(jié)點Pm處于能量瓶頸狀態(tài)，那么節(jié)點m將不適合被選擇作為其鄰居節(jié)點或潛在子節(jié)點的父節(jié)點，因為流經(jīng)節(jié)點m的數(shù)據(jù)流量最終都要流經(jīng)節(jié)點m的父節(jié)點Pm。因此，當(dāng)網(wǎng)絡(luò)中某個節(jié)點的父節(jié)點處于能量瓶頸狀態(tài)時，通過調(diào)整節(jié)點的期望壽命可以有效地避免該節(jié)點被其鄰居節(jié)點或潛在子節(jié)點選作為父節(jié)點。

最后，依據(jù)對備選父節(jié)點所劃分的優(yōu)先級等級，便可選擇出當(dāng)前節(jié)點的最優(yōu)父節(jié)點，即從備選父節(jié)點集中選擇優(yōu)先級最高的備選父節(jié)點作為當(dāng)前節(jié)點的最優(yōu)父節(jié)點，本文中僅無線鏈路質(zhì)量高于0.6的節(jié)點才能被添加到節(jié)點的備選父節(jié)點集中。而備選父節(jié)點的優(yōu)先級大小由復(fù)合路由判據(jù)值的大小決定，路由判據(jù)值越小，即備選父節(jié)點的優(yōu)先級越高。其中，路由判據(jù)值為：

(4)

式中：R(n,m)表示節(jié)點n與其備選父節(jié)點m之間的路由判據(jù)值，h(m)表示節(jié)點m的傳輸跳數(shù)，ETX(n,m)表示備選父節(jié)點m成功接收到節(jié)點n傳輸?shù)囊粋€數(shù)據(jù)包而該包需要傳輸?shù)钠骄鶄鬏敶螖?shù)，其值為節(jié)點n與節(jié)點m之間無線鏈路質(zhì)量的倒數(shù)，由于ρ(n,m)>0.5，所以1

(5)

2.2 節(jié)點間期望壽命信息通告策略

在RPL標(biāo)準(zhǔn)中，節(jié)點間額外信息的通告通常采取兩種方式：(1) 在DIO消息的幀格式中增添額外的字段攜帶節(jié)點間需要通告的額外信息；(2) 改變目標(biāo)函數(shù)的定義，即對節(jié)點在網(wǎng)絡(luò)中的網(wǎng)絡(luò)深度值(RANK)進行重新定義，使其包含節(jié)點間所需要通告的額外信息[8]。由于RPL具有較好的靈活性和開放性，上述兩種方式都在RPL的范圍內(nèi)。但是，采用第一種方式通常會增加DIO消息幀格式的大小，從而新增了一定的控制開銷。因此，為了不增加額外控制開銷，本文采用第二種方式，即對DIO消息中的RANK值進行重新定義，使其同時包含節(jié)點的傳輸跳數(shù)和期望壽命信息。于是，節(jié)點新的RANK值為：

RANKELT(n)=γ(h(n)+1)+(γ-1)ELT(n)

(6)

式中：γ定義為密碼參數(shù)，該參數(shù)擁有兩種作用，一種是用于節(jié)點在廣播DIO消息前，將傳輸跳數(shù)和節(jié)點期望壽命信息進行編碼；另一種是用于節(jié)點接收到其鄰居節(jié)點廣播的DIO消息后，將其鄰居節(jié)點傳輸跳數(shù)和節(jié)點期望壽命信息進行解碼。原則上，只要γ的取值能夠使得RANKELT(n)的值在16 bits的范圍內(nèi)且節(jié)點能夠正確解碼出其鄰居節(jié)點的傳輸跳數(shù)和期望壽命，γ可以為任意正整數(shù)。本文中，γ的取值為10。

當(dāng)節(jié)點計算出新的RANK值后，將其添加到DIO消息中的Rank字段中，并廣播該DIO消息。其鄰居節(jié)點接收到上述廣播的DIO消息后，利用先前的密碼參數(shù)解碼出節(jié)點的傳輸跳數(shù)和節(jié)點的期望壽命。解碼方式分別如式(7)和式(8)所示：

(7)

(8)

式(7)中，?y」表示為對y向下取整；式(8)中，mod()表示為取模運算操作。

因此，在ELT-EB-RPL中，無需改變原始DIO消息的幀格式以及增加額外的字段，節(jié)點間便可利用周期性廣播的DIO消息獲得彼此間的期望壽命信息，從而能夠便于節(jié)點作出正確的路由選擇。

3 性能評估

為了全面地評估ELT-EB-RPL的性能，本文采用Contiki 2.7操作系統(tǒng)中的Cooja仿真器對其進行模擬仿真，主要針對數(shù)據(jù)包投遞成功率、網(wǎng)絡(luò)生存時間以及節(jié)點死亡率三種性能指標(biāo)進行分析。同時，選擇基于剩余能量為路由判據(jù)的RPL(Residual energy based RPL, RE-RPL)和基于期望傳輸次數(shù)和節(jié)點剩余能量為路由判據(jù)的RPL(Transmission count and Residual energy based RPL, ETX-RE-RPL)進行仿真，并進行性能對比。

3.1 仿真環(huán)境

為了模擬現(xiàn)實場景，在300 m×300 m的仿真區(qū)域內(nèi)隨機分布100個傳感器節(jié)點，其中包括1個根節(jié)點和99個普通節(jié)點，且節(jié)點位置始終處于固定狀態(tài)。此外，根節(jié)點的初始能量不受限制，而普通節(jié)點的初始能量為8 J，且在仿真過程中不再補充。仿真時長為3 600 s，每次仿真重復(fù)10次，最終取其平均值作為最后結(jié)果。本文所用到的其他主要仿真參數(shù)設(shè)置如表1所示。

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

3.2 性能分析

3.2.1數(shù)據(jù)包投遞成功率

圖2所示為RE-RPL、ETX-RE-RPL和ELT-EB-RPL的數(shù)據(jù)包投遞成功率隨著發(fā)包速率逐漸增大的變化趨勢圖。從圖中可以發(fā)現(xiàn)，相較于RE-RPL和ETX-RE-RPL，ELT-EB-RPL的數(shù)據(jù)包投遞成功率最高，分析其原因在于：RE-RPL在網(wǎng)絡(luò)拓撲創(chuàng)建的過程中僅考慮了節(jié)點的剩余能量而未兼顧節(jié)點間的鏈路質(zhì)量，使得剩余能量充足但鏈路質(zhì)量較差的節(jié)點被選作為父節(jié)點的概率增大；ETX-RE-RPL在網(wǎng)絡(luò)拓撲的創(chuàng)建的過程中復(fù)合了期望傳輸次數(shù)和節(jié)點剩余能量，但在復(fù)合前并未對鏈路質(zhì)量較差節(jié)點進行一定篩選，并未從根本上避免剩余能量充足但鏈路質(zhì)量較差節(jié)點被選作為父節(jié)點；而ELT-EB-RPL在對多種路由度量復(fù)合前，對鏈路質(zhì)量較差的節(jié)點進行了一定篩選，從根本上避免了剩余能量充足但鏈路質(zhì)量較差節(jié)點被選作為父節(jié)點。

圖2 數(shù)據(jù)包投遞成功率比較

3.2.2網(wǎng)絡(luò)壽命

圖3所示為RE-RPL、ETX-RE-RPL和ELT-EB-RPL的網(wǎng)絡(luò)壽命隨著發(fā)包速率逐漸增大的變化趨勢圖。網(wǎng)絡(luò)壽命是指在網(wǎng)絡(luò)運行的過程中出現(xiàn)第一個能量耗盡的節(jié)點所耗費的時間。從圖中可以發(fā)現(xiàn)，相比較于RE-RPL和ETX-RE-RPL，ELT-EB-RPL的網(wǎng)絡(luò)壽命最長。分析其原因主要在于：(1) ELT-EB-RPL在對多種路由度量復(fù)合前，對鏈路質(zhì)量較差的節(jié)點進行了一定篩選，能夠有效地降低丟包率，從而相應(yīng)地減少了數(shù)據(jù)包重傳能耗；(2) ELT-EB-RPL在網(wǎng)絡(luò)拓撲構(gòu)建的過程中不是直接考慮節(jié)點的剩余能量，而是對其進一步處理過后的ELT，而ELT不僅能夠反映出節(jié)點的剩余能量情況，而且還能夠大致反映出當(dāng)前節(jié)點的負載情況，從而有效地均衡了節(jié)點的能耗；(3) ELT-EB-RPL在網(wǎng)絡(luò)拓撲創(chuàng)建的過程中不僅考慮了節(jié)點的ELT，而且還綜合考慮了其備選父節(jié)點及備選父節(jié)點上一跳節(jié)點的期望壽命，從而能夠有效地延長能量瓶頸節(jié)點的生存時間。

圖3 網(wǎng)絡(luò)壽命比較

3.2.3節(jié)點死亡率

圖4所示為RE-RPL、ETX-RE-RPL和ELT-EB-RPL的節(jié)點死亡率隨著發(fā)包速率逐漸增大的變化趨勢圖。節(jié)點死亡率是指在網(wǎng)絡(luò)運行的過程中網(wǎng)絡(luò)中出現(xiàn)能量耗盡節(jié)點數(shù)量與網(wǎng)絡(luò)中總的節(jié)點數(shù)量的比值。從圖中可以發(fā)現(xiàn)，相較于RE-RPL和ETX-RE-RPL，ELT-EB-RPL的節(jié)點死亡率最低。分析其原因主要在于：(1) ELT-EB-RPL對鏈路質(zhì)量較差的節(jié)點進行了一定篩選；(2) ELT-EB-RPL在網(wǎng)絡(luò)拓撲構(gòu)建的過程中不是直接考慮節(jié)點的剩余能量，而是對其進一步處理過后的ELT，而ELT不僅能夠反映出節(jié)點的剩余能量情況，而且還能夠大致反映出當(dāng)前節(jié)點的負載情況；(3) ELT-EB-RPL在網(wǎng)絡(luò)拓撲創(chuàng)建的過程中不僅考慮了節(jié)點的ELT，而且還綜合考慮了其備選父節(jié)點及備選父節(jié)點上一跳節(jié)點的期望壽命。上述三種方式均有效地均衡了節(jié)點能耗，能夠有效地延長節(jié)點的生存時間，從而相應(yīng)地降低了節(jié)點死亡的數(shù)量。

圖4 節(jié)點死亡率比較

4 結(jié) 語

由于當(dāng)前基于能量均衡的RPL在網(wǎng)絡(luò)拓撲構(gòu)建的過程中存在節(jié)點未作出正確的路由選擇的問題，導(dǎo)致構(gòu)建的網(wǎng)絡(luò)不能較好地實現(xiàn)能量均衡，提出了一種基于期望壽命的能量均衡RPL(ELT-EB-RPL)。首先，構(gòu)造一種復(fù)合路由判據(jù)，包括傳輸跳數(shù)、期望傳輸次數(shù)和節(jié)點期望壽命，同時，節(jié)點在選擇最優(yōu)父節(jié)點時需綜合考慮其備選父節(jié)點及備選父節(jié)點上一跳節(jié)點的期望壽命；其次，在不增加額外控制開銷的前提下，提出一種節(jié)點間期望壽命信息通告策略，以便節(jié)點作出正確的路由選擇；最后，通過仿真實驗對ELT-EB-RPL的性能進行對比分析。仿真結(jié)果表明，在不同發(fā)包速率下ELT-EB-RPL能夠有效實現(xiàn)能量均衡和延長網(wǎng)絡(luò)壽命。