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

在審

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

技術領域

本發明涉及網絡拓撲控制技術領域，具體涉及一種M2M網絡拓撲控制方法及系統。

背景技術

物聯網能使世界上的所有物體實現網絡互聯、交流信息，具有廣泛的應用價值和巨大的發展潛力，是當前世界新一輪經濟和科技發展的戰略制高點之一。近年來，隨著連入網絡的設備數量正以爆炸性的速度進行增長，其主要網絡形式從用戶到用戶、用戶到設備網絡逐步過渡到Machine-to-machine（M2M）網絡。根據Cisco的預測，2015年連入網絡的設備節點的數量將超過150億，是當前移動設備和因特網用戶總和的3倍以上。然而由于接入M2M網絡的設備節點類型具有多樣性（譬如，對于一個典型的家庭M2M網絡來說，可能包含了智能儀表、開關、打印機、生物醫學傳感器和其它類型的用于環境感知的傳感器等），使得M2M網絡具有許多復雜特征，如多樣的服務需求，較大的網絡規模和極低的能耗需求等。

拓撲控制是自組織網絡中的關鍵技術之一，在不影響網絡性能和服務質量的前提下，它能有效簡化網絡連接，提高網絡容量，減低網絡能量消耗和延長網絡的生命周期。與常規的自組織網絡不同的是，M2M中的拓撲控制要求在同一網絡中提供到網絡SINK節點的多種連通服務。舉例來說，在一個家庭M2M網絡中，生物醫學傳感器收集醫療關鍵信息。與一般的網絡收集數據相比，如智能儀表的測量數據，這種醫療數據要求更高的傳輸可靠性以保障待測人員身體狀況突變時，能得到及時有效的處理。另外，與傳統自組織網絡不同的是，連接到該網絡的設備節點可能具有不同的接口和數據標準，這將導致類型相異的設備節點不能識別來自于其它節點的數據，譬如智能儀表的數據與多媒體設備的視頻數據具有完全不同的數據格式，這就意味著設備之間的數據通信和數據分享可能需要具有強大功能的SINK節點（或稱為網關節點）進行翻譯和處理，以簡化設備節點。考慮到以上因素，M2M網絡中的傳輸可靠性可定義為到SINK節點的網絡連通度，即到SINK節點不相交傳輸路徑的數量，設備節點不同層次的傳輸可靠性需求通過提供數量不等的網絡傳輸路徑來實現。已有的移動自組織網絡和傳感器網絡拓撲控制理論和方法不能滿足M2M網絡的異構連通需求，迫切需要探索新的M2M網絡拓撲控制的理論、方法和技術。

目前面向M2M網絡異構連通需求的拓撲控制技術存在的主要問題有：（1）當前較少研究工作涉及到這個問題，并且均屬于屬于集中式算法，其中絕大部分對應著極高的時間復雜度，僅適用于小規模的網絡；而另一部分在網絡存在著可行解的情況下，通過初步的仿真實驗表明，實現K連通度的節點比例較少，即成功率較低，甚至在有些情況下，獲得的成功率低于隨機連接算法。（2）如何聯合解決設備節點的異構連通需求問題，目前也缺乏有效的解決方案，這將導致M2M網絡難以有效為不同節點提供個性化的連通服務，限制了M2M網絡的發展。

因此，急需研究時間復雜度低、能適用于實際規模網絡的集中式解決方案，以解決靜態M2M網絡的拓撲控制問題。此外，對于拓撲變化頻繁的情況下，如何設計分布式算法，以動態調整網絡拓撲、滿足網絡中設備的連通需求，對于大規模應用M2M網絡，更具有重要的理論研究意義和實際的應用價值。

發明內容

本發明提出了一種新的拓撲控制算法，用于解決M2M網絡中問題。一個M2M網絡中，有兩種類型的數據，分別是超級節點和普通節點。超級節點是需要k度連接的（其中K是正整數），而普通節點只需要1度連接。很顯然，k節點容錯拓撲控制問題在常見的ad-hoc網絡中是一個特例，所有在這個網絡中的節點都是超級節點。模擬結果表明，這種算法在稀疏的網絡中能保證超級節點和普通節點雙方的連接性。在現有的文獻中，這是開創性的工作，它能為M2M網絡解決拓撲控制問題，有效為不同節點提供個性化的連通服務。

本發明的技術方案如下所述。

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

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

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

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

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

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

其中：k是正整數。

所述的將M2M網絡原始無向圖轉換為有向圖，其轉換步驟如下：