[發明專利]無線自組織網絡中基于協同感知的組播路由方法

無效

• 申請號: 201010034078.7
• 申請日: 2010-01-14
• 公開（公告）號: CN101815336A
• 公開（公告）日: 2010-08-25
• 發明（設計）人: 周賢偉;林琳;王超;劉濤;杜利平;吳華怡
• 申請（專利權）人: 北京科技大學
• 主分類號: H04W40/02
• 分類號: H04W40/02
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于協同感知的無線自組織網絡組播路由方法，其特征在于：路由方法包括初始化過程、廣播建樹過程、剪枝過程、優化過程四個步驟；首先給出如下的規則和定義：

a、節點的標號規則

源節點S，標為1；

上游節點不是Steiner點的目的節點，標為2，記為2-節點；

上游節點是Steiner點的目的節點，標為3，記為3-節點；

Steiner點，標為4，記為4-節點.

b、對節點的定義

用(W_i，ζ_i)來標識組播樹中的節點i，其中v是一個5元組，ζ_i包含5個集合，

(b1)W_i＝(I_i，II_i，III_i，IV_i，V_i)

I_i：節點i的id號；

II_i：節點i的上游節點的id號；

III_i：節點i在當前組播樹中的層次；

IV_i：節點i在當前組播樹中的反向層次；

V_i：節點i的標號；

(b2)ζ_i＝(A_i，B_i，C_i，F_i，L_i)

A_i＝{id|節點i的鄰居節點，且標號為2或3}

B_i＝{id|節點i的鄰居節點但非上游節點，且標號為4}

C_i＝{id|節點i，節點i的上游節點，節點i的廣義下游節點，與節點i有相同的上游節點的節點及其廣義下游節點}

F_i＝{id|由于時延約束，節點i不能與之成為組播樹中的鄰居節點}

其中節點i的上游節點是指從源節點經過該上游節點單跳到達節點i，節點i的下游節點是指從源節點經過節點i單跳到達的節點，節點i的廣義下游節點是指從源節點經過節點i到達的節點，節點i的廣義下游節點集合記為L(i)，C_i和F_i被稱為節點i的禁用集合，節點i不能選擇它們作為在組播樹中的鄰接節點，禁用前者是為了避免出現環路，禁用后者是為了滿足時延約束；

c、對協同包的定義

在建樹以及優化過程中，改變組播樹結構的信息需要通過節點間的協同來獲取，在此定義協同包的格式及作用：

節點i的協同廣播包：(I_i，II_i，III_i，IV_i，C_i，F_i，V_i)，各符號的意義同上，用來通知鄰居節點有關節點i的信息；

局部協同確認包：確認自己和當前上游節點解除關聯關系；

局部協同否定包：確認自己不能和當前上游節點解除關聯關系；

A、初始化過程：對網絡中的每個節點v，設置A(v)、B(v)、L(v)和F(v)為空集，設置C(v)＝{v}，設置R為空集，設置d＝0，d為節點在組播樹上的層次；

B、廣播建樹過程：

(B1)網絡中的源節點S向鄰居節點發送協同廣播包，協同廣播包中具體信息為(I_S，--，1，--，{S}，1)，其鄰居節點ω收到協同廣播包后，同時向自己的鄰居節點發送協同廣播包，協同廣播包中具體信息為(I_ω，S，2，--，ω，2)，設置d＝2，此時組播樹已經構造了兩層；

(B2)若網絡中所有節點都有了自己的標號，轉(B4)；否則網絡中的任一沒有標號的節點i，在收到上層鄰居節點的協同廣播包后，選擇一個標號最小的節點作為自己的上游節點，若有多個，選擇id號最小的；根據自己選擇的上游節點的協同廣播包里的信息來計算自己的信息，其中標號按照標號規則進行選擇；d＝d+1；如果節點i選擇的上游節點標號為4，則節點i還要根據定義更新自己的兩個集合A_i和B_i；如果節點i選擇的上游節點標號不為4，則不更新自己的兩個集合A_i和B_i；

(B3)若d-1＝Δ，其中Δ是一個根據應用環境預先給定的時延上限，轉(B4)；否則，節點i向鄰居發送協同廣播包，轉(B2)；

(B4)若有某目的節點沒有收到協同廣播包，則它向鄰居廣播報警信息：滿足時延約束的組播樹不存在，算法結束；若沒有報警，則說明這個有向樹是以源節點S為根，覆蓋目的節點集合D的一棵樹，并且樹中源節點到每個目的節點的時延不超過時延上限Δ；

C、剪枝過程：對上面廣播建立的樹進行剪枝，就是將組播樹上的4-節點樹葉從組播樹上剪掉，將剪枝后的得到的組播樹記為T，記樹T中最底層的節點在樹T中的層次為max，則max就是樹的層數；樹T的最底層的節點將自己的反層次記為1，其中節點在組播樹中的反層次為x表示該節點在組播樹的倒數第x層上，然后它們將max在樹中進行廣播，樹T中的任一節點e收到廣播后將自己在組播樹的反層次IV_e更新為max-IV_e+1；

D、優化過程：

(D1)從樹T的最底層開始，按照反層次從小到大的順序，樹T中的節點i向鄰居節點發送協同廣播包，上游節點h在收到協同廣播包后，更新自己的禁用集合C_h為C_h?∪C_i，并將新的C_h發送給i，i更新自己的禁用集合C_i為C_h，節點i的其它的非上游鄰居節點j在收到廣播包后計算，若III_j+IV_i＞Δ+1，則通知節點i更新其禁用集合F_i為F_i∪{j}；

(D2)若除了R中的節點，樹T中沒有4-節點，則當前組播樹T就是滿足時延約束的Steiner樹；否則，若除了R中的節點，樹T中仍有4-節點，則對其中任一4-節點k，它通知自己的下游節點進行判斷：

若k的下游節點i沒有除k以外的其它上游節點選擇，則節點i回復k一個協同否定包；否則，回復k一個協同確認包；

若k沒有收到所有下游節點的協同確認包，轉到(D3)；否則，k將其下游節點的集合L(k)發送給L(k)中的所有節點并通知它們離開，節點k作為組播樹的一個Steiner點，宣布脫離組播樹，組播樹T更新為T-{k}；

k的每個下游節點i在收到k通知它離開的信息之后，若節點i選擇其它標號為2或3的節點作為它新的上游節點，則在這些可選擇的新上游節點中選擇任意一個節點j，在網絡中進行廣播，廣播的目的是：通知節點j與之建立鄰接關系，通知其它鄰居節點將L(k)中的節點加入它們的禁用集合中；

若節點i只能選擇其它標號為4的節點作為它新的上游節點，則在這些可選擇的新上游節點中任意選擇一個節點j，在網絡中進行廣播，廣播的目的是：通知節點j與之建立鄰接關系，通知其它鄰居節點將k的所有下游節點加入它們的禁用集合中，并通過節點j的回復，將自己的禁用集合C_i更新為C_j-{II_j}；

(D3)R＝R∪{k}，轉(D2)。