[發明專利]一種基于虛擬斯特納樹的組播隨機化路由方法

無效

• 申請號: 200710177293.0
• 申請日: 2007-11-14
• 公開（公告）號: CN101175042A
• 公開（公告）日: 2008-05-07
• 發明（設計）人: 周賢偉;楊揚;王建萍;賈東耀;王麗娜;楊裕亮;安建偉
• 申請（專利權）人: 北京科技大學
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04L12/18
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域：

本發明涉及一種無線傳感器網絡組播路由方法，通過該方法均衡網絡能量，也增加了組播樹的魯棒性，延長網絡的生命周期。

背景技術：

目前實現組播路由最普遍的方法是構造源節點到一組目的節點的樹形路由結構，信息可以沿著這棵樹決定的路徑進行發送，減少了信息傳遞的延時，而且信息復制僅在樹權處進行，可以節省網絡帶寬資源。

基于樹的路由協議中最核心的問題是斯特納(steiner)樹問題。steiner樹問題是指連接給定點的最小樹長問題，其最優解稱為steiner最小樹(Steiner?Minimum?Tree，SMT)。圖論中對steiner問題的研究可以追蹤到1961年，Karp等在1972年證明了最小steiner樹問題是NP完全問題。啟發式算法雖然在絕大多數的情況下都不能得到最優steiner樹，但它們能夠在較短的時間內找到費用接近最優的準steiner樹，因此它們在路由網絡費用優化中更有實際意義。到目前為止，還沒有一種啟發式算法的最差情況下的性能與最佳解性能之比好于兩倍。

Shibo?Wu，K.Selcuk?Candan在Proceedings?of?the?26th?IEEE?International?Conference?onDistributed?Computing?Systems(ICDCS’06)中提出了一種基于虛擬steiner樹的組播路由方法。該方法也是一種啟發式算法。其基本思想是首先利用如下原理：如果只有三個節點，也就是一個源節點，兩個組播節點，那么這三個節點的steiner點能被有效地計算出來，給定一個目的節點組(u，v)和源節點s，縮率表示為RR(s，u，v)，是這樣定義的：

RR(s,u,v)=1-d(s,t)+d(t,v)+d(t,v)d(s,u)+d(s,v)---(1-1)]]>

算法在每次循環中，確定一個最大縮率值的組，再分別把該組steiner節點和組播節點的連接加入到steiner樹，steiner節點被激活。循環過程中，如果steiner節點和組播節點組中的某一點重合，則連接另一點和steiner節點加入steiner樹，該重合組播節點被激活；如果steiner節點和源節點重合，則源節點和兩組播節點的連線都被加入Steiner樹中，最后形成虛擬Steiner樹，按照該虛擬steiner樹形成的相反的順序形成目的節點序列。路由建立過程中，源節點按照目的節點序列中的順序發送目的節點序列的信息。該序列中每個steiner節點(可以是組播節點，也可以是其它節點或虛擬節點)與與其結組的組播節點屬于同一代，是該組形成的steiner節點的下一代。節點收到路由建立數據包后，提取目的節點序列信息。如果下一代在當前節點的發射距離范圍內，則直接轉發到該下一代，如果沒有在其發射距離范圍內，則在其鄰居節點中找出距離該下一代距離最近的節點作為轉發節點。如果下一代為虛擬Steiner點，則發送到該虛擬Steiner節點的發射范圍內即可。