專利名稱：基于樹狀結(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)能量高效廣播方法
技術(shù)領(lǐng)域：
本發(fā)明屬于無線傳感器網(wǎng)絡(luò)節(jié)能廣播路由領(lǐng)域。具體涉及一種在無線傳感器網(wǎng)絡(luò)中通過局部范圍內(nèi)相互交換節(jié)點能量信息的方法，通過該方法獲得局部范圍節(jié)點能量高低次序信息，并將其應(yīng)用到廣播樹構(gòu)造中去，達(dá)到均衡使用無線傳感器網(wǎng)絡(luò)節(jié)點能量、延長網(wǎng)絡(luò)生命的目標(biāo)。
背景技術(shù)：
無線傳感器網(wǎng)絡(luò)由傳感器節(jié)點和信息采集(sink)節(jié)點組成，傳感器節(jié)點負(fù)責(zé)數(shù)據(jù)的采集和傳輸，sink節(jié)點負(fù)責(zé)匯總網(wǎng)絡(luò)中傳感器節(jié)點發(fā)來的數(shù)據(jù)，同時也是整個網(wǎng)絡(luò)的控制節(jié)點，對網(wǎng)絡(luò)中其它傳感器節(jié)點進(jìn)行管理。
由于無線傳感器網(wǎng)絡(luò)中節(jié)點在部署后，很難進(jìn)行回收。因此，在部署后很難為節(jié)點更換電池或?qū)ζ湓俅纬潆?。因此，?jié)點電源耗盡，就意味著節(jié)點死亡，無法再投入使用。當(dāng)一個網(wǎng)絡(luò)中死亡節(jié)點達(dá)到一定比率時，網(wǎng)絡(luò)可能會被分割成不連通的區(qū)域。如果區(qū)域內(nèi)沒有sink節(jié)點。那么該區(qū)域網(wǎng)絡(luò)所采集的數(shù)據(jù)就無法傳送出去，等同于此區(qū)域所有節(jié)點死亡。因此，需要研究一種能量均衡消耗的路由協(xié)議，避免頻繁使用某些節(jié)點而導(dǎo)致其快速死亡。
多目標(biāo)廣播是從廣播源向目標(biāo)組連續(xù)發(fā)送信息的過程。多目標(biāo)廣播交通是經(jīng)由廣播樹從廣播源傳送到機(jī)組中的所有接收主機(jī)。其中廣播樹以源節(jié)點為樹根，以目的節(jié)點為樹葉。

發(fā)明內(nèi)容
本發(fā)明的目的是設(shè)計一種面向無線傳感器網(wǎng)絡(luò)節(jié)能廣播路由方法。它運行于網(wǎng)絡(luò)層，完成能量高效的廣播樹的建立。
本發(fā)明的技術(shù)方案是在無線傳感器網(wǎng)絡(luò)中，節(jié)點在局部范圍內(nèi)交換的各自剩余能量信息，協(xié)議保護(hù)在局部區(qū)域范圍內(nèi)能量最少的一定比例的節(jié)點(比如，能量最少的10%節(jié)點)，降低它們作為廣播樹的樹內(nèi)節(jié)點的可能性一一從而降低它們參與分組轉(zhuǎn)發(fā)的可能性。本發(fā)明的方法簡單且易于實現(xiàn)。


圖1為按本發(fā)明的方法生成樹的狀態(tài)示意。
具體實施例方式
下面結(jié)合附圖及實例對本發(fā)明作進(jìn)一步的說明。
3協(xié)議分成三個階段，第一階段完成局部能量信息交換，在第二階段，根據(jù)第一階段獲得的能量信息，建立廣播樹。在第三階段，廣播信源按照第二階段建立的廣播樹，發(fā)送數(shù)據(jù)。前兩個階段可以并行進(jìn)行。
本方法實施過程假設(shè)每一個節(jié)點知道自己的鄰居節(jié)點。
第一階段完成局部能量信息交換。每個節(jié)點以周期T向自己相鄰區(qū)域擴(kuò)散自己的剩余能量信息分組。每個節(jié)點應(yīng)保存一個序列號seq。每個剩余能量信息分組攜帶下述信息源節(jié)點id值、seq值、該節(jié)點剩余能量數(shù)值、TTL值。Seq初值為0，每擴(kuò)散一次該類分組，seq值加l。 TTL值表示該分組可以擴(kuò)散的范圍(跳數(shù))。這樣，可以通過seq值和id值唯一的標(biāo)識一個能量信息分組，避免中間節(jié)點重復(fù)轉(zhuǎn)發(fā)。并且，seq可以標(biāo)識能量信息分組的新鮮程度，節(jié)點可以不處理陳舊的分組。所有的能量信息分組會被鄰居本地存貯后繼續(xù)轉(zhuǎn)發(fā)，每次轉(zhuǎn)發(fā)之前將分組TTL域的值減一。如果TTL值為0，則停止轉(zhuǎn)發(fā)。假定TTL初值為k。那么，網(wǎng)絡(luò)中每個節(jié)點都可以收到自己k跳鄰居發(fā)來的能量信息分組。即節(jié)點可以知道k跳范圍鄰居的剩余能量信息。據(jù)此，使用某種排序算法，節(jié)點可以計算出自己的剩余能量次序，即自己在局部范圍節(jié)點按剩余能量從高到低的排名。節(jié)點每收到一個能量信息都會重新計算能量次序。
節(jié)點發(fā)送能量信息分組的間隔T可以由節(jié)點根據(jù)自己能量變化的速度動態(tài)決定，如果節(jié)點能量變化得慢就加大T，如果能量變化得快就縮短T。另外一種可供選擇的方式是當(dāng)本節(jié)點能量變化超過一定比例時，就觸發(fā)一次能量信息分組發(fā)布過程。至此，第一階段描述完成。第一階段進(jìn)程的執(zhí)行隨時間持續(xù)進(jìn)行下去，直到網(wǎng)絡(luò)任務(wù)終止。
在第二階段，利用第一階段獲得的能量信息，建立廣播樹。具體過程是首先，源節(jié)點向全網(wǎng)廣播一個"樹建立請求"分組。然后，當(dāng)網(wǎng)絡(luò)中一個節(jié)點x從其鄰居y收到一個"樹
建立請求"分組時，執(zhí)行以下操作
第一步如果X第一次收到這個分組，那么
第二步 節(jié)點x本地建立到源節(jié)點的逆向路徑
第三步 如果節(jié)點x尚沒有收聽到其它節(jié)點向y發(fā)送的關(guān)于此次廣播會話的確認(rèn)分組第四步 那么，x向y發(fā)送一個確認(rèn)(ACK)分組
第五步 如果x的剩余能量次序是最后n%,則延遲一段時間D + random(O， tl)，其中random(O， tl)返回0到tl之間的一個隨機(jī)數(shù)，D和tl是網(wǎng)絡(luò)參數(shù)，取值為正；
第六步 否則延遲random(0，tl);第七步 節(jié)點X在超時之后繼續(xù)向鄰居廣播該分組；
第八步否則丟棄該分組。
該方法中，第三至第四步確定了誰將是樹內(nèi)節(jié)點 一個收到發(fā)送給自己的確認(rèn)分組的節(jié)點，表明自己將是樹的內(nèi)部節(jié)點。如果一個節(jié)點廣播了數(shù)據(jù)請求分組后一段時間沒有收到確認(rèn)分組，就說明，自己是樹葉節(jié)點，將來不需要為其它節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)分組。
第五至第六步確定了節(jié)點繼續(xù)轉(zhuǎn)發(fā)"樹建立請求"分組的延遲時間，其中random(O， tl)是為了避免著名的廣播風(fēng)暴問題，D的引入則是故意延遲能量非常低的節(jié)點轉(zhuǎn)發(fā)"樹建立請求"分組的時間。
可以根據(jù)網(wǎng)絡(luò)應(yīng)用的需要動態(tài)調(diào)整n的取值，如11=10，表示節(jié)點剩余能量次序后10%的節(jié)點。D的取值應(yīng)應(yīng)遠(yuǎn)遠(yuǎn)大于tl的值，從而盡可能保證能量非常低的節(jié)點的鄰居節(jié)點應(yīng)能從其它路徑收到"樹建立請求"分組(如果存在其它路徑)，這樣就最大程度地避免了能量非常低的節(jié)點成為樹內(nèi)節(jié)點。
第二階段確定了網(wǎng)絡(luò)中哪些節(jié)點屬于樹內(nèi)節(jié)點。圖1示意這種方法生成樹的狀態(tài)，能量非常低的節(jié)點成為樹葉節(jié)點。
在第三階段，廣播信源按照第二階段建立的廣播樹，發(fā)送數(shù)據(jù)。每一個樹內(nèi)節(jié)點都將廣播數(shù)據(jù)分組，每一個收到廣播數(shù)據(jù)的節(jié)點檢査自己是否是樹內(nèi)節(jié)點，如果是，則繼續(xù)廣播分組，否則直接丟棄分組。
權(quán)利要求
1、基于樹狀結(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)能量高效廣播方法，其特征在于在無線傳感器網(wǎng)絡(luò)中，節(jié)點在局部范圍內(nèi)交換的能量信息，節(jié)點根據(jù)自己的能量在附近區(qū)域節(jié)點的次序作為構(gòu)造廣播樹的依據(jù)，低能量的節(jié)點以較低的改作被選為廣播樹的樹內(nèi)節(jié)點。
2、 根據(jù)權(quán)利要求1所述的無線傳感器網(wǎng)絡(luò)的能量高效廣播方法，其特征在于交換能量信息被限制在局部范圍。方法是每個節(jié)點廣播自己的能量信息，并限制一個廣播跳數(shù)k。這樣每個節(jié)點只能收到周圍k跳范圍的節(jié)點的能量信息。其中k的值應(yīng)遠(yuǎn)小于網(wǎng)絡(luò)半徑。并且k值大小應(yīng)事先指定。
3、 根據(jù)權(quán)利要求1所述的無線傳感器網(wǎng)絡(luò)的能量高效廣播方法，其特征在于節(jié)點根據(jù)自己的能量在附近區(qū)域節(jié)點的次序作為構(gòu)造廣播樹的依據(jù)，低能量的節(jié)點以較低的改作被選為廣播樹的樹內(nèi)節(jié)點。在構(gòu)建廣播樹的過程中，能量最低的11%的節(jié)點會延遲轉(zhuǎn)發(fā)數(shù)據(jù)請求分組，避免使自己作為樹內(nèi)節(jié)點，且可以根據(jù)網(wǎng)絡(luò)應(yīng)用的需要取n值。
全文摘要
本發(fā)明屬于無線傳感器網(wǎng)絡(luò)節(jié)能廣播路由領(lǐng)域。具體涉及一種在無線傳感器網(wǎng)絡(luò)中通過局部范圍內(nèi)相互交換節(jié)點能量信息的方法，通過該方法獲得局部范圍節(jié)點能量次序信息，并將其應(yīng)用到廣播樹構(gòu)造中去，達(dá)到均衡使用網(wǎng)絡(luò)節(jié)點能量、延長網(wǎng)絡(luò)生命的目標(biāo)。本發(fā)明的技術(shù)方案是在無線傳感器網(wǎng)絡(luò)中，節(jié)點在局部范圍內(nèi)交換的剩余能量信息，協(xié)議保護(hù)在局部區(qū)域能量最少的一定比例的節(jié)點(如能量最少的10％節(jié)點)，降低它們作為廣播樹的樹內(nèi)節(jié)點的概率，從而降低它們參與分組轉(zhuǎn)發(fā)的概率。
文檔編號H04L12/56GK101577664SQ20081010578
公開日2009年11月11日 申請日期2008年5月5日 優(yōu)先權(quán)日2008年5月5日
發(fā)明者鄭 姚, 鋒 張, 張寶賢, 壯 趙, 雪 高, 奎 黃 申請人:北京銀易通網(wǎng)絡(luò)科技有限公司