改進最小生成樹算法在移動自組織網(wǎng)絡(luò)路由選擇中的應(yīng)用

張　娜

(鐵嶺師范高等?？茖W校， 遼寧 鐵嶺 112001)

?

改進最小生成樹算法在移動自組織網(wǎng)絡(luò)路由選擇中的應(yīng)用

張娜

(鐵嶺師范高等?？茖W校， 遼寧 鐵嶺 112001)

摘要:針對移動自組織網(wǎng)絡(luò)的動態(tài)性和多跳網(wǎng)絡(luò)特性，在路由選擇中提出改進最小生成樹算法.設(shè)計過程中既考慮節(jié)點間的直通中斷概率，又考慮多跳次數(shù)對信道容量的影響，通過調(diào)整最小生成樹得到源節(jié)點與目的節(jié)點間最佳路由.實驗結(jié)果表明：改進最小生成樹算法可以獲得更高的信道容量.

關(guān)鍵詞：改進最小生成樹算法；移動自組織網(wǎng)絡(luò)；路由選擇

移動自組織網(wǎng)絡(luò)是一種多跳的臨時性自治系統(tǒng)，在移動自組織網(wǎng)絡(luò)中，網(wǎng)絡(luò)中的節(jié)點通過中繼的方式連接，網(wǎng)絡(luò)拓撲結(jié)構(gòu)經(jīng)常變化.因為節(jié)點狀態(tài)可能隨時改變，通信信道也沒有傳統(tǒng)的固定基站穩(wěn)定，導致移動終端間的網(wǎng)絡(luò)拓撲結(jié)構(gòu)隨時可能發(fā)生變化[1].移動自組織網(wǎng)絡(luò)是一種臨時的、自治的、多跳的分布式網(wǎng)絡(luò)，沒有固定的基站支持通信，兩個節(jié)點之間的通信通過網(wǎng)絡(luò)中的節(jié)點進行信息轉(zhuǎn)發(fā)來完成，網(wǎng)絡(luò)中沒有中心節(jié)點或者嚴格的控制節(jié)點，所有節(jié)點地位平等，節(jié)點的功能隨狀態(tài)改變，通信路徑隨節(jié)點的改變進行調(diào)整，整體網(wǎng)絡(luò)信息的傳遞不會受任何節(jié)點故障影響.在移動自組織網(wǎng)絡(luò)中，通信路徑隨節(jié)點的狀態(tài)改變，其優(yōu)點是：不需要固定的基站支持通信；多跳網(wǎng)絡(luò)各個節(jié)點不需要直接連接，而是能夠通過中繼方式實現(xiàn)兩個距離很遠無法直接通信的節(jié)點之間傳遞信息.移動自組織網(wǎng)絡(luò)在軍事通信、移動網(wǎng)絡(luò)、緊急服務(wù)、災(zāi)難恢復(fù)、無線傳感器網(wǎng)絡(luò)等領(lǐng)域中都具有廣泛的應(yīng)用前景.

選擇合適的路由技術(shù)能夠以較低的通信負擔和計算負擔來獲得路由，而移動自組織網(wǎng)絡(luò)因為其具有動態(tài)性、多跳傳輸性，使得傳統(tǒng)的路由選擇技術(shù)在移動自組織網(wǎng)絡(luò)中無法直接使用，因此，研究新的適合移動自組織網(wǎng)絡(luò)特性的路由技術(shù)具有重要意義.

1路由選擇機制與分類

1.1路由選擇機制

路由選擇是指在互聯(lián)網(wǎng)絡(luò)中選擇從源節(jié)點到目標節(jié)點的傳輸信息通道，在信息通道中信息至少通過一個中間節(jié)點[2].路由選擇的主要工作是在OSI網(wǎng)絡(luò)參考模型中的網(wǎng)絡(luò)層.在路由選擇過程中包含兩個基本的操作：最佳路徑選擇和網(wǎng)間信息的傳遞.路由選擇策略有兩個考慮因素：一個為網(wǎng)絡(luò)的通信量，選擇通信量相對較小的路徑以避免擁塞；另一個為網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，隨時掌握網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，不能選擇一個不工作的路由器作為數(shù)據(jù)的下一跳路由器.

1.2路由選擇分類

路由選擇策略主要是選擇節(jié)點間的路徑，根據(jù)選擇方式的不同分為：靜態(tài)路由選擇和動態(tài)路由選擇[3].靜態(tài)路由選擇是事先計算好路由選擇，網(wǎng)絡(luò)啟動時加載到路由器中，不再變化.靜態(tài)路由選擇策略有：

(1) 固定式路由選擇：固定式路由選擇中網(wǎng)絡(luò)中的每一對節(jié)點都有一個固定的路徑，路徑存儲在各節(jié)點中的路由表中，當網(wǎng)絡(luò)拓撲結(jié)構(gòu)發(fā)生改變時路由表也隨之改變.當信息從源節(jié)點傳遞到某中間節(jié)點時，通過查找該節(jié)點路由表，就可以知道要轉(zhuǎn)發(fā)的下一節(jié)點地址.

(2) 洪泛路由選擇：又叫擴散法，一個分組由源節(jié)點發(fā)送到與其相鄰的所有節(jié)點，收到的節(jié)點再次將分組傳輸?shù)匠纸M經(jīng)過的節(jié)點以外的所有節(jié)點.當某一個信息分組首先到達目標節(jié)點時，則該信息分組經(jīng)歷的路徑最短，其主要應(yīng)用在諸如軍事網(wǎng)絡(luò)等對強壯性要求很高的場合.

(3) 隨機路由選擇：一個分組從源節(jié)點發(fā)送時只選擇一條路徑進行傳輸，選擇的路徑是隨機的或者采用輪詢的方式.

動態(tài)路由選擇策略是根據(jù)實時測量或者估計網(wǎng)絡(luò)的當前通信量和拓撲結(jié)構(gòu)做出路由選擇[4].動態(tài)路由選擇策略有：

(1) 獨立路由選擇策略(HOT POTATO算法).

(2) 集中路由選擇策略(RCC操控).

(3) 分布路由選擇策略(自由溝通策略).

(4) 混合式路由選擇策略.

路由選擇在網(wǎng)絡(luò)設(shè)計中是最關(guān)鍵的，采用何種算法進行路由尋址對最終的路徑選擇有重要的影響.

2改進最小生成樹算法在路由選擇中的應(yīng)用

最小生成樹算法是在一個有n個節(jié)點的無向圖G=(V,E)|V|=n中，(u,v)代表連接頂點u與頂點v的邊，而w(u,v)代表此邊的權(quán)重，若存在T為E的子集且為無循環(huán)圖，使得W(T)最小，則此T為G的最小生成樹.最小生成樹是原圖的極小連通子圖，具有保持圖連通的最少的邊.

最小生成樹算法在路由選擇中的應(yīng)用思想是：將源節(jié)點與目的節(jié)點間的所有節(jié)點進行描述，形成路由示意圖，如圖1所示.首先判斷路由圖是否為連通圖，如果路由圖為連通圖，則存在一條從源節(jié)點到目的節(jié)點的多跳直通路由；如果路由圖為非連通圖，則不存在這樣的路由.如果路由圖是連通圖，則選出最小生成樹，從源節(jié)點到目的節(jié)點在最小生成樹上的路徑就是選擇的路由[5].

圖1　路由示意圖

在描述路由圖中，假設(shè)一個參數(shù)η為節(jié)點到節(jié)點間的直通中斷概率的門限值，如果當前節(jié)點的發(fā)射功率pout≤η，則兩節(jié)點可以直接通信，即一跳通信；如果當前節(jié)點的發(fā)射功率pout>η，則需要通過中繼節(jié)點進行多跳通信.圖1中SN表示通信的源節(jié)點，DN表示通信的目的節(jié)點，RN表示通信的中繼節(jié)點.如果兩節(jié)點可以一跳直接通信，在圖中用實線連接；如果兩節(jié)點間不可以一跳直通通信，需要多跳，則用虛線連接.實際中圖1為有向圖，邊的權(quán)值為通信中斷概率，為降低算法的復(fù)雜度，將圖1簡化為無向圖，邊的權(quán)值取有向圖中權(quán)值最大者.

圖2　不考慮多跳次數(shù)最小生成樹

圖3　考慮多跳次數(shù)最小生成樹

3改進最小生成樹算法實現(xiàn)

假設(shè)將源節(jié)點與目的節(jié)點間的所有節(jié)點進行描述，形成路由示意圖G=(V,E)，V是所有頂點的集合，E是所有邊的集合.T=(U,E1)表示最終得到的最小生成樹，其中U是V的一個真子集，E1是E的真子集.|V|表示頂點的個數(shù)，|E|表示邊的個數(shù).將集合V中所有頂點編號V={v1,v2,…,vN},N=|V|，源節(jié)點為vk，目的節(jié)點為vm，源節(jié)點到目的節(jié)點的路徑為L.

(1) 初始化：令U=φ,E1=φ,E2=φ.

(2)Step1 ：

While(V?{vk,vm})

if(|E|<|V|-1)

V=V-{vi}(i=1,2,…,N,i≠k,i≠m),

E=E-{e1,e2,…,ej}

其中,j為vi的度數(shù)，e1，e2，…，ej為與節(jié)點vi相臨的邊，跳轉(zhuǎn)至Step1；

Else

圖G=(V,E)為連通圖|V|=N′,|E|=M′.

(3)Step2：

if(E≠φ)

While(w(ei)=min{w(e1),w(e2),…,w(e|E|)},E1=E1+{ei}無回路)

E1=E1+{ei},E=E-{ei},跳轉(zhuǎn)至Step2；

Else

得到最小生成樹T=(U,E1)，vk與vm的路徑L；

(4)Step3:

if(E-E1∪E2≠φ)

并且(1-max{w(L),w(e′)})/

(|L|-p+1)>(1-max{w(L)})/|L|)

跳轉(zhuǎn)至Step3；

Else

得到改進后的最小生成樹T=(U,E1)，vk與vm改進后的最佳路徑L.

(5) 結(jié)束.

4改進最小生成樹算法仿真與分析

仿真實驗結(jié)果驗證了當實驗采用相同的源節(jié)點與相同的目的節(jié)點，兩節(jié)點間的距離一致時，改進最小生成樹路由選擇算法與傳統(tǒng)的最小生成樹算法對比，可獲得更高的信道容量，見圖4.

圖4　兩種路由選擇方案下多跳直通

5總結(jié)

改進最小生成樹算法以高信道容量為目標，在設(shè)計方案過程中，即考慮節(jié)點間的直通中斷概率，又考慮多跳次數(shù)對信道容量的影響，先采用克魯斯卡爾算法得到最小生成樹，然后根據(jù)多跳次數(shù)的影響，通過反復(fù)迭帶調(diào)整最小生成樹，直至得到源節(jié)點與目的節(jié)點間最佳路由.通過實驗可以驗證：改進最小生成樹算法能夠獲得更高的信道容量.

參考文獻：

[1]易平,吳越,鄒福泰，等.無線自組織網(wǎng)絡(luò)和對等網(wǎng)絡(luò)：原理與安全[M].北京：清華大學出版社,2009：3-18.

[2]張鵬,崔勇.移動自組織網(wǎng)絡(luò)路由選擇算法研究進展[J].計算機科學,2010,37(1):10-22.

[3]RUSS W,DON S,ALVARO R.路由設(shè)計的優(yōu)化[M].北京：人民郵電出版社,2013:413-460.

[4]薛?？?，孫雨耕，劉振肖.基于帶寬和跳數(shù)的流量工程動態(tài)路由選擇算法研究[J].電子學報，2002，30(2)：274-278.

[5]陳恒.Ad hoc網(wǎng)絡(luò)的一種改進路由算法[J].江蘇科技信息,2014(21)：24-25.

[6]朱超,洪佩琳,盧漢成,等.空間網(wǎng)絡(luò)多路徑路由算法[J].通信技術(shù)，2013，46(9)：42-46.

[7]孫立悅，趙曉暉，虢明.基于中斷概率的協(xié)作通信中繼選擇與功率分配算法[J].通信學報，2013，34(10)：84-91.

Application of Improved Minimum Spanning Tree Algorithm in Routing of Mobile Ad Hoc Network

ZHANG Na

(Tieling Normal College, Tieling 112001, China)

Abstract:The improved minimum spanning tree algorithm was proposed for routing,according to the dynamics of mobile ad hoc network and the characteristics of multi-hop network.The proposed scheme takes into consideration both the outage probability among nodes and the effect of hop counts on the channel capacity.By adjusting the minimum spanning tree,the best routing is obtained between source node and destination node.Experimental results show that the improved minimum spanning tree algorithm is able to achieve higher channel capacity.

Key words:improved minimum spanning tree algorithm;mobile ad hoc network;routing

中圖分類號：TP393.2

文獻標識碼：A

doi:10.3969/j.issn.2095-2198.2016.01.016

文章編號：2095-2198(2016)01-0081-05

作者簡介：張娜(1982-)，女，遼寧沈陽人，講師，學士，主要從事計算機應(yīng)用方面的研究.

收稿日期：2015-09-02