[發明專利]M2M網絡拓撲控制方法及系統

在審

• 申請號: 201310493141.7
• 申請日: 2013-10-21
• 公開（公告）號: CN104065580A
• 公開（公告）日: 2014-09-24
• 發明（設計）人: 李小龍;彭鵬程;劉洋;劉建明
• 申請（專利權）人: 桂林電子科技大學
• 主分類號: H04L12/751
• 分類號: H04L12/751;H04L12/753
• 代理公司: 桂林市華杰專利商標事務所有限責任公司 45112
• 代理人: 劉梅芳

1.一種M2M網絡拓撲控制方法，所述控制方法包括：

對M2M網絡應用最小生成樹算法，得到第一個路徑集合，并對得到的最小生成樹進行初始化操作，以節點的所有鏈路中具有最大能量消耗的路徑作為該節點傳輸能力的初始化數值；

將M2M網絡無向圖轉換為有向圖；

對有向圖使用最大流算法，并且記錄每一個超級節點到sink節點的節點不相關路徑；

應用貪心策略對每個超級節點進行k輪掃描，每一輪掃描選出一條額外能量消耗最少的路徑，并進行記錄，得到第二個路徑集合；

合并第一個路徑集合中的路徑和第二個路徑集合的路徑，構造出新的網絡拓撲圖；

其中：k是正整數。

2.根據權利要求1所述的方法，其中所述的最小生成樹算法采用快速接近算法。

3.根據權利要求1所述的方法，其中所述的將M2M網絡原始無向圖轉換為有向圖，其轉換步驟如下：

(1)對于每個節點υ∈V/{t}，我們用υ_in和υ_out兩個節點代替，它們用一條有向邊<υ_in，υ_out>連接；

(2)對于每條無向邊(u，υ)，υ∈V/{t}我們用兩條有向邊<u_out，υ_in>和<υ_out，u_in>代替。若v=t那么我們則用一條有向邊<u_out，t>代替邊(u，v);

（3）設定每一條邊的容量都是1；

(4)對所有的邊<u_out，t>，它們的權重為零，而對于在圖中的其他邊，它們相關的權重值用下式計算：

ωu,υ=|min{0,pu-q(ru,υ)}|+|min{0,pυ-q(ru,υ)}|;]]>

其中：ru,v代表在節點u和v之間的歐里幾德距離，q是預定義的能量消耗，pu和pυ分別代表節點u和v當前的功率分配。

4.根據權利要求1所述的方法，其中所述的最大流算法采用ford-fulkerson算法。

5.根據權利要求1所述的方法，其中所述的貪心策略是貪婪最小額外能量消耗路徑選擇算法。

6.一種M2M網絡拓撲控制系統，包括：

對M2M網絡應用最小生成樹算法，得到第一個路徑集合，并對得到的最小生成樹進行初始化操作，以節點的所有鏈路中具有最大能量消耗的路徑作為該節點傳輸能力的初始化數值的裝置；

將M2M網絡無向圖轉換為有向圖的裝置；

對有向圖使用最大流算法，并且記錄每一個超級節點到sink節點的節點不相關路徑的裝置；

應用貪心策略對每個超級節點進行k輪掃描，每一輪掃描選出一條額外能量消耗最少的路徑，并進行記錄，得到第二個路徑集合的裝置；

合并第一個路徑集合中的路徑和第二個路徑集合的路徑，構造出新的網絡拓撲圖的裝置；

其中：k是正整數。