無線傳感器網(wǎng)絡(luò)自組織算法關(guān)鍵技術(shù)的研究.pdf

1、無線傳感器網(wǎng)絡(luò)綜合了傳感器技術(shù)、嵌入式計(jì)算技術(shù)、現(xiàn)代網(wǎng)絡(luò)及無線通信技術(shù)、分布式信息處理技術(shù)等,能夠通過各類集成化的微型傳感器相互協(xié)作,實(shí)時(shí)監(jiān)測、感知和采集各種環(huán)境或監(jiān)測對象的信息,通過嵌入式系統(tǒng)對信息進(jìn)行處理,并通過隨機(jī)自組織無線通信網(wǎng)絡(luò)以多跳中繼方式將所感知信息傳送到用戶終端,從而真正實(shí)現(xiàn)"無處不在的計(jì)算".無線傳感器網(wǎng)絡(luò)可廣泛用于軍事、國家安全、環(huán)境科學(xué)、交通管理、反恐維和、災(zāi)害預(yù)測、智能城市建設(shè)等領(lǐng)域.其巨大的科學(xué)意義和應(yīng)用價(jià)值,

2、已經(jīng)引起了學(xué)術(shù)界、工業(yè)界和軍事部門的極大關(guān)注,成為當(dāng)前熱門的研究領(lǐng)域.美國《技術(shù)評論》把無線傳感器網(wǎng)絡(luò)列為未來十項(xiàng)新興技術(shù)之首.《IEEE Spectrum》預(yù)計(jì)無線傳感器網(wǎng)絡(luò)的發(fā)展和廣泛應(yīng)用,將對人們的社會生活和產(chǎn)業(yè)變革帶來極大的影響和產(chǎn)生巨大的推動.《國家中長期科學(xué)和技術(shù)發(fā)展規(guī)劃綱要》和《國家"十一五"科學(xué)技術(shù)發(fā)展規(guī)劃》將"傳感器網(wǎng)絡(luò)與智能信息處理"提升到信息產(chǎn)業(yè)發(fā)展的一個(gè)重點(diǎn)領(lǐng)域與優(yōu)先主題,并把它列為具有前瞻性、先導(dǎo)性和探索性的重

3、大前沿技術(shù). 無線傳感器網(wǎng)絡(luò)因?yàn)椴灰蕾囉诠潭ǖ幕A(chǔ)設(shè)施,所以網(wǎng)絡(luò)節(jié)點(diǎn)要求具有自組織的能力.一個(gè)節(jié)點(diǎn)進(jìn)入工作區(qū)域之后,它只能依賴于MAC層和物理層所能提供的有限機(jī)制獲得周圍一跳(one-hop)鄰居的信息,對全網(wǎng)的拓?fù)浣Y(jié)構(gòu)將一無所知.這時(shí)候需要有一個(gè)算法將這些分散的節(jié)點(diǎn)有效地組織起來,協(xié)調(diào)一致來完成某一個(gè)特定的任務(wù),這一類的算法就叫做自組織算法.它為整個(gè)系統(tǒng)的運(yùn)行構(gòu)建拓?fù)浠A(chǔ),在此之上,各種路由協(xié)議、傳輸層協(xié)議以及應(yīng)用程序才能正常

4、運(yùn)作,可以說,自組織算法是整個(gè)無線傳感器網(wǎng)絡(luò)的"基石". 自組織算法是與網(wǎng)絡(luò)的拓?fù)錁?gòu)建與控制聯(lián)系在一起的.一般來說,無線傳感器網(wǎng)絡(luò)的組織拓?fù)浞譃槠矫娼Y(jié)構(gòu)和層次結(jié)構(gòu),相應(yīng)的,自組織的算法也分為基于平面結(jié)構(gòu)的算法和基于層次結(jié)構(gòu)的算法.層次結(jié)構(gòu)與平面結(jié)構(gòu)相比,在網(wǎng)絡(luò)管理、系統(tǒng)擴(kuò)展性、降低系統(tǒng)開銷,提高網(wǎng)絡(luò)吞吐能力以及QoS支持等各方面都存在明顯的優(yōu)勢,所以隨著應(yīng)用的增加,大規(guī)模的無線傳感器網(wǎng)絡(luò)逐漸呈現(xiàn)出層次化的趨勢,基于層次型結(jié)構(gòu)的自

5、組織算法是目前研究的重點(diǎn).層次型結(jié)構(gòu)的自組織算法一般包括分簇(clustering)方法與連通支配集 (Connected Dominating Sets) 方法.分簇方法是指在網(wǎng)絡(luò)規(guī)劃初期通過分布式算法將網(wǎng)絡(luò)劃分成簇頭節(jié)點(diǎn)與普通節(jié)點(diǎn).連通支配集的方法是利用圖論中連通支配集的理論在傳感器網(wǎng)絡(luò)中構(gòu)建類似于因特網(wǎng)的虛擬骨干網(wǎng)(Virtual Backbone),整個(gè)網(wǎng)絡(luò)被劃分成骨干節(jié)點(diǎn)集和普通節(jié)點(diǎn)集.在這兩種方法中,簇頭和骨干節(jié)點(diǎn)完成拓?fù)涔?/p>

6、理、路由構(gòu)建與維護(hù)以及資源分配等功能. 論文的第三部分研究了無線傳感器網(wǎng)絡(luò)的分布式分簇算法.首先證明了經(jīng)典IEACH算法的不確定性將會導(dǎo)致某些節(jié)點(diǎn)過快耗盡電池能量而縮短網(wǎng)絡(luò)生存期.在此基礎(chǔ)之上,提出了一種基于退避策略的負(fù)載均衡的分簇算法,通過自適應(yīng)地調(diào)整每個(gè)節(jié)點(diǎn)的退避等待時(shí)間從而保證擁有較多電池能量的節(jié)點(diǎn)有更大的機(jī)會成為簇頭,并引入信道競爭機(jī)制來保證簇頭的均勻分布,仿真實(shí)驗(yàn)表明,該算法有效延長了系統(tǒng)生命,提高了網(wǎng)絡(luò)的能耗效率.接

7、下來作者進(jìn)一步擴(kuò)展了以上分簇算法的研究工作,提出了一種兩參數(shù)的分布式分簇算法,該算法能夠通過參數(shù)的設(shè)置確保簇頭的均勻分布,從而避免了借助下層信道競爭機(jī)制來完成這一目的,降低了算法的實(shí)現(xiàn)復(fù)雜性.簇頭分布均勻?qū)蟠蠼档推胀ü?jié)點(diǎn)成為"被動型簇頭"的可能,減少節(jié)點(diǎn)與基站進(jìn)行遠(yuǎn)程通信的次數(shù),節(jié)約有限的系統(tǒng)能量. 論文的第四部分研究了無線傳感器網(wǎng)絡(luò)異構(gòu)分簇模型.近來提出的基于異構(gòu)分簇模型的無線傳感器網(wǎng)絡(luò),是指網(wǎng)絡(luò)中存在多種不同能力的節(jié)點(diǎn),

8、能力強(qiáng)的節(jié)點(diǎn)自動成為簇頭,這種網(wǎng)絡(luò)避免了復(fù)雜的簇頭選舉過程并有效降低了普通節(jié)點(diǎn)的硬件復(fù)雜性和成本.但是,固定簇頭的方法會削弱系統(tǒng)的負(fù)載均衡以及魯棒性.為了解決這個(gè)問題,本文提出了一種基于自適應(yīng)退避策略的簇頭調(diào)度方案,該方案通過適當(dāng)增加冗余度實(shí)現(xiàn)傳感節(jié)點(diǎn)的k履蓋,增強(qiáng)了網(wǎng)絡(luò)的魯棒性.同時(shí),依賴于地理信息和剩余電池能量信息,簇頭節(jié)點(diǎn)通過自主周期性睡眠來保證系統(tǒng)負(fù)載的均衡分配,延長網(wǎng)絡(luò)生存期. 在論文的第五部分,研究了基于連通支配集(

9、CDS)的虛擬骨干網(wǎng)形成算法.CDS的構(gòu)造算法要盡可能地減少參與路由計(jì)算的節(jié)點(diǎn)數(shù)量,即生成最小連通支配集(MCDS).本文提出了一種分布式的CDS形成算法,通過去除虛擬骨干網(wǎng)中所有的三角形回路,有效減少了骨上海交通大學(xué)博士學(xué)位論文:無線傳感器網(wǎng)絡(luò)臼組織算法關(guān)鍵技術(shù)的研究干網(wǎng)中節(jié)點(diǎn)的數(shù)目.同時(shí),該算法具有線性的時(shí)間和消息復(fù)雜性以及較低的實(shí)現(xiàn)復(fù)雜性.理論分析和仿真結(jié)果都顯示本文的算法優(yōu)于經(jīng)典算法. 本論文的第六部分,研究了與數(shù)據(jù)融合

10、相關(guān)的移動代理路由選擇問題.在分簇結(jié)構(gòu)的傳感器網(wǎng)絡(luò)中,簇中的傳感器節(jié)點(diǎn)并不直接發(fā)送原始數(shù)據(jù),而是由簇頭發(fā)送移動代理到各個(gè)節(jié)點(diǎn)收集有用的數(shù)據(jù),實(shí)現(xiàn)數(shù)據(jù)的融合.為了獲取簇中節(jié)點(diǎn)的數(shù)據(jù),在每一個(gè)數(shù)據(jù)融合周期內(nèi),簇頭需要事先計(jì)算好移動代理的路由,即選擇一條路線,在保證有用數(shù)據(jù)被采集到的前提下,使數(shù)據(jù)融合過程所消耗的能量最少從而最大化網(wǎng)絡(luò)生存期.考慮到傳感器節(jié)點(diǎn)覆蓋范圍有限以及相鄰節(jié)點(diǎn)測量數(shù)據(jù)強(qiáng)相關(guān)性的特點(diǎn),本文將多跳網(wǎng)絡(luò)環(huán)境下的移動代理路由問題