張　娜

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

?

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

張娜

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

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

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

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

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

1路由選擇機(jī)制與分類

1.1路由選擇機(jī)制

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

1.2路由選擇分類

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1　路由示意圖

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

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

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

3改進(jìn)最小生成樹(shù)算法實(shí)現(xiàn)

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

(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é)點(diǎn)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}無(wú)回路)

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

Else

得到最小生成樹(shù)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

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

(5) 結(jié)束.

4改進(jìn)最小生成樹(shù)算法仿真與分析

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

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

5總結(jié)

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

參考文獻(xiàn)：

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

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

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

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

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

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

[7]孫立悅，趙曉暉，虢明.基于中斷概率的協(xié)作通信中繼選擇與功率分配算法[J].通信學(xué)報(bào)，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

中圖分類號(hào)：TP393.2

文獻(xiàn)標(biāo)識(shí)碼：A

doi:10.3969/j.issn.2095-2198.2016.01.016

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

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

收稿日期：2015-09-02