Ｍｅｓｈ無線網絡監測代理分配算法

摘 要：由于Mesh無線網絡的不穩定性，需要在網絡中設置監測代理幫助完成網絡的故障檢測。討論了如何分配最少節點的監測代理，以完成對整個網絡關鍵路徑的完整覆蓋。引入節點駐留權值的概念，對滿足要求的監測代理節點集合進行優化，以分配出最合理的網絡監測代理。對算法時間復雜度的分析證明該算法是可行的。

關鍵詞：Mesh無線網絡; 代理分配; 時間復雜度

中圖法分類號：TP301 文獻標識碼：A 文章編號：1001-3695(2006)10-0052-02

Network Inspection Agent Allocation Scheme in Mesh Wireless Network

DING Xuyang1，2， FAN Mingyu1，2， LUO Huiqiong1，3

(1.School of Computer Science Engineering; 2.Research Center of Information Security; 3.Laboratory of Network Information， University of Electronic Science Technology， Chengdu Sichuan 610054， China)

Abstract:Because of in stability in the Mesh wireless network， we need allocate agents to complete faults detection of the network. This paper investigates how to allocate the least inspection agents， and still cover all vital paths. The concept of stay weight is introduced. According to the weight to optimize the inspection agent set and allocate the most reasonable network inspection agents. The time complex analysis proves that this algorithm is feasible.

Key words:Mesh Wireless Network; Agent Allocation; Time Complexity

在Mesh無線網絡中，由于節點移動或物理鏈路失效引起的網絡故障時常發生。在網絡管理中，總希望故障管理中心能收到所有關于網絡故障的報告，以便分析和維護網絡。然而故障發生后，如何減少故障報告的遺失一直是網絡故障管理中的難點。通常，故障報告的遺失主要由三種情況引起：①故障傳送路徑中某個節點的不當操作而引起報告丟失，如該節點通信過于繁忙，以至于在收到報告后沒有時間轉發；當有能力轉發時，報告已過期而被丟棄。②故障傳送路徑中某節點不執行轉發操作引起報告丟失，如存在惡意的網絡破壞者。③故障傳送路由中的某條或某些路徑失效，使得故障報告因目的地不可達而被丟棄[1，2]。

在通信網絡中，為了盡量避免以上情況的發生，通常在網絡中設置監測代理用于監測網絡故障，并在監測到故障發生后，及時將故障報告傳送至故障管理中心，以便管理中心作出準確及時的響應。對于Mesh無線網絡，我們仍可以借鑒這一思想，并通過合理改進來管理和維護網絡。

理想狀態下，每一個節點均作為網絡的監測代理節點是最可靠的管理方式。但是，隨著網絡規模的增加，這樣的分配方式將消耗大量的網絡資源。因此，我們的研究重點在于如何合理地分配一個最小的網絡監測代理集合。

針對Mesh無線網絡結構時常改變的特性，提出了一種基于駐留權值的監測代理分配算法，該算法具有以下特點：①引入節點駐留信任機制，避免由于代理節點頻繁更替而產生的開銷；②該算法性能良好，其時間復雜度不會隨著網絡規模的擴大而呈指數增長。

1 Mesh無線網絡監測代理分配算法

1．1 條件和約束

我們參考文獻[3]SONET中使用的方法，約定當一個故障發生時，可能是由網絡中某個節點或者某條鏈接失效引起的，故障報告將會被發送給通過故障發生處的網絡路由的上行節點和下行節點，并由這些節點轉發。

為描述監測代理算法，我們作如下假設：①網絡拓撲結構如圖1所示，記為G(N，L)；②網絡中存在四條路由，它們分別為α∶abce，β∶abdg，γ∶dceh以及δ∶cegf。

1．2 監測代理分配

1．2．1 映射矩陣

根據以下規則構造網絡的映射矩陣：

（1）矩陣MNRn×r，描述路由路徑與節點之間的關系，n為網絡中的節點數，r為網絡中存在的路由數。若路由j經過節點i，則相應MNRn×r[i，j]的值為1，反之為0。例如，MNRn×r[α，β]的值為1，代表著路由β經過節點α。

(2)矩陣MRLr×l，描述路由路徑與節點間鏈接的關系，r為網絡中存在的路由數，l為節點間的鏈接數。若路由i經過路徑j，則相應MRLr×l[i，j]的值為1，反之為0。例如，MRLr×l[β，6]的值為1，代表著路由經過鏈接6。

MNRn×r=a

將矩陣MNRn×r與矩陣MRLr×l相乘，可以得到通過網絡中路由作為關聯反映出的節點與節點間鏈接的關系矩陣CNLn×l。

CNLn×l=MNRn×r×MRLr×l=a

1．2．2 代理分配表

根據以下規則構造分配代理表：

(1)刪除矩陣CNLn×l中所有列元素值為0的路徑，因為所有列元素為0說明沒有路由通過該路徑，從而即使該路徑異常，也不會影響網絡的正常，故不需要監測；

(2)對應的CNLn×l[i，j]≥1，對應表T[i，j]的值為X。例如，CNLn×l[b，1]=2≥1，故對應表T[b，1]=X。

1345689 1011T=a

根據表T所示的節點與路徑之間的關聯關系，我們可以得到最大鏈路覆蓋的最少節點的監測代理候選集合S={{a，c}，{b，c}，{d，c}，{a，e}，{b，e}，{d，e}，{c，g}，{e，g}}。

1．2．3 監測代理選擇

由于Mesh無線網絡節點在網絡中駐留時間不確定，因此我們希望找到的作為代理的節點是在該網絡范圍內相對駐留時間最長的，以便減少由于代理節點離開網絡而引起的重新尋找代理節點所需的開銷。因此，我們引入駐留因子Ti，Ti∈[0，1]。駐留因子Ti是在節點進入網絡時，由網絡接入控制中心根據節點情況分配給節點的駐留權值。該權值的計算可以參考文獻[5]提到的方法，計算公式如下：

Ti=Wi(r，l，t)（1）

且wi(r，l，t)∈[0，1]。式中，wi(r，l，t)由三個參數確定：r為節點在網絡中承擔的角色參數；l為節點在網絡中的位置參數；t為節點與接入控制中心所協商的駐留時間參數。

假設通過公式計算所得到的節點駐留權值分別為：Ta=0．9，Tb=0．5，Tc=0．8，Td=0．7，Te=0．6，Tf=0．8，Tg=0．3和Th=0．7。根據代理候選集合和節點駐留權值的綜合考慮，選取{a，c}作為監測代理集合，也即選取節點a和節點c作為網絡的監測代理，且該監測代理集合具有最好的穩定性。

2 算法時間復雜度分析

假定存在網絡G(N，L，R)，其中N為網絡中的節點數，L為鏈路數，R為路由數。假設運算一次乘法所需時間為α，而運算一次加法所需時間為β，則按照式（1）的監測代理算法，對于網絡G(N，L，R)中監測代理的候選集合尋找共需用時：

T=N×[L×[R×α+(R-1)×β]]（2）

由式（2）可知，算法的時間復雜度o≤o(n3)，n=max(N，L，R)。因此，該算法是一個結構良好的算法。

3 結論

網絡監測代理的分配對網絡管理和維護是非常重要的，本文主要研究并給出了基于節點駐留權值的Mesh無線網絡監測代理分配算法，該算法能有效地尋找到覆蓋關鍵鏈接路徑的最小監測代理候選集合，且根據節點駐留權值選取出網絡中穩定性最優的監測代理節點，具有較小的時間復雜度。分析結果表明，該算法能有效地為Mesh無線網絡尋找和分配監測代理。

參考文獻：

[1]Minseok Oh. Network Management Agent Allocation Scheme in Mesh Network[J]. IEEE Communications Letters， 2003，7(12):601-603.

[2]S Bibas， M O Cordier， PDague， et al. Alarm Driven Supervision for Telecommunication Network:I——Offlinescenarios Generation[J]. Ann. Telecommun.， 1996，51(9):493-500.

[3]T H Wu. Fiber Network Service Survivability Reading[M]. MA: Artech House， 1992.

[4]Z Kohavi.Switching and Finite Automata Theory(2nd ed.)[M]. New York: McGrawHill， 1978.

[5]A AbdulRahman， S Hailes. A Distributed Trust Model[C]. Proc.of New Security Paradigms Workshop， 1997.48-60.

[6]R Perlman. An Overview of PTI Trust Model[Z]. IEEE Networt， 1999.

[7]YuChee Tseng， WenHua Liao， ShihLin Wu. Mobile Ad hoc Networks and Routing Protocols[R]. Handbook of Wireless Networks and Mobile Computing， 2002.371-392.

[8]Asad Amir Pirzada， Chris McDonald. Establishing Trust in Pure Ad hoc Networks[C]. Proceedings of the 27th Conference on Australasian Computer Science， 2004.47-54.

[9]AGanz， Q Xue. QoS Routing in Meshbased Wireless Networks[J]. International Journal of Wireless Information Networks， 2002，9(3):179-190.

[10]洪帆，高見元.Ad hoc網中的安全問題[J].網絡安全技術與應用，2005，51(2):54-56.

作者簡介：

丁旭陽（1981-），男，貴州遵義人，博士，主要研究方向為網絡通信、網絡信息安全；范明鈺（1962-），女，四川成都人，教授，博導，主要研究方向為信息安全；羅惠瓊（1955-），女，四川成都人，教授，主要研究方向為網絡通信。

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文