無線Mesh網網關節點動態選舉算法研究

鄒蕾

（吉林警察學院 信息工程系，吉林 長春 130000）

無線Mesh網網關節點動態選舉算法研究

鄒蕾

（吉林警察學院 信息工程系，吉林 長春 130000）

本文對無線Mesh網絡的網關節點選舉進行了分析研究.通過對無線Mesh網絡結構的研究提出一種網關節點選舉算法.該算法采用路由的機制確定了尋徑結果.整個過程由三個部分組成：可用網關節點的發現、最優網關的選舉、網關的維護.實驗表明該算法具有優化、簡潔、快速收簽以及靈活的特性.

無線Mesh網；Ad Hoc網絡；路由協議；網關選取

1 引言

無線Mesh網是Ad Hoc網絡的一種特殊形態，通過802.11、802.16、20.3G等技術組合成多跳無線鏈路的無線Mesh.無線Mesh可對系統大面積無限覆蓋，并且無線Mesh網絡也對無限系統提供了高的可靠性和大容量的帶寬.未來無線Mesh是一種先進的無線技術.傳統的網絡和無線Mesh網絡是完全不同的網絡.Mesh網絡的核心思想是:INTERNET的架構采用無線Mesh網絡設計的，在INTERNET網絡中，用戶位置主要在網絡邊緣，網絡連接方式采用節點和路由器相連接，如果不同節點在鏈路失敗后，路由器會采用通過其他路由的去尋找新的替代路徑.

Mesh終端的設備一般采用手機，電腦和PAD等.每個不同的終端進行相互訪問和連接構成P2P網絡.無線Mesh網作為一種新型寬帶無線接入技術備受學術界關注，逐漸成為下一代WMN的核心.

WMN的核心技術提供給通過無線技術提供給用連接無線網絡.移動終端用戶接入無線接入服務，當移動終端節點通過無線Mesh網接入Internet時，在無線Mesh網中需要找到可用的無線網關節點為其提供接入Mesh網絡的服務，所以如何選取網關節點一直是該領域研究的關鍵問題.

2 無線Mesh網網關節點動態選舉算法的設計與實現

這里設計用于無線Mesh網的網關節點動態選舉算法，主要是采用共同的思路——訪問網關.提出一種優化的網關選取算法.

根據無線Mesh網的有關特性，將網關節點動態選舉算法的過程應該分為三個階段:(1)可用網關節點的發現.(2)最優網關的選舉.(3)網關的維護.

2.1 可用網關節點的發現

2.1.1 算法需要維護的數據結構

1.算法的概念描述與定義

(1)協議圖G(V1,PV,E1,PE):通過G(V1,E1)在路由協議中表達網絡拓撲結構.其中，節點集合用V1表示，V1在網絡中表示網絡接入點，邊集合用EI表示，EI是無線鏈路，在網絡的實際應用中，鏈路，節點之間在不同的環境總會出現失效，所以為了滿足實際的需求，在協議圖G中給邊，節點賦概率值，形成協議圖G.

（1）路徑的可靠度，在協議圖G中，目的和源節點通常采用單路徑傳輸，邊與節點之間乘積定義為單路徑可靠度.

(2)傳輸路徑:目的，源點之間進行傳輸的通信鏈路.

(3)路由耗時:到達傳輸路徑一共消耗的時間.每項指標相加得到最后的耗時時間.

(4)路徑軌跡:網絡傳輸中記錄的節點序號.

(5)傳輸時間數組:在路徑的傳輸過程中，開始從節點I出發，到節點J為止，然后通過節點J 進行轉發，最后得到的時間.

2.節點的數據結構設計

表1 節點結構

根據無線Mesh網的特性和結構，在本算法中模擬一個無線Mesh網絡的節點結構.假設節點是作用在一個30×30范圍的區域以內,設定在這個區域內一共有10個網絡節點（節點用字符0、1、2、3、4、5、6、7、8、9表示），其中有8個網絡節點被設定為移動節點（移動節點用字符0、1、2、3、4、5、6、7表示）和2個網絡節點被設定為網關節點（節點用字符8、9表示）.移動節點具有移動性，它是可以任意移動的，它的移動范圍是在30×30范圍的區域之內；網關節點不具有移動性，它是以固定位置與無線Mesh網絡中的骨干網相連，為了區別網絡中的每個節點.節點所具有的結構如表1所示.

(1)節點位置:由于在WMN中具有GPS獨立定位功能的只有MESH網絡.該定位系統的誤差在1秒鐘之內不超過10米.為了在本文設定的30×30范圍的區域以內精確的表示出節點的位置，用兩個變量表示每個節點的坐標位置.

(2)網關標志位:網關標志位是用于節點是否是網關節點的.在無線Mesh網中，網關節點是以有線的方式與無線Mesh網的骨干網相連的，為了表示這個特殊的節點，用變量GW表示，當GW=1時證明該網絡節點為網關節點.

3.路由請求消息列表

無線Mesh網中當移動節點為了尋找可用的網關節點而發起路由時，首先發送一個探測包，其中主要包括的就是RREQ（路由請求消息），該探測包的結構如表2所示:

表2 路由請求消息

(1)源節點標識符:源節點標識符由字符0～9表示，代表每個節點的名稱.

(2)源節點地址:由節點位置（x，y）表示.

(3)網關節點標志:由于源節點要探測的是網關，由網關標志位（GW）表示.

(4)請求序列號:用于標識路由請求消息列表，由整數表示.

(5)發起的請求時間:源節點發起路由請求消息的起始時間.

4.路由表

無線Mesh網中每個節點的信息保存在路由表中，路由信息通過節點來保存.如果在路由器中發現新鏈路時，要把發現的新信息加入.通過路由算法實現分組發送找到路徑.路由通過可節點的存儲方式，可采用直接存儲路由方式，路由表的結構如表3所示:

(1)源節點標識符:源節點標識符由字符0～9表示，代表每個節點的名稱.

(2)源節點地址:由節點位置（x，y）表示.

(3)網關節點標志:由于源節點要探測的是網關，由網關標志位（GW）表示.

(4)請求序列號:用于標識路由請求消息列表，由整數表示.

(5)發起的請求時間:源節點發起路由請求消息的起始時間.

(6)終止請求時間:源節點發起路由請求后終止的時間.

(7)中間節點:每條路徑中源節點與目標節點間接相連的節點，按順序存儲.

2.1.2 網關節點的發現過程

在本文中模擬10個節點的無線Mesh網絡結構圖1如下所示:

圖1 模擬的無線Mesh網結構圖

圖2是自由無線Mesh網結構，用戶節點，GW，SGW節點都是無線終端.在網關節點發現過程中，通過一個網關實現用戶連接INTERNET網，若用戶不在網關的范圍內，網絡會自動失效，客戶需求重新選擇一個網關連接INTERNET網.

在介紹移動節點探測之前先做如下假設:系統中各節點都執行同樣的路由選擇算法,初始化網絡中各節點的路由表中路由大小初始值設為0.假設節點SRC_node為連接請求的源節點，連接請求的目的節點是網關.

第一階段，SRC_node連接上網絡.源節點SRC_node要向Internet發送數據時，它首先通過廣播發送本地路由請求信息RREQ分組，每個節點發送RREQ分組都有一定的范圍，這個范圍由節點本身的探測器所決定，假定這個探測范圍是一個定值，由表示.當SRC_node發送RREQ分組時后，在SRC_node節點為圓心以這個定值為半徑的范圍內，所有相鄰節點都可以接到這個RREQ包.RREQ中包含以下信息:目標網關標志位等.

第二階段，在探測距離范圍內的相鄰節點收到RREQ分組后，會選行判斷自己的是不是網關節點，如果它不是網關節點，則會變成路徑的中間節點，并且進行以下操作，通過軌跡數組記錄節點標識；中間節點再重復第一階段的內容以自己為圓心在探測范圍內再次進行發送，查找網關節點.倘若在探測距離的范圍內都沒有其它的節點存在或RREQ這個消息丟失了，則源節點SRC_node沒有發現到網關節點的路徑，它會重新返回斷開狀態并重新發送路由請求信息.

第三階段，當網關節點GW收到來自源節點SRC_node的RREQ分組后，根本自身的網關標志位GW進行判斷，證明自己就是源節點想要找到的網關，實現就路由請求.

第四階段，網關把相關信息進行封裝，然后進行路由分組，主要包含，網關點地址，源序列號，路由耗時等.封裝后，沿著原始傳給源節點.

圖2描述了上面討論的路由發現的機制.

圖2 路由發現機制

當路由器內部表發生改變，會及時把修改的狀態通知相連接的路由器，保證了數據傳輸.如圖3所示節點路由過程

圖3 路由發現過程

2.2 最優網關的選舉

通過上面的網關發現過程我們可以發現，源節點SRC_node收到從可用網關節點返回的RREP分組信息，即從當前的無線網絡中找到可達的網關節點的路由信息，因為無線Mesh網絡結構的復雜性以及網關節點可能會不止一個，所以在路由發現過程中所找到的可用路由信息和網關節點也可能會出現多個.由于網關的選舉機制最終僅僅允許每個移動節點只能選擇一個可用網關，所以就必須從這些可用的路由包中進行網關的選取.網關尋找過程中，節點收到從可用網關節點返回的應答信息RREP中查詢到每個可用網關節點的參數信息，將這些參數信息按照在網關選取策略中占有的不同比例進行綜合計算，并且最終算出一個計算結果，而這個計算結果就是這個可用網關節點的PRI（優先級）.公式如下所示:

公式中通過下面參數實現區分，選擇路徑指標:

1.路由大小:也是路徑的長度，即路徑的跳數，是路徑上所經過各個節點的個數總和.源節點發起路由請求消息時，將路由大小=0，路由每經過一次，記錄都寫入路由記錄中.進行累加.hop_percent是指路由大小在公式中所占的比例，本算法中hop_percent是給定的一個定值，hop_percent=10%.

2.可靠性:主要是了路由中鏈接依賴性，一般情況下網絡鏈接失效較多，如果失效后，網絡鏈接修復速度比較快.因為節點作用在無線Mesh網中具有移動性，該節點的可靠度也是未知的，所以在本文中出現的各個節點的可靠度被賦與一個隨機值.stab_percent指路由可靠性在公式中所占的比例，本算法中stab_percent是給定的一個定值.stab_percent=40%.

3.帶寬:指進行流通的鏈接容量.一般情況下，以太網鏈接中，10Mbps比64kbps更好.本文中出現的帶寬bandwidth被賦與一個隨機值.bandwidth_percent是指帶寬在公式中所占的比例，本算法中bandwidth是給定的一個定值.bandwidth_percent=20%.

4.路由延遲:節點進行分組傳輸所花的時間.它由所決定，本文中的delay是一個隨機值.delay_percent是路由延遲在公式中所占的比例，它是一個定值，delay_percent=10%.

5.等待隊列（team）:指路徑中正在等待的業務的數量.由網絡狀態所決定，所以本文中的team是一個隨機值.team_percent是等待隊列在公式中所占的比例，它是一個定值，team_percent=10%.

6.其它（other）:影響路由的其它因素，是一個隨機值，other_percent是它在算法中的比例，是一個定值，other_percent=10%.

2.3 網關的維護

由于無線Mesh網中終端節點具有可移動性，所以網關節點路由中信息應進行及時的維護.

算法按照周期，發送一次探測包，查找是否有備用的網關節點，如果查找到可用的網關節點，那么重新執行網關節點的優化選取.否則重新進行可用網關的發現等全過程.

3 結束語

這種無線Mesh網的網關節點分成三個階段:可用網關節點的發現、最優網關的選舉以及網關節點的維護.可用網關節點的發現過程中實現了對網絡結構中源移動節點對網關節點探測并發現的過程.最優網關的選舉實現了從多個可用網關節點以及多條路徑中優化選舉出最適合的網關節點，并定期通過網關節點的維護實現路由表的更新.

總之，由于無線Mesh網絡中節點的移動性以及鏈路的易受干擾性，使得數據易丟失，采用這種網關節點選舉算法減少和克服這種缺點，是一種較好的解決辦法.

〔1〕徐格，吳建平，徐明偉.高等計算機網絡——體系結構、協議機制、算法設計與路由器技術[M].北京：機械工業出版社，2013.70-83.

〔2〕劉元安.未來移動通信系統概論[M].北京：北京郵電大學出版社，1999.

〔3〕Yigal Bejerano,Seung-Jae Han,Amit Kumar.Efficient load-balancing routing for wirelessmesh networks.Computer Networks.205.11-18.

〔4〕Ian F Akyildiz,Xudong Wang,Weilin Wang.Wireless mesh networks-a survey.Computer Networks.2015.1-9.

〔5〕Tsai-Wei Wu,Hung-Yun Hsieh.Interworking wireless mesh networks-Problems,performancecharacterization, and perspectives.JournalofParalleland Distributed Computing.2014.5-12.

TP301.6

A

1673-260X（2017）02-0022-03

2016-10-21

2016年度吉林省高校科學技術和人文社會科學研究規劃項目（2016ZCY266）