鄒蕾

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

無線Mesh網(wǎng)網(wǎng)關(guān)節(jié)點動態(tài)選舉算法研究

鄒蕾

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

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

無線Mesh網(wǎng)；Ad Hoc網(wǎng)絡(luò)；路由協(xié)議；網(wǎng)關(guān)選取

1 引言

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

Mesh終端的設(shè)備一般采用手機，電腦和PAD等.每個不同的終端進行相互訪問和連接構(gòu)成P2P網(wǎng)絡(luò).無線Mesh網(wǎng)作為一種新型寬帶無線接入技術(shù)備受學(xué)術(shù)界關(guān)注，逐漸成為下一代WMN的核心.

WMN的核心技術(shù)提供給通過無線技術(shù)提供給用連接無線網(wǎng)絡(luò).移動終端用戶接入無線接入服務(wù)，當(dāng)移動終端節(jié)點通過無線Mesh網(wǎng)接入Internet時，在無線Mesh網(wǎng)中需要找到可用的無線網(wǎng)關(guān)節(jié)點為其提供接入Mesh網(wǎng)絡(luò)的服務(wù)，所以如何選取網(wǎng)關(guān)節(jié)點一直是該領(lǐng)域研究的關(guān)鍵問題.

2 無線Mesh網(wǎng)網(wǎng)關(guān)節(jié)點動態(tài)選舉算法的設(shè)計與實現(xiàn)

這里設(shè)計用于無線Mesh網(wǎng)的網(wǎng)關(guān)節(jié)點動態(tài)選舉算法，主要是采用共同的思路——訪問網(wǎng)關(guān).提出一種優(yōu)化的網(wǎng)關(guān)選取算法.

根據(jù)無線Mesh網(wǎng)的有關(guān)特性，將網(wǎng)關(guān)節(jié)點動態(tài)選舉算法的過程應(yīng)該分為三個階段:(1)可用網(wǎng)關(guān)節(jié)點的發(fā)現(xiàn).(2)最優(yōu)網(wǎng)關(guān)的選舉.(3)網(wǎng)關(guān)的維護.

2.1 可用網(wǎng)關(guān)節(jié)點的發(fā)現(xiàn)

2.1.1 算法需要維護的數(shù)據(jù)結(jié)構(gòu)

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

(1)協(xié)議圖G(V1,PV,E1,PE):通過G(V1,E1)在路由協(xié)議中表達網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).其中，節(jié)點集合用V1表示，V1在網(wǎng)絡(luò)中表示網(wǎng)絡(luò)接入點，邊集合用EI表示，EI是無線鏈路，在網(wǎng)絡(luò)的實際應(yīng)用中，鏈路，節(jié)點之間在不同的環(huán)境總會出現(xiàn)失效，所以為了滿足實際的需求，在協(xié)議圖G中給邊，節(jié)點賦概率值，形成協(xié)議圖G.

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

(2)傳輸路徑:目的，源點之間進行傳輸?shù)耐ㄐ沛溌?

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

(4)路徑軌跡:網(wǎng)絡(luò)傳輸中記錄的節(jié)點序號.

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

2.節(jié)點的數(shù)據(jù)結(jié)構(gòu)設(shè)計

表1 節(jié)點結(jié)構(gòu)

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

(1)節(jié)點位置:由于在WMN中具有GPS獨立定位功能的只有MESH網(wǎng)絡(luò).該定位系統(tǒng)的誤差在1秒鐘之內(nèi)不超過10米.為了在本文設(shè)定的30×30范圍的區(qū)域以內(nèi)精確的表示出節(jié)點的位置，用兩個變量表示每個節(jié)點的坐標(biāo)位置.

(2)網(wǎng)關(guān)標(biāo)志位:網(wǎng)關(guān)標(biāo)志位是用于節(jié)點是否是網(wǎng)關(guān)節(jié)點的.在無線Mesh網(wǎng)中，網(wǎng)關(guān)節(jié)點是以有線的方式與無線Mesh網(wǎng)的骨干網(wǎng)相連的，為了表示這個特殊的節(jié)點，用變量GW表示，當(dāng)GW=1時證明該網(wǎng)絡(luò)節(jié)點為網(wǎng)關(guān)節(jié)點.

3.路由請求消息列表

無線Mesh網(wǎng)中當(dāng)移動節(jié)點為了尋找可用的網(wǎng)關(guān)節(jié)點而發(fā)起路由時，首先發(fā)送一個探測包，其中主要包括的就是RREQ（路由請求消息），該探測包的結(jié)構(gòu)如表2所示:

表2 路由請求消息

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

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

(3)網(wǎng)關(guān)節(jié)點標(biāo)志:由于源節(jié)點要探測的是網(wǎng)關(guān)，由網(wǎng)關(guān)標(biāo)志位（GW）表示.

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

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

4.路由表

無線Mesh網(wǎng)中每個節(jié)點的信息保存在路由表中，路由信息通過節(jié)點來保存.如果在路由器中發(fā)現(xiàn)新鏈路時，要把發(fā)現(xiàn)的新信息加入.通過路由算法實現(xiàn)分組發(fā)送找到路徑.路由通過可節(jié)點的存儲方式，可采用直接存儲路由方式，路由表的結(jié)構(gòu)如表3所示:

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

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

(3)網(wǎng)關(guān)節(jié)點標(biāo)志:由于源節(jié)點要探測的是網(wǎng)關(guān)，由網(wǎng)關(guān)標(biāo)志位（GW）表示.

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

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

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

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

2.1.2 網(wǎng)關(guān)節(jié)點的發(fā)現(xiàn)過程

在本文中模擬10個節(jié)點的無線Mesh網(wǎng)絡(luò)結(jié)構(gòu)圖1如下所示:

圖1 模擬的無線Mesh網(wǎng)結(jié)構(gòu)圖

圖2是自由無線Mesh網(wǎng)結(jié)構(gòu)，用戶節(jié)點，GW，SGW節(jié)點都是無線終端.在網(wǎng)關(guān)節(jié)點發(fā)現(xiàn)過程中，通過一個網(wǎng)關(guān)實現(xiàn)用戶連接INTERNET網(wǎng)，若用戶不在網(wǎng)關(guān)的范圍內(nèi)，網(wǎng)絡(luò)會自動失效，客戶需求重新選擇一個網(wǎng)關(guān)連接INTERNET網(wǎng).

在介紹移動節(jié)點探測之前先做如下假設(shè):系統(tǒng)中各節(jié)點都執(zhí)行同樣的路由選擇算法,初始化網(wǎng)絡(luò)中各節(jié)點的路由表中路由大小初始值設(shè)為0.假設(shè)節(jié)點SRC_node為連接請求的源節(jié)點，連接請求的目的節(jié)點是網(wǎng)關(guān).

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

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

第三階段，當(dāng)網(wǎng)關(guān)節(jié)點GW收到來自源節(jié)點SRC_node的RREQ分組后，根本自身的網(wǎng)關(guān)標(biāo)志位GW進行判斷，證明自己就是源節(jié)點想要找到的網(wǎng)關(guān)，實現(xiàn)就路由請求.

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

圖2描述了上面討論的路由發(fā)現(xiàn)的機制.

圖2 路由發(fā)現(xiàn)機制

當(dāng)路由器內(nèi)部表發(fā)生改變，會及時把修改的狀態(tài)通知相連接的路由器，保證了數(shù)據(jù)傳輸.如圖3所示節(jié)點路由過程

圖3 路由發(fā)現(xiàn)過程

2.2 最優(yōu)網(wǎng)關(guān)的選舉

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

公式中通過下面參數(shù)實現(xiàn)區(qū)分，選擇路徑指標(biāo):

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

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

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

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

5.等待隊列（team）:指路徑中正在等待的業(yè)務(wù)的數(shù)量.由網(wǎng)絡(luò)狀態(tài)所決定，所以本文中的team是一個隨機值.team_percent是等待隊列在公式中所占的比例，它是一個定值，team_percent=10%.

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

2.3 網(wǎng)關(guān)的維護

由于無線Mesh網(wǎng)中終端節(jié)點具有可移動性，所以網(wǎng)關(guān)節(jié)點路由中信息應(yīng)進行及時的維護.

算法按照周期，發(fā)送一次探測包，查找是否有備用的網(wǎng)關(guān)節(jié)點，如果查找到可用的網(wǎng)關(guān)節(jié)點，那么重新執(zhí)行網(wǎng)關(guān)節(jié)點的優(yōu)化選取.否則重新進行可用網(wǎng)關(guān)的發(fā)現(xiàn)等全過程.

3 結(jié)束語

這種無線Mesh網(wǎng)的網(wǎng)關(guān)節(jié)點分成三個階段:可用網(wǎng)關(guān)節(jié)點的發(fā)現(xiàn)、最優(yōu)網(wǎng)關(guān)的選舉以及網(wǎng)關(guān)節(jié)點的維護.可用網(wǎng)關(guān)節(jié)點的發(fā)現(xiàn)過程中實現(xiàn)了對網(wǎng)絡(luò)結(jié)構(gòu)中源移動節(jié)點對網(wǎng)關(guān)節(jié)點探測并發(fā)現(xiàn)的過程.最優(yōu)網(wǎng)關(guān)的選舉實現(xiàn)了從多個可用網(wǎng)關(guān)節(jié)點以及多條路徑中優(yōu)化選舉出最適合的網(wǎng)關(guān)節(jié)點，并定期通過網(wǎng)關(guān)節(jié)點的維護實現(xiàn)路由表的更新.

總之，由于無線Mesh網(wǎng)絡(luò)中節(jié)點的移動性以及鏈路的易受干擾性，使得數(shù)據(jù)易丟失，采用這種網(wǎng)關(guān)節(jié)點選舉算法減少和克服這種缺點，是一種較好的解決辦法.

〔1〕徐格，吳建平，徐明偉.高等計算機網(wǎng)絡(luò)——體系結(jié)構(gòu)、協(xié)議機制、算法設(shè)計與路由器技術(shù)[M].北京：機械工業(yè)出版社，2013.70-83.

〔2〕劉元安.未來移動通信系統(tǒng)概論[M].北京：北京郵電大學(xué)出版社，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年度吉林省高?？茖W(xué)技術(shù)和人文社會科學(xué)研究規(guī)劃項目（2016ZCY266）