[發明專利]基于MCDS近似算法的最小化資源消耗的組播路由方法

有效

• 申請號: 200910058410.0
• 申請日: 2009-02-20
• 公開（公告）號: CN101562780A
• 公開（公告）日: 2009-10-21
• 發明（設計）人: 林大澤;周賢偉;張永德;彭萊;吳敏;李永芳;汪林
• 申請（專利權）人: 西部礦業股份有限公司
• 主分類號: H04W4/06
• 分類號: H04W4/06;H04W8/08;H04W40/04;H04W84/18
• 代理公司: 西寧金語專利代理事務所
• 代理人: 哈慶華

1.一種基于MCDS近似算法的最小化資源消耗的組播路由方法，其特征在于：所述的方法基于已建立好的組播樹找到一個最大獨立集MIS，然后找到支配集節點連接所有的MIS節點，得到一棵支配組播樹，所述方法包括如下步驟：

1)構造MIS

在組播樹T上，樹中節點的級別level為該節點距離樹根的跳數；樹根的級別為0；我們定義節點的rank為二元組(level，id)；

IF?levelv＞levelu?THEN?rankv＞ranku，OR

IF?levelv＝levelu?AND?IDv＞IDu?THEN?rankv＞ranku

每個節點的id在樹T中具有唯一性，所以樹中節點有一確定的排序；算法初始化過程，每個節點先計算自己的等級和低等級的鄰居節點的個數，并存儲這兩個值；每一節點保持兩個本地感知變量x1和x2；變量x1記錄鄰居節點中級別還沒有確定的節點個數，它的初始值為節點所有鄰居節點個數；變量x2記錄了節點還未完成執行步驟的子節點的個數，它的初始值為所有子節點個數；所有節點保存一個LevelList變量，記錄了鄰居節點的級別，初始化為空；還有一個本地變量y，它記錄了低等級鄰居節點的個數；初始化開始時，根節點廣播帶有他的級別為0信息的level消息；當接收到一個level消息，節點將包含發送節點id和級別的條目添加到自己LeveList變量中去，然后將x1減1；如果發送者是它在樹T中的父節點，它將自己的級別設置為發送者的級別加1，然后通過level消息廣播自己的級別；當x1＝0時，節點設置y為它的低等級鄰居節點的個數，該值通過計算LeveList中的信息得到；如果該節點是葉節點，即它的變量x2初始化為0，并且它的級別已經決定，它發送一個LEVELCOMPLETE消息給它的父節點，當接收到LEVELCOMPLETE消息后，節點將它的x2變量減1；如果節點經過更新后的變量x2＝0，而且它不是根節點，它將發送LEVELCOMPLETE消息給它的父節點，然后重新設置x2變量為其子節點個數；到此為止，所有節點都確定了各自的等級和它們鄰居的等級，接下來根節點將用顏色標識的方法構建MIS；

所有節點最初都標識為白色節點，而在該階段結束時，它們最終將標識為灰色或是黑色；每一個節點保存一個BlackNum變量；在基于UDG模型下，BlackNum至多為5；根節點首先將自己標識為黑色，然后廣播BLACK消息，當接收到BLACK消息后，節點將BlackNum加1，如果它的顏色為白色，它將標識自己為灰，然后廣播GRAY消息，此消息中包含它的level信息；白節點接收到GRAY消息，如果發送者的等級低于它的等級，將其y值減1；如果更新后的y值為0，它將標識自己為黑色節點，然后廣播一個BLACK消息；當一個葉節點被標識，它將發送MARKCOMPLETE消息給其父節點；當一個節點接收到MARKCOMPLETE消息后，它將自己的x2變量減1；如果更新后其x2＝0，而且它不是根節點，它將發送一個MARKCOMPLETE消息給其父節點；當根節點的本地變量x2＝0后，所有節點都已經被標識為黑色或是灰色，然后根節點將進入支配樹的構造階；

2)構造支配樹

構造一棵支配樹T*，算法結束后被標識為黑的節點集，即近似MCDS。初始化每個黑節點有一個Connect變量，將記錄它的連接節點id，Degree變量記錄連接節點的鄰居黑節點的個數，初始化為0，x1初始化為鄰居節點個數，x2記錄節點的子節點個數，初始化為0；步驟如下：

(a)先由已經被標識為黑的根節點開始廣播一個CONNCET消息，未確定灰節點每收到一個CONNCET消息將BlackNum變量的值減1，回復CONNECTREP消息給CONNCET的發送者，CONNECTREP消息中有灰節點的鄰居未遍歷黑節點個數，即BlackNum變量值；根節點每接收到一個CONNECTREP消息，x1變量減1，比較CONNECTREP消息中發送者黑色鄰居節點的個數和自己的Degree變量的大小，如果前者大，就以該值來更新Degree變量，并將Connect變量更新為該發送者的id；

(b)如果根節點經過更新后x1＝0，發送CONNECT-CONFIRM消息給變量Connect中存儲的id的節點，重置x1值為節點的度；接收到CONNECT-CONFIRM消息的灰節點成為樹T*的根節點，標識為黑，將自己的狀態更新為已確定，并廣播BLACK-COMFIRM消息；

(c)CONNECT節點的所有未遍歷黑色鄰居節點接收到BLACKCONFIRM消息后將發送者標記為自己的父節點，x1值減1，將自己的狀態更新為已遍歷，并重復上述樹T*的根節點的步驟，只是黑節點每接收到一個CONNECTREP消息，在x1變量減1的同時將x2變量加1，接收到CONNECTCONFIRM消息的灰節點應該成為轉發節點而不是樹T*的根節點，并將發送者標識為自己的父節點；所以當灰節點的BlackList變量值為0時，記錄發送CONNCET消息節點的id號，并將其標記為自己的父節點，把自己的狀態更新為已確定，說明它的所有鄰居黑節點已遍歷；當黑節點廣播CONNCET消息后收不到任何回復時，說明它的所有鄰居灰節點已確定；

(d)已確定的灰節點發送DONE消息給它的父節點；無BlackNum變量的黑節點每接收到一個DONE消息將變量x2減1，節點變量x2＝0時，發送DONE消息給它的父節點；存有BlackNum變量的黑節點每收到一個DONE消息將它的BlackNum變量值減1，直到BlackNum＝0發送DONE消息給它的父節點；當樹T*根節點收到DONE消息，該算法結束。