孫佳美,任秀麗
(遼寧大學(xué)信息學(xué)院,沈陽(yáng)110036)
無(wú)線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)是由大量多功能、低功耗、廉價(jià)的傳感器節(jié)點(diǎn)和一個(gè)Sink節(jié)點(diǎn)或基站組成的網(wǎng)絡(luò)系統(tǒng),節(jié)點(diǎn)間采用自組織無(wú)線通信的方式建立連接并傳遞信息,協(xié)同完成特定功能[1]。傳感器節(jié)點(diǎn)的能量、計(jì)算能力、存儲(chǔ)容量和通信帶寬等資源極為有限,如何設(shè)置有效的能量均衡策略,控制節(jié)點(diǎn)的能量消耗成為無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議研究的重點(diǎn)。
針對(duì)低功耗的無(wú)線網(wǎng)絡(luò),IETF工作組制定了RPL路由協(xié)議[2]。在RPL路由協(xié)議中,根據(jù)路由度量計(jì)算節(jié)點(diǎn)rank值,通過(guò)比較節(jié)點(diǎn)rank值選擇下一跳。節(jié)點(diǎn)根據(jù)網(wǎng)絡(luò)狀況動(dòng)態(tài)調(diào)整數(shù)據(jù)包發(fā)送頻率,減少了節(jié)點(diǎn)能耗。但采用跳數(shù)作為路由度量,與節(jié)點(diǎn)間實(shí)際距離存在偏差。而且跳數(shù)少的路徑其單跳距離可能較長(zhǎng),影響鏈路質(zhì)量。
關(guān)于RPL路由協(xié)議的優(yōu)化研究中,文獻(xiàn)[3](ELT-RPL)提出了一種期望壽命路由度量,用于估算網(wǎng)絡(luò)中瓶頸節(jié)點(diǎn)的生存時(shí)間,以此構(gòu)建網(wǎng)絡(luò)拓?fù)洌徊⒁罁?jù)最大最小原則選擇父節(jié)點(diǎn),延長(zhǎng)了網(wǎng)絡(luò)的生命周期。但該協(xié)議增加了控制包的數(shù)量造成包碰撞率增加,導(dǎo)致收包率下降。文獻(xiàn)[4](OBL-RPL)通過(guò)對(duì)節(jié)點(diǎn)的剩余能量進(jìn)行分級(jí)和調(diào)節(jié)節(jié)點(diǎn)的通信半徑的方法,對(duì)目標(biāo)函數(shù)進(jìn)行改進(jìn)。該協(xié)議均衡了節(jié)點(diǎn)的負(fù)載,但會(huì)增加路徑跳數(shù),并且存在網(wǎng)絡(luò)抖動(dòng)現(xiàn)象。文獻(xiàn)[5](EAM-RPL)將鏈路質(zhì)量與節(jié)點(diǎn)能耗相結(jié)合,提出了能量感知路由度量。該路由協(xié)議延長(zhǎng)了網(wǎng)絡(luò)的生命周期。但在網(wǎng)絡(luò)后期,由于父節(jié)點(diǎn)狀態(tài)信息更新不及時(shí),導(dǎo)致節(jié)點(diǎn)做出錯(cuò)誤的路由選擇,加速瓶頸節(jié)點(diǎn)的死亡。文獻(xiàn)[6](HE-CRPL)提出一種高效的基于簇父集協(xié)作通信的路由協(xié)議,該協(xié)議在選擇簇父節(jié)點(diǎn)時(shí)綜合考慮節(jié)點(diǎn)的通信可靠性與節(jié)點(diǎn)的剩余能量,并引入期望壽命ELT進(jìn)行最優(yōu)簇父集選擇。雖然延長(zhǎng)了網(wǎng)絡(luò)的生命周期,但增加了簇父節(jié)點(diǎn)之間的通信量。文獻(xiàn)[7](HIT-RPL)提出一種基于機(jī)會(huì)路由的RPL路由協(xié)議。節(jié)點(diǎn)采用任播的方式傳輸數(shù)據(jù)包,數(shù)據(jù)包的傳輸不依賴(lài)某一固定鏈路。雖然提高了網(wǎng)絡(luò)的可靠性,但目的節(jié)點(diǎn)會(huì)接收到多個(gè)來(lái)自不同路徑的相同數(shù)據(jù)包,增加了目的節(jié)點(diǎn)和中繼節(jié)點(diǎn)的負(fù)載。文獻(xiàn)[8](EB-RPL)提出一種帶有電量估算的路由協(xié)議,設(shè)計(jì)了一種基于能量消耗速率的父節(jié)點(diǎn)電量估算策略,通過(guò)估算父節(jié)點(diǎn)電量進(jìn)行路由決策。延長(zhǎng)了網(wǎng)絡(luò)的生命周期,但節(jié)點(diǎn)的預(yù)測(cè)誤差會(huì)影響節(jié)點(diǎn)的路由決策。以上這些算法在處理多指標(biāo)優(yōu)化問(wèn)題上,采用加權(quán)法將多個(gè)鏈路質(zhì)量指標(biāo)組合成一個(gè)指標(biāo),各指標(biāo)的權(quán)重系數(shù)都是根據(jù)主觀經(jīng)驗(yàn)值給定。由于網(wǎng)絡(luò)環(huán)境復(fù)雜多變,鏈路質(zhì)量指標(biāo)在網(wǎng)絡(luò)運(yùn)行過(guò)程中不斷發(fā)生變化,采用固定的主觀權(quán)重?zé)o法根據(jù)實(shí)際指標(biāo)的變化作出自適應(yīng)的調(diào)整,路由決策難以滿(mǎn)足網(wǎng)絡(luò)的實(shí)際需求。
通過(guò)分析以上協(xié)議,本文提出了一種無(wú)線傳感網(wǎng)中基于均方差賦權(quán)法的路由協(xié)議MSDRP(Mean-Squared Deviation weight decision Routing Protocol)。構(gòu)造一種新的節(jié)點(diǎn)距離路由度量。提出了一個(gè)節(jié)點(diǎn)鄰域空間劃分模型,并在節(jié)點(diǎn)鄰域內(nèi)確定一個(gè)參考點(diǎn)。根據(jù)余弦定理將節(jié)點(diǎn)距鄰節(jié)點(diǎn)距離,節(jié)點(diǎn)距Sink節(jié)點(diǎn)距離,鄰節(jié)點(diǎn)距Sink節(jié)點(diǎn)距離,節(jié)點(diǎn)的通信半徑等多個(gè)變量的取值及其變化關(guān)系轉(zhuǎn)化到節(jié)點(diǎn)鄰域內(nèi)參考點(diǎn)距鄰節(jié)點(diǎn)距離這一個(gè)變量的測(cè)量上。提高鄰節(jié)點(diǎn)距離這一評(píng)價(jià)指標(biāo)所考慮因素的全面性和合理性。綜合考慮鄰節(jié)點(diǎn)的剩余能量,鄰節(jié)點(diǎn)的距離,鄰節(jié)點(diǎn)的鏈路質(zhì)量和鄰節(jié)點(diǎn)的負(fù)載這四個(gè)評(píng)價(jià)指標(biāo),根據(jù)均方差賦權(quán)法對(duì)節(jié)點(diǎn)評(píng)價(jià)指標(biāo)的權(quán)值進(jìn)行動(dòng)態(tài)調(diào)整。通過(guò)目標(biāo)函數(shù)公式計(jì)算出鄰節(jié)點(diǎn)的目標(biāo)函數(shù)值,選擇目標(biāo)函數(shù)值最大的節(jié)點(diǎn)作為下一跳,建立數(shù)據(jù)傳輸路徑。仿真結(jié)果表明該路由協(xié)議能夠有效均衡節(jié)點(diǎn)能耗,延長(zhǎng)網(wǎng)絡(luò)的生命周期。
網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)隨機(jī)分布在監(jiān)測(cè)區(qū)域內(nèi),且部署后位置固定。另外,節(jié)點(diǎn)之間的距離采用文獻(xiàn)[9]中的RSSI測(cè)距方法計(jì)算。傳感器節(jié)點(diǎn)依靠電池供電,能量有限。節(jié)點(diǎn)ID編號(hào)唯一,初始通信半徑都相同。Sink節(jié)點(diǎn)位置固定,能量充足。所有節(jié)點(diǎn)可以接收來(lái)自Sink節(jié)點(diǎn)廣播的數(shù)據(jù)包。節(jié)點(diǎn)發(fā)送和接收數(shù)據(jù)所消耗的能量采用與文獻(xiàn)[10]中相同的能耗模型進(jìn)行計(jì)算。
圖1 節(jié)點(diǎn)的鄰域劃分
節(jié)點(diǎn)的單跳通信范圍是節(jié)點(diǎn)的鄰域。節(jié)點(diǎn)鄰域模型將節(jié)點(diǎn)鄰域劃分成兩部分,如圖1所示。點(diǎn)A表示Sink節(jié)點(diǎn),點(diǎn)Nx表示傳感器節(jié)點(diǎn)。節(jié)點(diǎn)Nx的鄰域用圓Nx來(lái)表示,圓Nx的半徑為傳感器節(jié)點(diǎn)的初始通信半徑R0。Sink節(jié)點(diǎn)的通信區(qū)域用圓A表示,圓A的半徑為節(jié)點(diǎn) Nx距 Sink節(jié)點(diǎn)的距離 d(Nx,Sink)。將圓Nx與圓A的相交區(qū)域視為節(jié)點(diǎn)Nx的前向鄰域(如圖1中的陰影區(qū)域),圓Nx內(nèi)的剩余區(qū)域?yàn)楣?jié)點(diǎn)Nx的后向鄰域。稱(chēng)節(jié)點(diǎn)Nx前向鄰域內(nèi)的鄰節(jié)點(diǎn)為節(jié)點(diǎn)Nx的前向鄰節(jié)點(diǎn)。
根據(jù)節(jié)點(diǎn)Nx的鄰域劃分模型確定節(jié)點(diǎn)Nx鄰域內(nèi)的參考點(diǎn),如圖2所示。過(guò)點(diǎn)A(Sink節(jié)點(diǎn))和點(diǎn)Nx作一條直線Lx。直線Lx與圓Nx相交于圓A內(nèi)一點(diǎn)Ox,將點(diǎn)Ox作為節(jié)點(diǎn)Nx鄰域內(nèi)的參考點(diǎn)。兩圓的交點(diǎn)B和C分別是節(jié)點(diǎn)Nx鄰域內(nèi)的兩個(gè)臨界點(diǎn)。
圖2 節(jié)點(diǎn)鄰域內(nèi)的參考點(diǎn)
如圖2所示,設(shè)節(jié)點(diǎn)Nk是節(jié)點(diǎn)Nx的前向鄰節(jié)點(diǎn)。則節(jié)點(diǎn)Nk距Sink節(jié)點(diǎn)的距離為d(Nk,Sink),節(jié)點(diǎn)Nk距節(jié)點(diǎn)Nx的距離為d(Nk,Nx)。節(jié)點(diǎn)Nk距節(jié)點(diǎn)Nx鄰域內(nèi)參考點(diǎn)Ox的距離為d(Nk,Ox)。節(jié)點(diǎn)Nx距Sink節(jié)點(diǎn)的距離為d(Nx,Sink),節(jié)點(diǎn)Nx距其鄰域內(nèi)的參考點(diǎn)Ox的距離為d(Nx,Ox)=R0,R0為節(jié)點(diǎn)的初始通信半徑。設(shè)三角形 ΔNkNxA中∠NkNxA的度數(shù)為θxk。根據(jù)余弦定理,角θxk的余弦值cosθxk可以分別用式(1)和式(2)來(lái)表示。
聯(lián)合式(1)和式(2)可以推導(dǎo)出節(jié)點(diǎn)Nk距參考點(diǎn) Ox的距離 d(Nk,Ox),如式(3)。
節(jié)點(diǎn)間的距離是影響節(jié)點(diǎn)能耗的重要因素。文獻(xiàn)[11-13]中分別采用了不同方法計(jì)算節(jié)點(diǎn)的距離代價(jià)。本文所定義的距離度量,如圖2所示。將節(jié)點(diǎn)Nk距參考點(diǎn)Ox的距離d(Nk,Ox)作為在節(jié)點(diǎn)Nx的鄰域內(nèi),節(jié)點(diǎn)Nk的距離路由度量。從式(3)中可以看出,在建立了參考點(diǎn)后的鄰域劃分模型中,節(jié)點(diǎn)距離路由度量這一評(píng)價(jià)指標(biāo)的選擇,不僅考慮到節(jié)點(diǎn)、鄰節(jié)點(diǎn)和Sink節(jié)點(diǎn)所構(gòu)成的三角形三邊的變化關(guān)系;同時(shí)還考慮了下一跳節(jié)點(diǎn)與鄰域內(nèi)特殊位置的距離變化關(guān)系。為了避免在路由選擇的過(guò)程中產(chǎn)生路由環(huán)路,規(guī)定節(jié)點(diǎn)從其鄰域劃分模型中的前向鄰域內(nèi)選擇下一跳節(jié)點(diǎn)。為了減少傳輸跳數(shù),規(guī)定節(jié)點(diǎn)從其鄰域內(nèi)選擇距離Sink節(jié)點(diǎn)最近的鄰節(jié)點(diǎn)作為下一跳。顯然在節(jié)點(diǎn)的前向鄰域內(nèi),參考點(diǎn)所在的位置最靠近Sink節(jié)點(diǎn),因此參考點(diǎn)的位置是選擇下一跳節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸?shù)睦硐胛恢?。將下一跳?jié)點(diǎn)的選擇限定在節(jié)點(diǎn)的前向鄰域內(nèi),在此前提下,圖2中各點(diǎn)間的距離滿(mǎn)足如下條件(4)。
式中:R0表示節(jié)點(diǎn)的初始通信半徑。d(Nk,Nx)表示鄰節(jié)點(diǎn)Nk距節(jié)點(diǎn)Nx的距離。由于鄰節(jié)點(diǎn)在節(jié)點(diǎn)的一跳鄰域內(nèi),所以節(jié)點(diǎn)距鄰節(jié)點(diǎn)的距離d(Nk,Nx)應(yīng)大于 0且小于 R0。d(Nx,Sink)表示節(jié)點(diǎn) Nx距Sink節(jié)點(diǎn)的距離。Area表示整個(gè)網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域的面積。當(dāng)Sink節(jié)點(diǎn)位于傳感器節(jié)點(diǎn)的一跳鄰域內(nèi)時(shí),傳感器節(jié)點(diǎn)采用單跳通信的方式直接向Sink節(jié)點(diǎn)發(fā)送數(shù)據(jù)。對(duì)于那些無(wú)法直接向Sink節(jié)點(diǎn)發(fā)送數(shù)據(jù)的傳感器節(jié)點(diǎn),應(yīng)選擇中繼節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)。因此設(shè)定d(Nx,Sink)的距離大于R0,即只對(duì)需要選擇中繼的節(jié)點(diǎn)進(jìn)行研究。d(Nk,Sink)表示鄰節(jié)點(diǎn)Nk距Sink節(jié)點(diǎn)的距離。由于規(guī)定了在節(jié)點(diǎn)的前向鄰域內(nèi)選擇下一跳節(jié)點(diǎn),所以d(Nk,Sink)應(yīng)小于 d(Nx,Sink)。 d(Nk,Ox)表示節(jié)點(diǎn) Nk距參考點(diǎn) Ox的距離。maxDistx表示節(jié)點(diǎn)Nx的前向鄰域內(nèi)臨界點(diǎn)距參考點(diǎn)Ox的距離。在圖2中,點(diǎn)B和點(diǎn)C分別是節(jié)點(diǎn)Nx前向鄰域內(nèi)的兩個(gè)臨界點(diǎn)。根據(jù)不等式組(4)中的臨界條件,當(dāng) d(Nk,Nx)= R0時(shí),d(Nk,Sink)= d(Nx,Sink),此時(shí) d(Nk,Ox)取得最大值,即d(Nk,Ox)= maxDistx。 之后分別將 d(Nk,Nx)= R0和 d(Nk,Sink)= d(Nx,Sink)代入式(3)中,求得maxDistx的計(jì)算公式,如式(5)。
將均方差賦權(quán)法引入到無(wú)線傳感器網(wǎng)絡(luò)的路由協(xié)議當(dāng)中,將本文所提節(jié)點(diǎn)的距離路由度量作為節(jié)點(diǎn)路由選擇的一個(gè)評(píng)價(jià)指標(biāo)。結(jié)合節(jié)點(diǎn)的剩余能量,節(jié)點(diǎn)的鏈路質(zhì)量,節(jié)點(diǎn)的負(fù)載等評(píng)價(jià)指標(biāo)。分別對(duì)節(jié)點(diǎn)的評(píng)價(jià)指標(biāo)進(jìn)行數(shù)據(jù)標(biāo)準(zhǔn)化處理和無(wú)量綱化處理,將指標(biāo)數(shù)據(jù)的數(shù)值限定到相同的數(shù)據(jù)區(qū)間內(nèi)并消除不同量綱的影響。根據(jù)節(jié)點(diǎn)不同指標(biāo)數(shù)據(jù)的離散程度,利用均方差賦權(quán)法對(duì)指標(biāo)的權(quán)值進(jìn)行動(dòng)態(tài)調(diào)整。根據(jù)目標(biāo)函數(shù)對(duì)節(jié)點(diǎn)的評(píng)價(jià)指標(biāo)進(jìn)行加權(quán)求和,選擇目標(biāo)函數(shù)值最大的節(jié)點(diǎn)作為下一跳,構(gòu)建數(shù)據(jù)傳輸路徑。由于路由決策問(wèn)題涉及到節(jié)點(diǎn)的多個(gè)評(píng)價(jià)指標(biāo)的綜合評(píng)判,因此無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的路由選擇問(wèn)題可以看作是一個(gè)多指標(biāo)決策問(wèn)題。
對(duì)評(píng)價(jià)指標(biāo)進(jìn)行賦權(quán)的方法主要有三類(lèi),分別是主觀賦權(quán)法、客觀賦權(quán)和主客觀賦權(quán)。主觀賦權(quán)法是根據(jù)主觀經(jīng)驗(yàn)對(duì)評(píng)價(jià)指標(biāo)賦予權(quán)值,如文獻(xiàn)[14]中的層次分析法是典型的主觀賦權(quán)法,它根據(jù)專(zhuān)家調(diào)研意見(jiàn)賦予指標(biāo)權(quán)值值。客觀賦權(quán)法是根據(jù)評(píng)價(jià)指標(biāo)的變化特征,建立數(shù)學(xué)函數(shù)模型計(jì)算權(quán)值。本文所引入的均方差賦權(quán)法屬于客觀賦權(quán)法。
均方差即標(biāo)準(zhǔn)差,標(biāo)準(zhǔn)差是方差的算術(shù)平方根。標(biāo)準(zhǔn)差能反映數(shù)據(jù)集的離散程度。均方差賦權(quán)法的主要原理是:各指標(biāo)相對(duì)權(quán)重系數(shù)的大小,取決于在該指標(biāo)下各方案評(píng)價(jià)值的相對(duì)離散程度[15]。若各方案在某指標(biāo)下評(píng)價(jià)值的離散程度越大,就表明在該評(píng)價(jià)指標(biāo)下,各方案的差異性較大,該指標(biāo)應(yīng)賦予較大的權(quán)值系數(shù),反之亦然。若某指標(biāo)下各方案的評(píng)價(jià)值都相同(即評(píng)價(jià)指標(biāo)的離散程度為0),則該指標(biāo)的權(quán)值系數(shù)應(yīng)為0。在無(wú)線傳感器網(wǎng)絡(luò)的路由決策過(guò)程中,可以將下一跳節(jié)點(diǎn)的選擇作為一個(gè)決策方案。將不同節(jié)點(diǎn)的選擇問(wèn)題轉(zhuǎn)化為不同方案的評(píng)價(jià)決策問(wèn)題。
通常將評(píng)價(jià)指標(biāo)分為“效益型”和“成本型”兩大類(lèi)?!靶б嫘汀敝笜?biāo)的評(píng)價(jià)值越大越好,“成本型”指標(biāo)的評(píng)價(jià)值越小越好。不同評(píng)價(jià)指標(biāo)具有不同的量綱和量綱單位,為了消除量綱與量綱單位的影響,應(yīng)將評(píng)價(jià)指標(biāo)進(jìn)行無(wú)量綱化處理。常用的無(wú)量綱化處理方法參見(jiàn)文獻(xiàn)[16]。
對(duì)于評(píng)價(jià)值越大越好的“效益型”指標(biāo),無(wú)量綱化計(jì)算公式如式(6)。
式(6)中Cmax,Cmin分別是指標(biāo)C的最大值和最小值。對(duì)于評(píng)價(jià)值越小越好的“成本型”指標(biāo),無(wú)量綱化計(jì)算公式如式(7)。
本文所提算法將節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)的距離、節(jié)點(diǎn)的鏈路質(zhì)量和節(jié)點(diǎn)的負(fù)載作為節(jié)點(diǎn)進(jìn)行路由選擇的評(píng)價(jià)指標(biāo)。各指標(biāo)的定義和計(jì)算方法如下。
2.2.1 節(jié)點(diǎn)的剩余能量
所有傳感器節(jié)點(diǎn)的初始能量都相同,初始能量值為E0。隨著網(wǎng)絡(luò)的運(yùn)行,傳感器節(jié)點(diǎn)的剩余能量不斷減少。當(dāng)節(jié)點(diǎn)的剩余能量減少到某一限定值時(shí),節(jié)點(diǎn)進(jìn)入失效狀態(tài),不再采集數(shù)據(jù)。對(duì)于任意傳感器節(jié)點(diǎn)Nx,其剩余能量用Ex來(lái)表示。
2.2.2 節(jié)點(diǎn)的距離路由度量
如2.4節(jié)中所述,將節(jié)點(diǎn)距鄰域內(nèi)參考點(diǎn)的距離d(Nk,Ox)作為節(jié)點(diǎn)的距離路由度量。其度量值可以根據(jù)式(3)計(jì)算求得。對(duì)于任意節(jié)點(diǎn)Nx及其鄰域內(nèi)的節(jié)點(diǎn)Nk,鄰節(jié)點(diǎn)Nk在節(jié)點(diǎn)Nx的鄰域內(nèi)的距離度量用 Dkx來(lái)表示,即 Dkx=d(Nk,Ox)。
2.2.3 節(jié)點(diǎn)的鏈路質(zhì)量
數(shù)據(jù)包傳輸時(shí)的碰撞和擁塞會(huì)導(dǎo)致數(shù)據(jù)包丟失或被延遲轉(zhuǎn)發(fā),因此數(shù)據(jù)包在被接收時(shí)存在時(shí)延。因此將節(jié)點(diǎn)的數(shù)據(jù)包傳輸時(shí)延作為節(jié)點(diǎn)鏈路質(zhì)量的評(píng)價(jià)指標(biāo)。通過(guò)鄰節(jié)點(diǎn)數(shù)據(jù)包確認(rèn)信息中的時(shí)間戳來(lái)計(jì)算數(shù)據(jù)包的傳輸時(shí)延。對(duì)于任意節(jié)點(diǎn)Nx及其鄰域內(nèi)的節(jié)點(diǎn)Nk,用Tkx表示鄰節(jié)點(diǎn)Nk轉(zhuǎn)發(fā)節(jié)點(diǎn)Nx的數(shù)據(jù)包的傳輸時(shí)延。
2.2.4 節(jié)點(diǎn)的負(fù)載
同一節(jié)點(diǎn)會(huì)接收到來(lái)自不同節(jié)點(diǎn)所轉(zhuǎn)發(fā)的數(shù)據(jù)。將節(jié)點(diǎn)在一個(gè)數(shù)據(jù)傳輸周期內(nèi)所接收到的數(shù)據(jù)包個(gè)數(shù)作為節(jié)點(diǎn)的負(fù)載。所謂數(shù)據(jù)傳輸周期是指Sink節(jié)點(diǎn)接收到網(wǎng)絡(luò)中所有節(jié)點(diǎn)發(fā)送的數(shù)據(jù)所需的時(shí)間。對(duì)于任意傳感器節(jié)點(diǎn)Nx,其負(fù)載用Lx來(lái)表示。
用集合NbZx={N1,…,Nm}表示節(jié)點(diǎn) Nx前向鄰域內(nèi)的m個(gè)前向鄰節(jié)點(diǎn)。從集合NbZx中選擇一個(gè)節(jié)點(diǎn) Nk,則 k∈[1,m]。 在節(jié)點(diǎn) Nx的前向鄰域內(nèi),節(jié)點(diǎn) Nk的評(píng)價(jià)指標(biāo)集用 Cxk= {Ek,Dxk,Txk,Lk}來(lái)表示。其中Ek表示節(jié)點(diǎn)Nk的剩余能量,Dxk表示節(jié)點(diǎn)Nk的距離路由度量,Txk表示節(jié)點(diǎn)Nk的鏈路質(zhì)量,Lk表示節(jié)點(diǎn)Nk的負(fù)載。
節(jié)點(diǎn)Nx的m個(gè)前向鄰節(jié)點(diǎn)構(gòu)成一個(gè)m行的評(píng)價(jià)矩陣Mx,矩陣Mx中的每一行為一個(gè)節(jié)點(diǎn)的評(píng)價(jià)指標(biāo)集,如式(8)。
分別按照2.1節(jié)中所述的“效益型”和“成本型”兩種指標(biāo)類(lèi)型,對(duì)節(jié)點(diǎn)的評(píng)價(jià)指標(biāo)進(jìn)行分類(lèi)。通常節(jié)點(diǎn)的剩余能量越多越好,所以節(jié)點(diǎn)的剩余能量是“效益型”指標(biāo)。根據(jù)式(6),對(duì)矩陣Mx中表示節(jié)點(diǎn)剩余能量這一列的數(shù)據(jù)進(jìn)行無(wú)量綱化和標(biāo)準(zhǔn)化處理,如式(9)。
式(9)中,maxEx和minEx分別表示節(jié)點(diǎn)Nx的m個(gè)前向鄰節(jié)點(diǎn)剩余能量的最大值和最小值,exk表示節(jié)點(diǎn)Nk的剩余能量的標(biāo)準(zhǔn)化數(shù)據(jù)值。如2.4節(jié)中所述,對(duì)于節(jié)點(diǎn)的距離路由度量值,應(yīng)是越小越好。因此節(jié)點(diǎn)的距離度量屬于“成本型”指標(biāo)。同樣,對(duì)于節(jié)點(diǎn)的傳輸延遲和負(fù)載,也是越小越好。所以節(jié)點(diǎn)的鏈路質(zhì)量和負(fù)載都屬于“成本型”指標(biāo)。根據(jù)式(7),分別對(duì)矩陣Mx中節(jié)點(diǎn)的距離度量,節(jié)點(diǎn)的鏈路質(zhì)量和節(jié)點(diǎn)的負(fù)載的各列數(shù)據(jù)進(jìn)行無(wú)量綱化和標(biāo)準(zhǔn)化處理,如式(10)至(12)。
式(10)中,maxDx和minDx分別表示節(jié)點(diǎn)Nx的m個(gè)前向鄰節(jié)點(diǎn)距離度量的最大值和最小值,dxk表示節(jié)點(diǎn)Nk的距離度量的標(biāo)準(zhǔn)化數(shù)據(jù)值。
式(11)中,maxTx和minTx分別表示節(jié)點(diǎn)Nx的m個(gè)前向鄰節(jié)點(diǎn)數(shù)據(jù)傳輸延遲的最大值和最小值,txk表示節(jié)點(diǎn)Nk的傳輸延遲的標(biāo)準(zhǔn)化數(shù)據(jù)值。
式(12)中,maxLx和minLx分別表示節(jié)點(diǎn)Nx的m個(gè)前向鄰節(jié)點(diǎn)數(shù)據(jù)傳輸延遲的最大值和最小值,lxk表示節(jié)點(diǎn)Nk的剩余能量的標(biāo)準(zhǔn)化數(shù)據(jù)值。對(duì)矩陣Mx中的數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理后得到標(biāo)準(zhǔn)矩陣STDx,如
式(13)。
式(13)中,由于經(jīng)過(guò)了數(shù)據(jù)標(biāo)準(zhǔn)化處理,標(biāo)準(zhǔn)矩陣STDx內(nèi)每個(gè)元素的取值范圍都在0~1區(qū)間。標(biāo)準(zhǔn)矩陣STDx中的各列分別對(duì)應(yīng)節(jié)點(diǎn)的各個(gè)評(píng)價(jià)指標(biāo)。根據(jù)2.1節(jié)中所述的均方差賦權(quán)法,分別計(jì)算矩陣STDx中每列指標(biāo)的平均值和標(biāo)準(zhǔn)差,如式(14),其中m是節(jié)點(diǎn)Nx的前向鄰節(jié)點(diǎn)個(gè)數(shù)。
將矩陣STDx中的標(biāo)準(zhǔn)差數(shù)據(jù)表示為標(biāo)準(zhǔn)差向量 Sx={sxe,sxd,sxt,sxl}。 對(duì)標(biāo)準(zhǔn)差向量 Sx進(jìn)行歸一化處理,如式(15)。將標(biāo)準(zhǔn)差向量Sx的歸一化值作為節(jié)點(diǎn)Nx鄰域內(nèi),m個(gè)前向鄰節(jié)點(diǎn)各評(píng)價(jià)指標(biāo)的權(quán)值。節(jié)點(diǎn)Nx鄰域內(nèi)的權(quán)值向量用Wx={wxe,wxd,wxt,wxl}來(lái)表示。
式(15)中,Sumx是節(jié)點(diǎn)Nx鄰域內(nèi)節(jié)點(diǎn)評(píng)價(jià)指標(biāo)的標(biāo)準(zhǔn)差之和。對(duì)于節(jié)點(diǎn)Nx,wxe是節(jié)點(diǎn)剩余能量的權(quán)值,wxd是節(jié)點(diǎn)距離度量的權(quán)值,wxt是節(jié)點(diǎn)鏈路質(zhì)量的權(quán)值,wxl是節(jié)點(diǎn)負(fù)載的權(quán)值。
無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的路由選擇問(wèn)題,是一個(gè)多指標(biāo)綜合評(píng)判問(wèn)題。本文采用加權(quán)求和的方式對(duì)節(jié)點(diǎn)的各項(xiàng)指標(biāo)進(jìn)行綜合評(píng)判,即目標(biāo)函數(shù)是對(duì)節(jié)點(diǎn)指標(biāo)進(jìn)行加權(quán)求和的計(jì)算函數(shù)。對(duì)于節(jié)點(diǎn)Nx,其目標(biāo)函數(shù)如式(16)。
式中:fx(Nk)是節(jié)點(diǎn)Nk在節(jié)點(diǎn)Nx鄰域內(nèi)的目標(biāo)函數(shù)值。 wxe,wxd,wxt和 wxl是節(jié)點(diǎn) Nx鄰域內(nèi)的各指標(biāo)權(quán)值,如式(16)。 exk,dxk,txk和 lxk是節(jié)點(diǎn) Nk的在節(jié)點(diǎn)Nx鄰域內(nèi)的各指標(biāo)標(biāo)準(zhǔn)化數(shù)據(jù),如式(13)中矩陣STDx的第k行。在經(jīng)過(guò)3.3節(jié)中的數(shù)據(jù)標(biāo)準(zhǔn)化處理后,所有指標(biāo)的數(shù)據(jù)值都是越大越好。因此節(jié)點(diǎn)應(yīng)選擇目標(biāo)函數(shù)值最大的鄰節(jié)點(diǎn)作為下一跳,如式(17)。
式(17)中,NextHop(Nx)表示節(jié)點(diǎn)Nx的下一跳節(jié)點(diǎn),Ni表示節(jié)點(diǎn)Ni。其中Ni是節(jié)點(diǎn)Nx的m個(gè)前向鄰節(jié)點(diǎn)中,目標(biāo)函數(shù)值最大的節(jié)點(diǎn)。
位于Sink節(jié)點(diǎn)一跳鄰域內(nèi)的所有節(jié)點(diǎn)采用單跳通信的方式直接向Sink節(jié)點(diǎn)發(fā)送數(shù)據(jù)。Sink節(jié)點(diǎn)一跳鄰域外的所有節(jié)點(diǎn)采用多跳的方式將數(shù)據(jù)發(fā)送至Sink節(jié)點(diǎn)。
節(jié)點(diǎn)向下一跳發(fā)送數(shù)據(jù),下一跳節(jié)點(diǎn)返回確認(rèn)信息。下一跳節(jié)點(diǎn)繼續(xù)傳遞數(shù)據(jù),直至Sink節(jié)點(diǎn)接收到源節(jié)點(diǎn)所發(fā)送的數(shù)據(jù)。當(dāng)Sink節(jié)點(diǎn)接收到網(wǎng)絡(luò)中所有可用節(jié)點(diǎn)的數(shù)據(jù)包后,就完成了一輪傳輸。隨后Sink節(jié)點(diǎn)廣播消息宣布開(kāi)啟新一輪的數(shù)據(jù)傳輸。
每輪數(shù)據(jù)傳輸周期開(kāi)始之前,節(jié)點(diǎn)間都會(huì)互相傳遞剩余能量等鏈路信息。當(dāng)節(jié)點(diǎn)發(fā)現(xiàn)有鄰節(jié)點(diǎn)電量不足時(shí),就將電量不足的節(jié)點(diǎn)標(biāo)記為失效節(jié)點(diǎn)。在進(jìn)行下一次的路由選擇時(shí),排除掉鄰居信息表中的失效節(jié)點(diǎn)。從可用鄰節(jié)點(diǎn)中選擇下一跳繼續(xù)傳輸數(shù)據(jù)。
本文提出的MSDRP路由協(xié)議的具體實(shí)現(xiàn)步驟如下,其流程如圖3所示。
步驟1 網(wǎng)絡(luò)初始化。Sink節(jié)點(diǎn)廣播開(kāi)始消息,所有傳感器節(jié)點(diǎn)進(jìn)入初始化階段。節(jié)點(diǎn)通過(guò)鄰居發(fā)現(xiàn)協(xié)議探測(cè)周?chē)徆?jié)點(diǎn),創(chuàng)建鄰居節(jié)點(diǎn)信息表。通過(guò)RSSI測(cè)距方法計(jì)算節(jié)點(diǎn)間距離并存入鄰居表。
步驟2 數(shù)據(jù)更新。節(jié)點(diǎn)通過(guò)無(wú)線通信的方式與周?chē)徆?jié)點(diǎn)互相通信,獲取鄰節(jié)點(diǎn)剩余能量信息,節(jié)點(diǎn)的鏈路質(zhì)量和節(jié)點(diǎn)的負(fù)載等指標(biāo)數(shù)據(jù)并更新鄰居表。標(biāo)記剩余能量不足的節(jié)點(diǎn)。
步驟3 數(shù)據(jù)標(biāo)準(zhǔn)化。節(jié)點(diǎn)根據(jù)3.3節(jié)中所描述的方法,對(duì)節(jié)點(diǎn)的指標(biāo)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理。
步驟4 計(jì)算指標(biāo)權(quán)值。節(jié)點(diǎn)利用均方差賦權(quán)法計(jì)算標(biāo)準(zhǔn)化數(shù)據(jù)的標(biāo)準(zhǔn)差,計(jì)算各指標(biāo)對(duì)應(yīng)的權(quán)重值。
步驟5 計(jì)算目標(biāo)函數(shù)。節(jié)點(diǎn)根據(jù)根據(jù)目標(biāo)函數(shù)公式計(jì)算鄰節(jié)點(diǎn)目標(biāo)函數(shù)值,選擇目標(biāo)函數(shù)值最大的節(jié)點(diǎn)作為下一跳。
步驟6 數(shù)據(jù)傳輸。節(jié)點(diǎn)選擇好下一跳后,與下一跳節(jié)點(diǎn)建立通信連接。開(kāi)始新一輪的數(shù)據(jù)傳輸。完成一輪數(shù)據(jù)傳輸后,節(jié)點(diǎn)檢查自身剩余能量。如果節(jié)點(diǎn)剩余能量不足則進(jìn)入失效狀態(tài),執(zhí)行步驟7退出網(wǎng)絡(luò)。否則執(zhí)行步驟2更新鄰節(jié)點(diǎn)數(shù)據(jù)。
步驟7 退出網(wǎng)絡(luò)。剩余能量不足的節(jié)點(diǎn)進(jìn)入失效狀態(tài),不再采集和轉(zhuǎn)發(fā)任何數(shù)據(jù)。
圖3 路由協(xié)議流程圖
使用OMNeT++5.2仿真環(huán)境,對(duì)MSDRP協(xié)議的性能進(jìn)行驗(yàn)證。將MSDRP與RPL、EB-RPL在網(wǎng)絡(luò)能效性、時(shí)效性等方面進(jìn)行了比較;并使用CC2530開(kāi)發(fā)板在實(shí)際環(huán)境下進(jìn)行了測(cè)試。
使用OMNet++對(duì)網(wǎng)絡(luò)協(xié)議進(jìn)行仿真。將100個(gè)節(jié)點(diǎn)隨機(jī)分布在100 m×100 m的區(qū)域內(nèi),Sink節(jié)點(diǎn)位于監(jiān)測(cè)區(qū)域的中心位置。節(jié)點(diǎn)初始能量為0.5 J,數(shù)據(jù)包大小為 500 byte,控制包大小為 50 byte。節(jié)點(diǎn)初始通信半徑R0=20 m。
3.2.1 網(wǎng)絡(luò)能效性
隨著網(wǎng)絡(luò)的運(yùn)行和節(jié)點(diǎn)能量的消耗,網(wǎng)絡(luò)中不斷有節(jié)點(diǎn)因能量耗盡而失效。網(wǎng)絡(luò)中剩余節(jié)點(diǎn)的個(gè)數(shù)反映網(wǎng)絡(luò)中節(jié)點(diǎn)能量的消耗情況,是評(píng)價(jià)網(wǎng)絡(luò)能效性的標(biāo)準(zhǔn)之一。通常將網(wǎng)絡(luò)中首個(gè)節(jié)點(diǎn)失效的時(shí)間作為網(wǎng)絡(luò)的生命周期。如圖4是網(wǎng)絡(luò)中的剩余節(jié)點(diǎn)個(gè)數(shù)隨仿真時(shí)間的變化情況。隨著仿真時(shí)間的增加,網(wǎng)絡(luò)中的失效節(jié)點(diǎn)逐漸增加,可用節(jié)點(diǎn)逐漸減少。從圖4可以看出,MSDRP協(xié)議與RPL和EBRPL相比,網(wǎng)絡(luò)生命周期分別提高了55.56%和20.69%。這說(shuō)明MSDRP協(xié)議所采用的權(quán)值計(jì)算方法能夠有效均衡節(jié)點(diǎn)能耗,延長(zhǎng)網(wǎng)絡(luò)的生命周期。
圖4 網(wǎng)絡(luò)生命周期對(duì)比圖
3.2.2 網(wǎng)絡(luò)負(fù)載均衡性
通常除了檢測(cè)區(qū)域邊緣部分的少數(shù)節(jié)點(diǎn),網(wǎng)絡(luò)中的大部分節(jié)點(diǎn)會(huì)接收多個(gè)節(jié)點(diǎn)的數(shù)據(jù)并進(jìn)行轉(zhuǎn)發(fā)。由于節(jié)點(diǎn)周期的鄰節(jié)點(diǎn)個(gè)數(shù)和節(jié)點(diǎn)所處的地理位置不同,節(jié)點(diǎn)需要接收和轉(zhuǎn)發(fā)的數(shù)據(jù)包個(gè)數(shù)也存在差異。節(jié)點(diǎn)能量主要消耗在發(fā)送和接收數(shù)據(jù)包上,節(jié)點(diǎn)的剩余能量標(biāo)準(zhǔn)差可以反映節(jié)點(diǎn)之間剩余能量的離散程度,依此對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)的負(fù)載均衡性進(jìn)行評(píng)估。圖5是網(wǎng)絡(luò)中節(jié)點(diǎn)的剩余能量標(biāo)準(zhǔn)差隨仿真時(shí)間的變化情況。從圖5可以看出,隨著仿真時(shí)間的增加,節(jié)點(diǎn)的剩余能量標(biāo)準(zhǔn)差始終處于上下波動(dòng)的狀態(tài),且波動(dòng)幅度基本保持在一定范圍內(nèi)。與RPL和EB-RPL相比,MSDRP的節(jié)點(diǎn)剩余能量的標(biāo)準(zhǔn)差分別降低了51.11%和33.33%。且MSDRP協(xié)議中節(jié)點(diǎn)剩余能量標(biāo)準(zhǔn)差的波動(dòng)幅度較小,這說(shuō)明MSDRP協(xié)議能夠有效均衡網(wǎng)絡(luò)中節(jié)點(diǎn)的負(fù)載。
圖5 節(jié)點(diǎn)負(fù)載均衡性對(duì)比圖
3.2.3 網(wǎng)絡(luò)可靠性
數(shù)據(jù)包傳輸時(shí)的碰撞和擁塞會(huì)導(dǎo)致數(shù)據(jù)包丟失,無(wú)線鏈路的不穩(wěn)定也會(huì)導(dǎo)致數(shù)據(jù)包丟失[17]。因此節(jié)點(diǎn)的丟包率是反映網(wǎng)絡(luò)可靠性的一個(gè)評(píng)價(jià)指標(biāo)。實(shí)驗(yàn)中通過(guò)改變節(jié)點(diǎn)的發(fā)包速率,統(tǒng)計(jì)節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包個(gè)數(shù)和Sink節(jié)點(diǎn)接收的數(shù)據(jù)包個(gè)數(shù),計(jì)算出節(jié)點(diǎn)的丟包率。圖6是不同節(jié)點(diǎn)發(fā)包速率下,節(jié)點(diǎn)丟包率的變化情況。
從圖6中可以看出,隨著節(jié)點(diǎn)發(fā)包速率的增加,節(jié)點(diǎn)丟包率逐漸增加。當(dāng)節(jié)點(diǎn)發(fā)包速率較快時(shí),節(jié)點(diǎn)丟包率有明顯上升的趨勢(shì)。與RPL和EB-RPL協(xié)議相比,MSDRP協(xié)議的丟包率分別降低了75.3%和55.6%。且隨著發(fā)包速率的增加,MSDRP協(xié)議中節(jié)點(diǎn)的丟包率上升緩慢。這說(shuō)明MSDRP協(xié)議能夠有效均衡節(jié)點(diǎn)負(fù)載,減少數(shù)據(jù)包碰撞,提高網(wǎng)絡(luò)可靠性。
3.2.4 網(wǎng)絡(luò)時(shí)效性
源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)和目的節(jié)點(diǎn)接收的數(shù)據(jù)存在時(shí)間延遲,時(shí)間延遲主要來(lái)自于數(shù)據(jù)包的傳輸延遲[18]。因此數(shù)據(jù)包的傳輸延遲是檢驗(yàn)網(wǎng)絡(luò)時(shí)效性的重要指標(biāo)。圖7是不同節(jié)點(diǎn)發(fā)包速率下,數(shù)據(jù)包傳輸延遲的變化情況。從圖7中可以看出,隨著節(jié)點(diǎn)發(fā)包速率的增加,RPL和EB-RPL協(xié)議的數(shù)據(jù)包傳輸延遲呈快速上升的趨勢(shì),而MSDRP協(xié)議的數(shù)據(jù)包傳輸延遲上升趨勢(shì)較為緩慢。與RPL和EB-RPL相比,MSDRP的數(shù)據(jù)包傳輸延遲分別降低了63.5%和42.6%。這說(shuō)明MSDRP協(xié)議結(jié)合節(jié)點(diǎn)鏈路質(zhì)量對(duì)指標(biāo)權(quán)值進(jìn)行調(diào)整,能夠有效提高網(wǎng)絡(luò)的時(shí)效性。
圖7 節(jié)點(diǎn)數(shù)據(jù)包傳輸延遲對(duì)比圖
3.3.1 測(cè)試環(huán)境和節(jié)點(diǎn)參數(shù)
在面積為100 m×100 m的實(shí)驗(yàn)場(chǎng)地上部署測(cè)試系統(tǒng)。系統(tǒng)所用節(jié)點(diǎn)工作頻段為2.4 GHz,節(jié)點(diǎn)芯片型號(hào)為CC2530,執(zhí)行 ZigBee/IEEE802.15.4標(biāo)準(zhǔn),RAM大小為8 kbyte,支持CSMA/CA協(xié)議。實(shí)驗(yàn)中將10個(gè)節(jié)點(diǎn)隨機(jī)部署在監(jiān)測(cè)區(qū)域內(nèi),其中一個(gè)節(jié)點(diǎn)作為Sink節(jié)點(diǎn)與PC機(jī)相連。普通節(jié)點(diǎn)采集數(shù)據(jù)并逐跳發(fā)送至Sink節(jié)點(diǎn),Sink節(jié)點(diǎn)將數(shù)據(jù)發(fā)送到PC機(jī)上。
3.3.2 實(shí)驗(yàn)結(jié)果及結(jié)論
實(shí)際環(huán)境的測(cè)試內(nèi)容與仿真中所進(jìn)行的實(shí)驗(yàn)相對(duì)應(yīng),分別對(duì)三個(gè)路由協(xié)議RPL、EB-RPL和MSDRP的網(wǎng)絡(luò)能效性、負(fù)載均衡性、可靠性和時(shí)效性進(jìn)行了對(duì)比實(shí)驗(yàn)。實(shí)際環(huán)境測(cè)試效果與仿真結(jié)果基本一致。進(jìn)一步驗(yàn)證了MSDRP能夠均衡節(jié)點(diǎn)能耗,延長(zhǎng)網(wǎng)絡(luò)生命周期。
針對(duì)無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)能耗不均衡的問(wèn)題,本文提出一種基于均方差賦權(quán)法的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議MSDRP。該協(xié)議將客觀賦權(quán)法中的均方差賦權(quán)法,引入到無(wú)線傳感器網(wǎng)絡(luò)的路由協(xié)議當(dāng)中。根據(jù)提出的節(jié)點(diǎn)鄰域劃分模型,限定節(jié)點(diǎn)的選擇區(qū)域,縮小節(jié)點(diǎn)的選擇范圍,減少節(jié)點(diǎn)的計(jì)算量。根據(jù)均方差賦權(quán)法和鄰節(jié)點(diǎn)指標(biāo)的變化情況,
對(duì)指標(biāo)權(quán)值進(jìn)行動(dòng)態(tài)調(diào)整。通過(guò)目標(biāo)函數(shù)對(duì)節(jié)點(diǎn)的各項(xiàng)指標(biāo)的標(biāo)準(zhǔn)化數(shù)據(jù)加權(quán)求和。最后選擇目標(biāo)函數(shù)值最大的節(jié)點(diǎn)作為下一跳。該目標(biāo)函數(shù)綜合考慮了節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)的距離度量、節(jié)點(diǎn)的鏈路質(zhì)量和節(jié)點(diǎn)的負(fù)載。實(shí)驗(yàn)結(jié)果表明,MSDRP協(xié)議能有效延長(zhǎng)網(wǎng)絡(luò)生命周期,均衡節(jié)點(diǎn)能耗。