位置固定節(jié)點的無線傳感網(wǎng)絡廣播算法研究【開題報告】

1、<p><b>　　畢業(yè)設計開題報告</b></p><p><b>　　測控技術與儀器</b></p><p>　　位置固定節(jié)點的無線傳感網(wǎng)絡廣播算法研究</p><p><b>　　1選題的背景、意義</b></p><p>　　無線傳感器網(wǎng)絡(Wireless

2、Sensor Networks，wSN)是集信息采集、信息傳輸、信息處理于一體的綜合智能信息系統(tǒng)，是目前倍受國際關注、涉及多學科交叉知識、各項技術高度集合的前沿熱點研究領域之一，它綜合了微機電系統(tǒng)(Micro．Electron Mechanical System，MEMS)、傳感器技術、嵌入式計算技術、現(xiàn)代網(wǎng)絡及無線通信技術、分布式信息處理技術等。作為一種新興測控網(wǎng)絡技術，它能夠通過各類集成化的傳感器自主實現(xiàn)數(shù)據(jù)采集、融合和傳輸，并以自

3、主多跳的網(wǎng)絡方式傳送給用戶終端，從而實現(xiàn)物理世界、計算機世界和人類社會三元世界的連通。無線傳感器網(wǎng)絡能夠應用在軍事國防、工農(nóng)業(yè)控制、城市管理、環(huán)境監(jiān)測、生物醫(yī)療、搶險救災、防恐反恐、危險區(qū)域遠程控制等諸多領域，具有非常廣泛的應用前景，</p><p>　　由于無線傳感器網(wǎng)絡中節(jié)點數(shù)目龐大，使得其在組網(wǎng)和通信時要采用廣播方式，以加快信息傳播的范圍和速度，從而可以節(jié)省電力。廣播是無線傳感器網(wǎng)絡最基礎的通信方式之一，它

4、的目的是將信息從網(wǎng)絡中源節(jié)點發(fā)送給網(wǎng)絡中其余的每一個節(jié)點。廣播可以實現(xiàn)網(wǎng)絡的控制、時間同步、路由建立與維護資源分配與管理等。</p><p>　　廣播在無線傳感器網(wǎng)絡中具有極為廣泛的應用．如節(jié)點向全網(wǎng)通告重要數(shù)據(jù)，sink點向全網(wǎng)周期性查詢數(shù)據(jù)等．簡單泛洪(flooding)可以實現(xiàn)廣播．這種方式雖然簡單但極為耗能，而通常無線傳感器網(wǎng)絡節(jié)點電池容量有限且一般不可充電或更換，并且數(shù)據(jù)傳輸極為耗費能量．所以簡單泛洪并

5、不適合無線傳感器網(wǎng)絡廣播。無線傳感器網(wǎng)絡節(jié)點位置相對固定，但是節(jié)點數(shù)量巨大，密集高，冗余轉播加劇了網(wǎng)絡的擁塞、信道的競爭和數(shù)據(jù)沖突，從而降低網(wǎng)絡的性能，增加節(jié)點的能量消耗，縮短網(wǎng)絡的壽命，因而設計優(yōu)化無線傳感器網(wǎng)絡的廣播算法有著現(xiàn)實意義。</p><p>　　2相關研究的最新成果及動態(tài) </p><p>　　在國內(nèi)外相關文獻中相繼出現(xiàn)了許多各具特點的無線傳感器網(wǎng)絡廣播算法，但總的說來還有很

6、多需要深入研究的問題。</p><p>　　(1)文獻[3-4]對泛洪廣播方法進行了改進，提出了基于概率、基于計數(shù)、基于距離等的廣播策略。這些策略減少了冗余分組轉播的數(shù)量，但是信道的競爭、數(shù)據(jù)沖突仍然較大，廣播延遲較長，此外，還可能會丟棄一些非冗余的廣播分組，無法保證廣播分組的可達性。在基于概率的算法中，節(jié)點在接收到數(shù)據(jù)包后以概率戶轉發(fā)數(shù)據(jù)包，以概率l—p丟棄數(shù)據(jù)包．在基于計數(shù)的算法中，節(jié)點只有在接收到的數(shù)據(jù)包副

7、本率小于設定的門限值時才轉發(fā)數(shù)據(jù)包．在基于位置的算法中，節(jié)點根據(jù)自身位置以及在一段時間內(nèi)偵聽到的其它發(fā)送節(jié)點的位置信息決定是否轉發(fā)數(shù)據(jù)包．這些算法雖然簡單，但是減少的冗余節(jié)點數(shù)有限，性能改善并不明顯．</p><p>　　(2)基于連通支配集的路由算法的關鍵在于構造連通支配集，較小的支配集不但有利于構造更優(yōu)的路由，并且非支配節(jié)點在沒有監(jiān)測任務時，可進入休眠狀態(tài)，從而極大的節(jié)約能量。據(jù)此提出了一種基于極大獨立集構造

8、最小連通支配集的算法MISB：首先基于圖的局部拓撲信息，并利用貪心算法，使具有極大度的節(jié)點為獨立點，構造出一個極大獨立集；然后利用獨立點作為錨點，利用分治的思想使用圖的局部拓撲信息來連通極大獨立集，從而構造出連通支配集。MISB算法能夠得到較小的連通支配集，應用于無線傳感器網(wǎng)絡路由，能夠大大節(jié)省寶貴的網(wǎng)絡資源。</p><p>　　(3)在節(jié)點發(fā)送功率可調(diào)節(jié)并同時保證所有節(jié)點都接收到廣播的數(shù)據(jù)包的約束條件下，據(jù)此

9、在RBOP算法的基礎上提出了一種高效節(jié)能的最小化能量廣播算法ERBOP。ERBOP算法的設計過程及仿真結果表明，ERBOP的性能明顯優(yōu)于RBOP。ERBOP算法可節(jié)約無線傳感器網(wǎng)絡的能量資源，能較好的適用于無線傳感器網(wǎng)絡的廣播。</p><p>　　(4)從減少轉發(fā)節(jié)點以節(jié)約能量、平衡通信量以平均消耗網(wǎng)絡節(jié)點能量出發(fā)，提出了一種基于聚簇的能量感知廣播算法CBEA。仿真實驗表明，CBEA算法有效減少了冗余轉發(fā)節(jié)點從

10、而節(jié)約了網(wǎng)絡能量，平衡了網(wǎng)絡通信量從而平均消耗了網(wǎng)絡節(jié)點能量，因此大大延長了網(wǎng)絡生存時間。cBEA算法是一種性能優(yōu)越的廣播算法，能夠較好的適用于無線傳感器網(wǎng)絡的廣播。</p><p>　　（5）提出了MPR方法。MPR利用2一hop鄰節(jié)點信息最小化轉發(fā)節(jié)點集．基于連通支配集的廣播算法【10-12】是目前研究得較多的一類廣播算法，該類算法大多也是利用2-hop鄰節(jié)點信息計算連通支配集，只有支配節(jié)點才參與轉發(fā)數(shù)據(jù)包．

11、這些利用2-hop鄰節(jié)點信息的廣播算法雖然具有較好的性能，但需要更多的通信開銷以獲取和維護2一hop的鄰節(jié)點信息，不適應拓撲變化．</p><p>　　（6）提出了一種僅利用l-hop鄰節(jié)點信息的邊緣轉發(fā)算法EFB．在EFB算法中，</p><p>　　節(jié)點首先將其傳輸范圍劃分為6個大小相等的扇形區(qū)域．圖l表示了節(jié)點A的傳輸范圍劃分情況．節(jié)點A的6個區(qū)域記為，Ap1，Ap2，?，Ap6，并

12、記表示兩個相鄰節(jié)點的區(qū)域相交情況．當節(jié)點B從鄰節(jié)點A接收到數(shù)據(jù)包后，確定自身處于節(jié)點A的哪個扇形區(qū)域中．EFB算法具有較好的性能，且只利用1-hop鄰節(jié)點信息．通信開銷較?。?lt;/p><p>　　圖2中，不失一般性，假設節(jié)點B處于節(jié)點A的Ap1區(qū)域．節(jié)點B不充當轉發(fā)節(jié)點的條件是，在Ap1區(qū)域與節(jié)點B的各個區(qū)域相交的區(qū)域中，距離節(jié)點以最遠的3個邊緣區(qū)域Ap11，Ap12與Ap16。中每個區(qū)域都存在其它節(jié)點，并且Ap

13、12中節(jié)點的傳輸范圍覆蓋了區(qū)域a，Ap16，中節(jié)點傳輸范圍覆蓋了區(qū)域6．區(qū)域a、b表示了被節(jié)點B的傳輸范圍覆蓋而沒有被節(jié)點A的傳輸范圍覆蓋的區(qū)域．EFB算法具有較好的性能，且只利用1-hop鄰節(jié)點信息．通信開銷較?。?lt;/p><p>　　但我們發(fā)現(xiàn)EFB算法仍存在一些不足之處，在廣播過程中還有冗余轉發(fā)節(jié)點存在，影響了算法的性能．</p><p>　　3課題的研究內(nèi)容及擬采取的研究方法（技術

14、路線）、研究難點及預期達到的目標</p><p><b>　?。?）研究內(nèi)容：</b></p><p>　　為進一步減少冗余轉發(fā)節(jié)點，本文提出了一種利用l-hop鄰節(jié)點信息的基于傳輸范圍覆蓋的廣播算法TRCB．在TRCB算法中，由發(fā)送節(jié)點決定其l—hop鄰節(jié)點是否參與轉發(fā)，如果該節(jié)點被轉發(fā)節(jié)點以及參與轉發(fā)的1一hop鄰節(jié)點覆蓋。將不參與轉發(fā)．</p>&

15、lt;p><b>　?。?）研究方法：</b></p><p>　　采用Matlab作為仿真軟件，在設定的區(qū)域內(nèi)隨機產(chǎn)生節(jié)點的二維坐標，并且當節(jié)點間的距離小于傳輸半徑時節(jié)點相鄰，每個節(jié)點都存儲了其鄰節(jié)點的坐標信息。然后利用本文算法進行仿真。</p><p><b>　?。?）研究難點：</b></p><p>　　a

16、. 節(jié)點U是否被集合S覆蓋的問題。</p><p>　　b.計算節(jié)點U的轉發(fā)節(jié)點集。</p><p>　　c. 計算節(jié)點U0是否被集合5覆蓋。</p><p>　　(4)預期達到目標：</p><p>　　TRCB的轉發(fā)率均遠小于EFB算法，性能遠優(yōu)于同樣是利用1一hop鄰節(jié)點信息的邊緣轉發(fā)算法EFB．</p><p>

17、;　　4研究工作詳細進度和安排</p><p>　　2010年10月15日——12月15日 閱讀相關的資料；</p><p>　　2010年12月16日——2011年01月10日完成文獻綜述、外文翻譯的撰寫；</p><p>　　2011年01月10日——02月25日 完成開題報告；</p><p>　　2011年02月26日——04月08日

18、 完成系統(tǒng)框架設計和系統(tǒng)各模塊功能設計；</p><p>　　2011年04月09日——05月10日 撰寫論文，完成論文初稿；</p><p>　　2011年05月11日——05月25日 完成論文修改稿，準備答。</p><p><b>　　5參考文獻</b></p><p>　　[1]崔莉．鞠海玲．苗勇。等．無線傳感器

19、網(wǎng)絡研究進展[J]．計算</p><p>　　機研究與發(fā)展,2005,42(1):163-174．</p><p>　　[2]唐勇，周明天,張欣．無線傳感器網(wǎng)絡路由協(xié)議研究進展 [J]．軟件學報，2006,17(3):410-421．</p><p>　　[3] CorsonM S,Macker J P,Cirincione G H.Internet-based m

20、obile Ad Hoc networking[J].IEEE Internet Computing,1999,3(4):63-70.</p><p>　　[4] Ni S Y,Tseng Y C,Chen Y S,et al.The broadcast storm problem in a mobile Ad Hoc network[C]. Proc MOBICOM,1999:151-162.</p>

21、;<p>　　[5]Cai Y，Hua K，PhiIlips A．Leveraging 1-hop neighborhood knowIedge for efficient nooding in wireless ad hoc networks[C]．Proc of the 24th IEEE Int’l Performance Computing and Communications Conf．,Arizona,USA,

22、2005,347-354．</p><p>　　[6]Sasson Y,Cavin D，schiper A．Probabilistic broadcast for fooding in wireless mobile ad hoc networks[C]．Proc of the IEEE Wireless Communications and Networking Conf．(WCNC’03)，New Orlea

23、ns，Louisiana,USA，20031124—1130．</p><p>　　[7]Tseng Y．Ni S，Shih E．Adaptive approaches to relieving broadcast storms in a wireless multihop mobile ad hoc network[J]．IEEE Transactions on Computers，2003，52(5):545

24、-557．</p><p>　　[8]Williams B,Mehta D，Camp T，et a1．Predictive modeIs to rebroadcast in mobile ad hoc networks[J]．IEEE Transactions on Mobile Computing，2004，3(3)：295—303．</p><p>　　[9]Laouiti A,Qay

25、yum A,Viennot L．MuItipoint relaying;an efficient technique for flooding in mobile wireless networks[C].Proc of the 35th Annual Hawaii Int’l Conf.on System Sciences.Hawaii,USA,2002,298-307.</p><p>　　[10]Stojm

26、bnovic I,seddigh M,Zunic J．Dominating sets and neighbor elilIlination based broadcasting algorithms in wireIess networks[J]．IEEE Transactions on Parallel and Distributed Systems．2002，13(1):114—25．</p><p>　　[

27、11]Wu J，Li H．On calculating connected dominatillg set for efficient routing in ad hoc wireless networks[C]．Proc of the 3rd Int’I Workshop on Discrete Algofithms and Methods for Mobile Computing and Communications，USA．199

28、9,7-14．</p><p>　　[12]Wan P，Alzoubi K,Frieder O．Distributed construction of connected dominating set in wireless ad hoc networks[c]．Proc of IEEE Infocom,USA，2002．1597-1604．</p><p>　　[13] 盧先領.無沖突的