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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、網(wǎng)絡(luò)研究進(jìn)展[J]．計(jì)算</p><p>　　機(jī)研究與發(fā)展,2005,42(1):163-174．</p><p>　　[2]唐勇，周明天,張欣．無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議研究進(jìn)展 [J]．軟件學(xué)報(bào)，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] 盧先領(lǐng).無(wú)沖突的