傳感器網(wǎng)絡(luò)中考慮響應(yīng)時(shí)間的路由機(jī)制-設(shè)計(jì)應(yīng)用

精品文檔-下載后可編輯傳感器網(wǎng)絡(luò)中考慮響應(yīng)時(shí)間的路由機(jī)制-設(shè)計(jì)應(yīng)用摘要:為了把響應(yīng)時(shí)間引入傳感器網(wǎng)絡(luò)中的路由機(jī)制,細(xì)分了網(wǎng)絡(luò)層次,分析了響應(yīng)時(shí)間模型、基于二層架構(gòu)的傳感器網(wǎng)絡(luò),制定了2種可行方案.新路由機(jī)制以現(xiàn)有節(jié)能路由算法為基礎(chǔ),根據(jù)時(shí)間約束修正路由路徑和增添帶有響應(yīng)時(shí)間約束的路由表.分析結(jié)果表明,2種方案在計(jì)算復(fù)雜度和通信功耗上存在一個(gè)平衡,2種方案在實(shí)際傳感器網(wǎng)絡(luò)應(yīng)用下是有效的.仿真試驗(yàn)表明,在路由機(jī)制中引入響應(yīng)時(shí)間是必須的.關(guān)鍵詞:無線傳感器網(wǎng)絡(luò);響應(yīng)時(shí)間;路由機(jī)制0引言作為熱點(diǎn)問題,無線傳感器網(wǎng)絡(luò)(WSN,wirelesssensornetwork)鮮有實(shí)際應(yīng)用.究其原因,主要有以下2點(diǎn):傳感器節(jié)點(diǎn)(SN,sensornode)價(jià)格較高;沒有考慮實(shí)際情況的路由協(xié)議.為詳細(xì)說明第2點(diǎn),首先介紹WSN的性質(zhì).在普遍意義上,它具有以下特性:①SN能量有限;②SN的放置采用飛機(jī)投撒等方式,不能控制;③WSN是無線自主的,設(shè)定SN的初始狀態(tài)之后的拓?fù)鋯?dòng)和網(wǎng)絡(luò)運(yùn)行是自組織的.傳統(tǒng)網(wǎng)絡(luò)路由算法和普通Adhoc網(wǎng)絡(luò)路由算法都不能很好地應(yīng)用于WSN中,針對(duì)傳感器網(wǎng)絡(luò)路由算法的研究,前期比較典型的工作有LEACH,LEACH2,TEEN和PEGAGIS等.它們考慮使鏈路代價(jià)而沒有考慮負(fù)載平衡.之后的工作以負(fù)載平衡和鏈路代價(jià)兩者結(jié)合作為算法性能衡量標(biāo)準(zhǔn),比較典型的有負(fù)載平衡組劃分、化網(wǎng)絡(luò)生命期等.二層路由協(xié)議較平面路由協(xié)議更加負(fù)載平衡.AlbertoCerpa等提出了一種實(shí)際可用的參與度模型,本文路由機(jī)制基于該模型.本文將WSN分為鄰域發(fā)現(xiàn)(ND,neighbordiscovery)、動(dòng)態(tài)參與度模型(DJM,dynamicjoiningmodel)、組內(nèi)路由和組間路由.在假設(shè)前2層模型有較好實(shí)現(xiàn)的情況下研究了組內(nèi)路由算法.為引入響應(yīng)時(shí)間這一WSN應(yīng)用的重要指標(biāo),提出2種方法對(duì)現(xiàn)有的路由算法進(jìn)行改進(jìn):沿用節(jié)能性路由算法并在節(jié)點(diǎn)中根據(jù)響應(yīng)時(shí)間(RT,responsetime)約束修訂路由;組長(CHSN,clusterheadsensornode)在計(jì)算路由時(shí)考慮RT因素,為節(jié)點(diǎn)消息的不同RT要求分別計(jì)算路由.1WSN參考模型及基本假定1.1層次介紹無線傳感器網(wǎng)絡(luò)MAC層、網(wǎng)絡(luò)層以及傳輸層都是WSN中研究的熱點(diǎn)問題.為了明確研究內(nèi)容和方法,提出以能量節(jié)省、響應(yīng)時(shí)間和傳送質(zhì)量為標(biāo)準(zhǔn)將WSN中的課題劃分為物理層、MAC層、網(wǎng)絡(luò)層(該層包含ND協(xié)議、路由等,具體關(guān)系如圖1所示)和應(yīng)用層.圖1細(xì)化的網(wǎng)絡(luò)層1.2ND與DJM協(xié)議ND協(xié)議為每個(gè)SN提供鄰居信息,其中鄰居定義為可以和該節(jié)點(diǎn)單跳傳送的SN集合.考慮到WSN應(yīng)用環(huán)境可能會(huì)有突發(fā)事件,如某SN被監(jiān)控對(duì)象撞壞,使用定時(shí)查詢方式實(shí)現(xiàn)ND協(xié)議,該協(xié)議采集數(shù)據(jù)的類型取決于DJM的設(shè)計(jì).本文使用丟包率、剩余能量和鄰居個(gè)數(shù)作為DJM的參考標(biāo)準(zhǔn),因此,ND協(xié)議需要采集鄰居的能量信息并統(tǒng)計(jì)丟包率.其中,鄰居的判定依據(jù)為丟包率是否小于對(duì)應(yīng)的丟包率門限.在ND協(xié)議提供必要數(shù)據(jù)的基礎(chǔ)上,本文采用了參與度模型,即在某一時(shí)刻只有部分節(jié)點(diǎn)參與組建網(wǎng)絡(luò).該模型中SN有4種狀態(tài)(sleep、passive、test、active),只有處于test和active狀態(tài)時(shí)參與網(wǎng)絡(luò)傳送消息.passive狀態(tài)節(jié)點(diǎn)只接收鄰居狀態(tài)消息,監(jiān)測(cè)網(wǎng)絡(luò)通信質(zhì)量,當(dāng)丟包率和鄰居數(shù)不符合要求時(shí),按狀態(tài)轉(zhuǎn)換自動(dòng)機(jī)轉(zhuǎn)入test狀態(tài)以改善網(wǎng)絡(luò)連通性和通信質(zhì)量,其余sleep節(jié)點(diǎn)休眠以節(jié)能.2路由機(jī)制描述2.1問題與假定本文研究滿足響應(yīng)時(shí)間的節(jié)能組內(nèi)路由機(jī)制.首先,說明對(duì)WSN的描述和假定.①SN能量有限,密集分布,采用飛機(jī)投撒等方式放置,不能控制;②WSN是無線自組網(wǎng),允許多跳(multi-hop)路由;③WSN對(duì)響應(yīng)時(shí)間的要求為硬約束,即數(shù)據(jù)必須在它對(duì)應(yīng)的響應(yīng)時(shí)間內(nèi)傳送到組長.以響應(yīng)時(shí)間為硬約束、能量消耗為標(biāo)準(zhǔn)采用集中式算法考慮組內(nèi)路由策略.因?yàn)楝F(xiàn)有的分布式Bellman-Ford算法要求網(wǎng)絡(luò)初始和拓?fù)渥兓瘯r(shí)所有節(jié)點(diǎn)都必須已知全局拓?fù)?代價(jià)太高.對(duì)于節(jié)能路由,使用貪心算法多次迭代就可得到近似路徑.不考慮RT約束的集中式組內(nèi)節(jié)能路由算法基于以下假定:①組內(nèi)只有一個(gè)組長,它已知組內(nèi)全局拓?fù)?②SN具有初始標(biāo)志,并具有一定的存儲(chǔ)和判定能力;③ND、DJM和鏈路代價(jià)都具有良好的實(shí)現(xiàn).鏈路代價(jià)表示一定量數(shù)據(jù)經(jīng)過一段鏈路的消耗,等于其所含邊對(duì)應(yīng)數(shù)據(jù)傳送的耗能總和.發(fā)送數(shù)據(jù)代價(jià)(使用RSSI測(cè)量)和節(jié)點(diǎn)能量都可以在ND協(xié)議中獲得,使用文獻(xiàn)[1]中鏈路代價(jià)模型.因?yàn)镾N的路由路徑是個(gè)Markov鏈,即鏈路中到第i個(gè)節(jié)點(diǎn)的路由僅由第i-1個(gè)節(jié)點(diǎn)確定.組內(nèi)路由算法可以描述為第1步:針對(duì)每個(gè)SN,SN以化該節(jié)點(diǎn)與CHSN間的鏈路代價(jià)為標(biāo)準(zhǔn)選擇下一跳中繼SN;第2步:若拓?fù)鋬?nèi)路由有變化,轉(zhuǎn)向第1步,否則路由決策結(jié)束.下面提出節(jié)點(diǎn)決策和組長決策2種方式修正路由策略引入RT硬約束.2.2節(jié)點(diǎn)決策經(jīng)過上述路由算法,組長為每個(gè)節(jié)點(diǎn)確定節(jié)能路由并發(fā)送路由表.節(jié)點(diǎn)決策機(jī)制下,每個(gè)節(jié)點(diǎn)根據(jù)消息的RT約束對(duì)組長發(fā)來的路由路徑進(jìn)行調(diào)整.消息m的鏈路延時(shí)使用如式(1)表示,它由數(shù)據(jù)發(fā)送時(shí)間和節(jié)點(diǎn)延遲時(shí)間2部分構(gòu)成.其中,L為對(duì)應(yīng)鏈路;S(m)為m的長度;C(e)為邊e上m的延時(shí),由e的起始節(jié)點(diǎn)的延遲R(e)和發(fā)送S(m)數(shù)據(jù)量的延遲(數(shù)據(jù)長度除以該邊的傳送速率c)2部分構(gòu)成.由式(1)可見,鏈路包含節(jié)點(diǎn)數(shù)越少,延遲時(shí)間越短.節(jié)點(diǎn)決策路由表述為:對(duì)應(yīng)于每個(gè)發(fā)送消息的RT約束,SN逐步去除鏈路中SN的直接中繼節(jié)點(diǎn)(SN找其直接中繼節(jié)點(diǎn)的直接中繼做直接中繼節(jié)點(diǎn)),直至滿足該RT約束或者該SN無法直接傳送到下一中繼節(jié)點(diǎn).2.3組長決策節(jié)點(diǎn)決策機(jī)制較簡單,但是節(jié)能效果不是.可以利用組長進(jìn)行決策,在原有的節(jié)能鏈路上為不同RT約束等級(jí)計(jì)算路由.不失一般性,假定SN具有相同的通信模型,此時(shí)RT約束可以轉(zhuǎn)化為鏈路中繼節(jié)點(diǎn)數(shù)的約束.組長決策路由為:對(duì)于某SN,設(shè)節(jié)能算法(如2.1節(jié)所述)計(jì)算出的路由鏈路為L,對(duì)應(yīng)的中繼節(jié)點(diǎn)集合為C,RT等級(jí)集合為R(RT等級(jí)已經(jīng)轉(zhuǎn)化為中繼節(jié)點(diǎn)的個(gè)數(shù)).對(duì)應(yīng)R中每個(gè)等級(jí)r(r=1,2,.)在C中選取構(gòu)成鏈路能量消耗的r個(gè)節(jié)點(diǎn).下面介紹節(jié)點(diǎn)決策和組長決策算法應(yīng)用到WSN路由機(jī)制中的相關(guān)問題.3路由機(jī)制應(yīng)用同構(gòu)和異構(gòu)網(wǎng)絡(luò)的啟動(dòng)方式不盡相同,基本的啟動(dòng)過程為:節(jié)點(diǎn)定時(shí)啟動(dòng),處于test狀態(tài);ND協(xié)議;根據(jù)DJM確定節(jié)點(diǎn)狀態(tài)(組長節(jié)點(diǎn)和普通節(jié)點(diǎn));組劃分與組間路由;組內(nèi)路由;事件驅(qū)動(dòng)拓?fù)淇刂?組內(nèi)路由初始時(shí)使用直接傳送協(xié)議收集網(wǎng)絡(luò)拓?fù)湫畔?CHSN收集完組內(nèi)拓?fù)浜?運(yùn)行本文提出的考慮RT約束的節(jié)能路由算法.事件驅(qū)動(dòng)機(jī)制為:僅當(dāng)組長變化或者組內(nèi)拓?fù)渥兓瘯r(shí),組長重新計(jì)算路由.組長變化有2種情況:CHSN主動(dòng)退休和CHSN突然出現(xiàn)故障.組內(nèi)局部拓?fù)渥兓性黾雍腿コ?jié)點(diǎn)2種情況.協(xié)議中使用多入單出式路由表,使得每個(gè)SN向路由表中后繼節(jié)點(diǎn)傳送信息(采集信息和中繼信息).節(jié)點(diǎn)決策路由中,每個(gè)節(jié)點(diǎn)需保存自己到CHSN路徑中每一跳節(jié)點(diǎn)信息.而組長決策路由表要為每個(gè)RT級(jí)別存儲(chǔ)一個(gè)下一跳節(jié)點(diǎn)信息(只有數(shù)據(jù)采集信息具有響應(yīng)時(shí)間約束,其他信息如路由信息等無此約束).消息每中繼,對(duì)應(yīng)的RT字段便更新并根據(jù)當(dāng)前節(jié)點(diǎn)的路由表發(fā)送.4模型驗(yàn)證4.1模型分析路由機(jī)制的復(fù)雜度包括:CHSN時(shí)間、空間復(fù)雜度、SN時(shí)間、空間復(fù)雜度和全局的通信復(fù)雜度.首先對(duì)組內(nèi)信息做以下設(shè)定:①組內(nèi)節(jié)點(diǎn)數(shù)為n;②組半徑為r,即組內(nèi)節(jié)點(diǎn)與組長傳送消息所需的跳步數(shù);③響應(yīng)時(shí)間劃分為g個(gè)級(jí)別.首先分析未考慮響應(yīng)時(shí)間約束的節(jié)能算法復(fù)雜度.211節(jié)所述組內(nèi)路由算法每次迭代的平均和壞時(shí)間復(fù)雜度都是O(n2)(壞復(fù)雜度為n2,平均復(fù)雜度為n2/2),而經(jīng)過模擬測(cè)試知迭代次數(shù)是有限的(隨機(jī)分布的500個(gè)節(jié)點(diǎn)的情況迭代次數(shù)不超過20次).下面分別分析節(jié)點(diǎn)決策和組長決策機(jī)制.4.1.1節(jié)點(diǎn)決策復(fù)雜度首先分析通信復(fù)雜度.因?yàn)槁酚纱_定過程的數(shù)據(jù)包主要是路由信息包,1個(gè)路由數(shù)據(jù)包帶來的復(fù)雜度等于包長與包傳送次數(shù)的乘積.該包中數(shù)據(jù)信息為發(fā)送路徑的標(biāo)志集合,1個(gè)需要m跳的路由信息的通信復(fù)雜度為Comm(m)=mLhead+Lidm(m-1)/2(2)其中,通信復(fù)雜度Comm為跳數(shù)m的函數(shù);Lhead為數(shù)據(jù)包首部長度;Lid為節(jié)點(diǎn)標(biāo)志占用比特?cái)?shù).更新1個(gè)節(jié)點(diǎn)路由信息的壞復(fù)雜度為Comm(r)即O(r2);更新所有節(jié)點(diǎn)路由信息(所有節(jié)點(diǎn)的路由信息都需要更新)的壞復(fù)雜度為O(rn).現(xiàn)有的更新方式為flooding方式,更新1個(gè)路由信息的通信復(fù)雜度為O(nr).組長時(shí)間復(fù)雜度即為組內(nèi)路由算法復(fù)雜度,空間復(fù)雜度為路由表的存儲(chǔ)和路由路徑的存儲(chǔ).路由表為Lid,為(n-1)Lid.節(jié)點(diǎn)路由的平均和壞時(shí)間復(fù)雜度都為O(n),路由表多入單出,邊緣節(jié)點(diǎn)(處于網(wǎng)絡(luò)拓?fù)溥吘?不做中繼的節(jié)點(diǎn))的路由表為Lid,其他普通節(jié)點(diǎn)空間復(fù)雜度為2Lid,空間復(fù)雜度為nLid.路由路徑的壞空間復(fù)雜度為rLid.因此,邊緣節(jié)點(diǎn)的空間復(fù)雜度為(r+1)×Lid,其他普通節(jié)點(diǎn)的空間復(fù)雜度為(r+2)Lid,為(r+n-1)Lid.4.1.2組長決策復(fù)雜度通信復(fù)雜度是節(jié)點(diǎn)決策通信復(fù)雜度的g倍;組長時(shí)間復(fù)雜度為2.1節(jié)所述組內(nèi)路由算法的復(fù)雜度和路徑處理的復(fù)雜度(復(fù)雜度為O(nCgr)),組長空間復(fù)雜度和第3節(jié)所述節(jié)點(diǎn)決策復(fù)雜度相同;節(jié)點(diǎn)路由的時(shí)間復(fù)雜度為O(1),邊緣節(jié)點(diǎn)的空間復(fù)雜度為gLid,其他普通節(jié)點(diǎn)的空間復(fù)雜度為(g+1)×Lid,為(g+n)Lid.4.2系統(tǒng)模擬本節(jié)討論引入RT約束引起的能量消耗.為了滿足硬性時(shí)間約束,WSN能量損耗會(huì)有所增加,由于鮮有相關(guān)的工作,只討論本文提出的2種機(jī)制的能量損耗表現(xiàn).通過比較RT約束下SN的平均功耗與不考慮RT約束的對(duì)應(yīng)值,機(jī)制的可用性可以得到檢驗(yàn).在不影響結(jié)果有效性的前提下,對(duì)WSN做如下假設(shè):①節(jié)點(diǎn)隨機(jī)分布且所有節(jié)點(diǎn)是同構(gòu)的(節(jié)點(diǎn)具有相同的通信模型和能量模型);②所有節(jié)點(diǎn)同組,即網(wǎng)絡(luò)僅有1個(gè)組長節(jié)點(diǎn).③MAC層、ND層和DJM層具有良好實(shí)現(xiàn),只討論活動(dòng)節(jié)點(diǎn).SN參數(shù)根據(jù)伯克利大學(xué)的Mica2設(shè)定,應(yīng)用以森林防火為例,對(duì)一個(gè)邊為50m的方形區(qū)域(組長位于左上角)的系統(tǒng)模擬.圖2中的曲線表示節(jié)點(diǎn)決策下SN平均功耗和無RT約束節(jié)能算法下SN平均功耗的比值.可以看出,在RT較小即跳步數(shù)較少的情況下,網(wǎng)絡(luò)耗能會(huì)有較大變化.曲線下的方框代表RT級(jí)別為1時(shí),組長決策的SN平均功耗和無RT約束的節(jié)能算法下SN平均功耗的比值.可以看出,組長決策優(yōu)于節(jié)點(diǎn)決策路由(圖中前者為9.5倍,后者為8.5倍).圖2節(jié)能路由算法和考慮響應(yīng)時(shí)間約束的節(jié)能路由比較總之,考慮RT約束必須更改