基于連通性的動(dòng)態(tài)固定信道分配算法

尹鳳杰，梅丙乾，楊 暉，張 穎

(遼寧大學(xué) 信息學(xué)院，遼寧 沈陽(yáng) 110036)

基于連通性的動(dòng)態(tài)固定信道分配算法

尹鳳杰，梅丙乾，楊 暉，張 穎

(遼寧大學(xué) 信息學(xué)院，遼寧 沈陽(yáng) 110036)

隨著跳數(shù)的增加，無(wú)線Mesh網(wǎng)絡(luò)的延遲開(kāi)始增大，吞吐量開(kāi)始降低，QoS難以得到保證.基于多信道多接口的信道分配策略可以很好地解決上述問(wèn)題，但目前對(duì)多信道Mesh網(wǎng)絡(luò)的研究往往忽視了節(jié)點(diǎn)之間的連通性問(wèn)題.在原有的寬帶優(yōu)先搜索(BFS,Breadth First Search)算法的基礎(chǔ)上，針對(duì)動(dòng)態(tài)固定信道分配(DFCA,Dynamic Fixed Channel Allocation) 算法進(jìn)行研究，在保證連通性的前提下，為每個(gè)節(jié)點(diǎn)動(dòng)態(tài)的分配固定信道，減少了鏈路之間干擾，提高了傳輸效率，同時(shí)考慮了新加入節(jié)點(diǎn)以及失效節(jié)點(diǎn)帶來(lái)的問(wèn)題.仿真結(jié)果表明，在發(fā)送速率較大、數(shù)據(jù)流數(shù)較多的情況下，DFCA算法較傳統(tǒng)算法在吞吐量方面得到很大提高.

Mesh網(wǎng)絡(luò)；多信道；多接口；動(dòng)態(tài)分配；固定信道

0 引言

無(wú)線Mesh網(wǎng)絡(luò)(WMN,Wireless Mesh Network)是一種新型的無(wú)線網(wǎng)絡(luò)技術(shù)，與傳統(tǒng)無(wú)線網(wǎng)絡(luò)相比，WMN具有組網(wǎng)靈活、覆蓋率高、容量大、前期投資少等諸多優(yōu)點(diǎn)，近年來(lái)已成為研究的熱點(diǎn).隨著WMN的研究與深入，其中的問(wèn)題也慢慢暴露出來(lái)，最嚴(yán)重的問(wèn)題是隨著跳數(shù)的增加，WMN的延遲開(kāi)始增大，吞吐量開(kāi)始降低，QoS也變得難以得到保證.同時(shí)隨著用戶(hù)對(duì)WMN傳輸數(shù)據(jù)量和傳輸業(yè)務(wù)多樣化需求的增大，現(xiàn)有的單信道單接口的結(jié)構(gòu)已經(jīng)滿(mǎn)足不了多業(yè)務(wù)的需求，而多信道多接口的無(wú)線Mesh網(wǎng)絡(luò)節(jié)點(diǎn)可以工作在相互之間并不干擾的正交信道上，極大地提高了WMN的傳輸速率和網(wǎng)絡(luò)的容量，較好地解決了無(wú)線網(wǎng)絡(luò)中存在的隱藏終端和暴露終端問(wèn)題[1-2].

對(duì)于WMN制定合理的信道分配策略一直是多信道多接口WMN研究的重點(diǎn)，國(guó)內(nèi)外學(xué)者做了很多研究工作.文獻(xiàn)[3]分析了多信道多接口技術(shù)近年來(lái)在無(wú)線傳感器網(wǎng)絡(luò)中的應(yīng)用，得出結(jié)論利用該技術(shù)可以有效地減少干擾并降低信道沖突，增加網(wǎng)絡(luò)容量.文獻(xiàn)[4]提出一種為所有節(jié)點(diǎn)分配相同信道的方案(CCA)，這種方案沒(méi)有充分利用多信道的優(yōu)勢(shì)，且?guī)?lái)了很大的干擾.文獻(xiàn)[5]提出了一種差異信道的分配方案，為不同節(jié)點(diǎn)分配不同的信道，在一定程度上降低了信道之間的干擾，但是該方案中信道的分配是固定的，破壞了網(wǎng)絡(luò)的連通性.文獻(xiàn)[6]在車(chē)載自組織網(wǎng)絡(luò)中合理的實(shí)現(xiàn)了多接口多信道，提出了一種基于通信雙方車(chē)輛節(jié)點(diǎn)信道切換隊(duì)列的動(dòng)態(tài)信道分配方法，較好地解決了車(chē)輛節(jié)點(diǎn)間通信信道的動(dòng)態(tài)分配以及信道公平接入和分配不合理的問(wèn)題，但該方案中沒(méi)有考慮信道的獨(dú)立性和干擾問(wèn)題.文獻(xiàn)[7]提出一種最小干擾的信道分配策略(MICA)，該方法充分考慮流量、距離、接口數(shù)等因素確定節(jié)點(diǎn)的優(yōu)先級(jí)，并以此來(lái)進(jìn)行信道的分配.文獻(xiàn)[8]將最優(yōu)信道帶寬調(diào)制與多信道多接口技術(shù)相結(jié)合提出分布式流量感知的信道帶寬調(diào)制，有效增加了頻譜使用效率并提高了網(wǎng)絡(luò)性能，但該方法并沒(méi)有考慮信道的優(yōu)化問(wèn)題.文獻(xiàn)[9]將多信道多接口應(yīng)用到多播信道分配中，可以使無(wú)線Mesh網(wǎng)絡(luò)的干擾程度最小化，并最大化網(wǎng)絡(luò)吞吐量，但該算法沒(méi)有考慮在實(shí)際無(wú)線路由器中可能存在增加、刪除和移動(dòng)以及多播成員可能自由地加入和離開(kāi)多播組等動(dòng)態(tài)情況，即沒(méi)有考慮信道重新分配問(wèn)題.文獻(xiàn)[10]從多信道多接口無(wú)線Mesh網(wǎng)絡(luò)傳輸容量入手，提出拓?fù)淇煽啃约s束下的邏輯拓?fù)湓O(shè)計(jì)方法，以拓?fù)淇煽啃约熬W(wǎng)絡(luò)路徑跳數(shù)為約束條件，以最大容量最小干擾為優(yōu)化目標(biāo)，進(jìn)而得到優(yōu)化的邏輯拓?fù)?

針對(duì)現(xiàn)有研究存在的問(wèn)題，本文提出一種基于連通性的動(dòng)態(tài)固定信道分配策略，為節(jié)點(diǎn)動(dòng)態(tài)的分配固定信道，固定信道用于數(shù)據(jù)的接收，備用信道處于“待接收”狀態(tài)，隨時(shí)準(zhǔn)備用于數(shù)據(jù)的接收，其余信道為可切換信道，用于數(shù)據(jù)的發(fā)送.同時(shí)這三種信道可以在一定條件下相互轉(zhuǎn)換，保障了網(wǎng)路連通性的前提下提高了網(wǎng)絡(luò)吞吐量，降低了信道之間的干擾，并優(yōu)化了網(wǎng)絡(luò)信道的分配.

1 WMN干擾模型及圖論模型

1.1 干擾模型

在WMN中由于復(fù)雜的無(wú)線環(huán)境，信道之間的相互干擾十分嚴(yán)重，網(wǎng)絡(luò)的傳輸速率往往只能發(fā)揮其最大帶寬的一部分.此外，WMN中的流量走向具有很大的不確定性，在某一階段很容易出現(xiàn)某個(gè)或某些節(jié)點(diǎn)負(fù)載過(guò)重的問(wèn)題，形成網(wǎng)絡(luò)的瓶頸.

WMN中存在各種類(lèi)型的干擾，根據(jù)業(yè)務(wù)流的不同可劃分為流內(nèi)干擾和流間干擾[11]，本文重點(diǎn)對(duì)流內(nèi)干擾和流間干擾進(jìn)行研究.

流內(nèi)干擾(Inter Interference)是指在同一流的傳輸路徑上傳輸?shù)臄?shù)據(jù)如果工作在同一信道上則由于相互競(jìng)爭(zhēng)而會(huì)產(chǎn)生干擾.流間干擾(Intra Interference)是指不同流的傳輸路徑如果和相鄰傳輸路徑工作在同一信道上則兩者之間會(huì)產(chǎn)生影響.

由于WMN的環(huán)境較為復(fù)雜，對(duì)每個(gè)節(jié)點(diǎn)的SINR計(jì)算也是一個(gè)復(fù)雜和龐大的工程，同時(shí)由于背景噪聲的不斷變化，每個(gè)節(jié)點(diǎn)的SINR也處在動(dòng)態(tài)變化之中，尤其是對(duì)于臨界值的情況很難進(jìn)行準(zhǔn)確的處理，所以在研究中通常不采用物理干擾模型，而是采用協(xié)議干擾模型.

假設(shè)一個(gè)WMN由N個(gè)節(jié)點(diǎn)組成，現(xiàn)進(jìn)行如下定義：

ni：WMN中的第i個(gè)節(jié)點(diǎn)，且1≤i≤N.

di,j：節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的距離.

Rt：節(jié)點(diǎn)的傳輸距離，是兩個(gè)節(jié)點(diǎn)在沒(méi)有干擾的情況下能夠通信的最大距離.

Ri：節(jié)點(diǎn)的干擾距離，是對(duì)其他節(jié)點(diǎn)帶來(lái)干擾的有效距離，通常是Rt的2.2倍，默認(rèn)所有節(jié)點(diǎn)的Rt、Ri都是一樣的.

Ci：節(jié)點(diǎn)i可用的信道.

CUi：節(jié)點(diǎn)i正在使用的信道.

則節(jié)點(diǎn)j能夠接收到節(jié)點(diǎn)i發(fā)送的數(shù)據(jù)需要滿(mǎn)足以下條件：

di,j≤Rt，即兩個(gè)節(jié)點(diǎn)之間的距離小于節(jié)點(diǎn)的傳輸距離.

?k∈Ck,k∈Ci且k∈Cj，即兩個(gè)節(jié)點(diǎn)之間存在相同的信道

?/m≠i,j,CUm=CUi且CUm=CUj，dm,j≤Ri，即不存在節(jié)點(diǎn)m，使得m正在使用和i，j相同的信道，且m，j之間的距離小于干擾距離.也就是只有m正在使用和i，j相同的信道且m，j之間的距離小于干擾距離時(shí)，m才會(huì)對(duì)j產(chǎn)生干擾.

協(xié)議干擾模型其實(shí)就是一種邏輯的是非關(guān)系[12]，只要滿(mǎn)足上述三個(gè)條件節(jié)點(diǎn)j能夠接收到節(jié)點(diǎn)i發(fā)送的數(shù)據(jù).由于WMN中節(jié)點(diǎn)弱移動(dòng)性的特點(diǎn)，兩個(gè)節(jié)點(diǎn)之間的距離一般是固定的，可能對(duì)其產(chǎn)生干擾的節(jié)點(diǎn)在不在其干擾范圍內(nèi)也是確定的，在進(jìn)行算法研究時(shí)只需重點(diǎn)考慮信道問(wèn)題即可，很適合WMN信道干擾問(wèn)題的研究，如無(wú)特殊說(shuō)明 則本文采用的是協(xié)議干擾模型.

1.2 圖論模型

采用圖論方式為WMN建立模型，通常認(rèn)為所有節(jié)點(diǎn)都處在同一平面上，且各節(jié)點(diǎn)的傳輸距離Rt和干擾距離Ri都是相同的.

假設(shè)WMN中有m個(gè)可用的正交信道c={1,2,3,4…m}；Ii是節(jié)點(diǎn)i處的接口數(shù)，且1≤Ii≤m,如果兩個(gè)節(jié)點(diǎn)在彼此的傳輸距離內(nèi)，將信道分配給各個(gè)節(jié)點(diǎn)形成鏈路以后所有節(jié)點(diǎn)和鏈路就構(gòu)成了網(wǎng)絡(luò)拓?fù)銰=(V,E)，其中V表示節(jié)點(diǎn)，E表示分配給節(jié)點(diǎn)之間的鏈路，這樣就構(gòu)成了連接圖，連接圖很好地表明了節(jié)點(diǎn)和信道之間的關(guān)系，但是節(jié)點(diǎn)之間的鏈路是否產(chǎn)生干擾不易從連接圖上看出，如圖1就是一個(gè)連接圖.

在連接圖的基礎(chǔ)上，可以得到WMN的沖突圖G′=(V′,E′)，其中V′表示節(jié)點(diǎn)之間的鏈路，如果兩條鏈路之間存在干擾，則代表兩條鏈路之間存在一條邊，這些邊組成集合E′.

假設(shè)圖1連接圖中的沖突域?yàn)?跳范圍，則可以得到圖2的沖突圖.

沖突圖很好地表明了鏈路之間的干擾關(guān)系，很適合WMN信道干擾的研究，結(jié)合協(xié)議干擾模型，本文采用上述假設(shè)，認(rèn)為沖突域?yàn)?跳范圍.

2 動(dòng)態(tài)固定信道分配算法

2.1 BFS信道分配算法

當(dāng)一個(gè)多接口多信道的節(jié)點(diǎn)A需要通信時(shí)，它的鄰居節(jié)點(diǎn)至少要感知到節(jié)點(diǎn)A的一個(gè)信道才能正常通信，尤其是對(duì)于節(jié)點(diǎn)A是新加入節(jié)點(diǎn)的情況下.目前國(guó)內(nèi)外研究的重點(diǎn)往往在于人為的將信道分配給兩個(gè)節(jié)點(diǎn)，而兩個(gè)節(jié)點(diǎn)之間如果彼此無(wú)法感知到對(duì)方的話是無(wú)法正常進(jìn)行信道分配的.

對(duì)此文獻(xiàn)[13]提出一種基于感知的信道分配算法，為每一個(gè)節(jié)點(diǎn)分配兩種接口，一個(gè)用于固定信道傳輸，其余的用于可切換信道傳輸，節(jié)點(diǎn)對(duì)數(shù)據(jù)的接收是通過(guò)固定信道完成的， 具體內(nèi)容如下：

每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)鄰居表和信道使用表，鄰居表用以記錄鄰居節(jié)點(diǎn)固定信道的使用情況，信道使用表記錄2跳以?xún)?nèi)鄰居各個(gè)信道使用數(shù)量的情況，同時(shí)每個(gè)信道維護(hù)一個(gè)如圖3所示的包隊(duì)列.

圖1 連接圖

圖2 沖突圖

圖3 包隊(duì)列

每個(gè)節(jié)點(diǎn)定期的向鄰居節(jié)點(diǎn)發(fā)送一個(gè)Hello包，由于使用多信道，在某個(gè)信道上發(fā)送的Hello包只會(huì)被正在使用該信道的節(jié)點(diǎn)接收到，所以節(jié)點(diǎn)需要在每一個(gè)可用信道上發(fā)送Hello包.Hello包包含了節(jié)點(diǎn)固定信道的使用情況和節(jié)點(diǎn)當(dāng)前的鄰居表，當(dāng)一個(gè)節(jié)點(diǎn)收到鄰居節(jié)點(diǎn)發(fā)送的Hello包時(shí)，節(jié)點(diǎn)根據(jù)包中鄰居節(jié)點(diǎn)固定信道使用情況來(lái)更新自己的鄰居表和信道使用表.當(dāng)一個(gè)新的節(jié)點(diǎn)加入時(shí)，它不會(huì)和其他節(jié)點(diǎn)進(jìn)行通信，直到這個(gè)節(jié)點(diǎn)在每一個(gè)信道上發(fā)送了自己Hello包.一個(gè)節(jié)點(diǎn)A將數(shù)據(jù)包發(fā)送給鄰居節(jié)點(diǎn)B的具體流程如下：

1)節(jié)點(diǎn)A查詢(xún)并更新自己的鄰居表，找到節(jié)點(diǎn)B的固定信道使用情況.

2)若找到節(jié)點(diǎn)B的固定信道信息則將數(shù)據(jù)加入到節(jié)點(diǎn)B正在使用的固定信道的隊(duì)列上等待傳輸.

3)若查找不到節(jié)點(diǎn)B的固定信道使用情況則進(jìn)行等待，若超過(guò)設(shè)定的閾值則停止本次發(fā)送，同時(shí)將該數(shù)據(jù)在隊(duì)列上清除.若在閾值范圍內(nèi)收到來(lái)自節(jié)點(diǎn)B的Hello包則進(jìn)行步驟(2).

4)進(jìn)行數(shù)據(jù)的發(fā)送，如果數(shù)據(jù)發(fā)送成功則結(jié)束本次數(shù)據(jù)傳輸，將數(shù)據(jù)從隊(duì)列上清除；如果數(shù)據(jù)發(fā)送失敗則進(jìn)行步驟(1)，直至超時(shí)；超時(shí)則停止本次發(fā)送，同時(shí)將該數(shù)據(jù)在隊(duì)列上清除.

以上算法適合于網(wǎng)絡(luò)流量比較均衡的情況，但是WMN中存在著中心流量的情況，即某一時(shí)刻流量集中流向某個(gè)節(jié)點(diǎn)或某一時(shí)刻流量從某個(gè)節(jié)點(diǎn)流出，如圖4所示當(dāng)某個(gè)節(jié)點(diǎn)流量集中流出時(shí)，該算法可以充分發(fā)揮多信道的優(yōu)勢(shì).假設(shè)節(jié)點(diǎn)A為中心節(jié)點(diǎn)，節(jié)點(diǎn)B、C、D、E為鄰居節(jié)點(diǎn)，節(jié)點(diǎn)A、B、C、D、E的固定信道分別為信道a、b、c、d、e，流量是從中心節(jié)點(diǎn)流向鄰居節(jié)點(diǎn)，則根據(jù)上述算法，節(jié)點(diǎn)A分別使用信道b、c、d、e同時(shí)發(fā)送數(shù)據(jù)，極大地提高了傳輸速率.然而當(dāng)流量集中流向中心節(jié)點(diǎn)時(shí)，如圖5所示，根據(jù)上述算法節(jié)點(diǎn)B、C、D、E都使用信道a傳輸數(shù)據(jù)，相當(dāng)于是單信道傳輸，并沒(méi)有發(fā)揮多信道的優(yōu)勢(shì)，基于上述原因，本文提出動(dòng)態(tài)固定信道的信道分配算法DFCA(Dynamic Fixed Channel Allocation Algorithm).

圖4 流量從中心節(jié)點(diǎn)流出

圖5 流量從中心節(jié)點(diǎn)流入

2.2 DFCA信道分配算法

在原來(lái)的信道分配算法中，每個(gè)節(jié)點(diǎn)只有一個(gè)固定信道，其他節(jié)點(diǎn)如果需要向該節(jié)點(diǎn)傳輸數(shù)據(jù)則使用該節(jié)點(diǎn)的固定信道進(jìn)行傳輸，當(dāng)多個(gè)節(jié)點(diǎn)需要和該節(jié)點(diǎn)進(jìn)行通信時(shí)則需要競(jìng)爭(zhēng)使用信道.本文為節(jié)點(diǎn)動(dòng)態(tài)的配置固定信道，設(shè)置多個(gè)固定信道和一個(gè)備用的信道，為節(jié)點(diǎn)配備信道的具體算法如下：

1)節(jié)點(diǎn)在發(fā)送Hello包之前先檢查自己備用信道使用情況，并查詢(xún)自己的信道使用表.如果備用信道正在被使用，則在信道使用表中挑選一個(gè)使用數(shù)量最少的信道作為自己新的備用信道，原來(lái)的備用信道轉(zhuǎn)換為固定信道；如果檢查到自己的固定信道存在空閑的情況，將這些信道以及備用信道的使用數(shù)進(jìn)行比較，挑選一個(gè)數(shù)值最小的作為備用信道，其余信道成為普通的可切換信道，以上信息都會(huì)被加入到Hello包中發(fā)送出去.

2)如果增加的固定信道數(shù)量達(dá)到一定的閾值則不再進(jìn)行增加，同時(shí)在固定信道中選擇使用數(shù)量最少的信道作為備用信道.

圖6 DFCA節(jié)點(diǎn)分配信道算法流程圖

3)節(jié)點(diǎn)收到鄰居節(jié)點(diǎn)發(fā)送的Hello包以后，根據(jù)包中鄰居節(jié)點(diǎn)固定信道的使用情況進(jìn)行查詢(xún)，并根據(jù)其中的信息更新自己的鄰居表以及自己的信道使用表.具體算法流程圖如圖6所示：

需要特別說(shuō)明的是節(jié)點(diǎn)所有的信道都是空閑即沒(méi)有進(jìn)行數(shù)據(jù)傳輸時(shí)候的情況，假設(shè)現(xiàn)在某個(gè)節(jié)點(diǎn)A有一個(gè)固定信道正在通信，備用信道空閑，現(xiàn)在數(shù)據(jù)傳輸完畢，則在這兩個(gè)信道當(dāng)中選擇一個(gè)信道使用數(shù)量少的作為備用信道，這時(shí)候節(jié)點(diǎn)A的Hello表中只存在一個(gè)信道就是節(jié)點(diǎn)A的備用信道，而沒(méi)有任何的固定信道.

同時(shí)節(jié)點(diǎn)所維護(hù)的包隊(duì)列的結(jié)構(gòu)也發(fā)生了相應(yīng)的改變.當(dāng)節(jié)點(diǎn)正在進(jìn)行通信，且節(jié)點(diǎn)的固定信道數(shù)量并未達(dá)到閾值時(shí)的包隊(duì)列如圖7所示，當(dāng)節(jié)點(diǎn)沒(méi)有進(jìn)行通信時(shí)的包隊(duì)列如圖8所示，當(dāng)節(jié)點(diǎn)的固定信道達(dá)到一定閾值時(shí)的包隊(duì)列如圖9所示.

當(dāng)兩個(gè)節(jié)點(diǎn)之間需要通信，例如節(jié)點(diǎn)A向節(jié)點(diǎn)B發(fā)送數(shù)據(jù)時(shí)，節(jié)點(diǎn)A會(huì)選擇使用節(jié)點(diǎn)B的備用信道進(jìn)行數(shù)據(jù)傳輸，具體過(guò)程如下：

1)節(jié)點(diǎn)A查詢(xún)并更新自己的鄰居表，找到節(jié)點(diǎn)B的備用信道使用情況.

2)若找到節(jié)點(diǎn)B的備用信道信息則將數(shù)據(jù)加入到節(jié)點(diǎn)B正在使用的備用信道的隊(duì)列上等待傳輸.

3)若查找不到節(jié)點(diǎn)B的備用信道使用情況則進(jìn)行等待，若超過(guò)設(shè)定的閾值則停止本次發(fā)送，同時(shí)將該數(shù)據(jù)在隊(duì)列上清除.若在閾值范圍內(nèi)收到來(lái)自節(jié)點(diǎn)B的Hello包則進(jìn)行步驟(2).

圖7 包隊(duì)列情況1

圖8 包隊(duì)列情況2

圖9 包隊(duì)列情況3

4)進(jìn)行數(shù)據(jù)的發(fā)送，如果數(shù)據(jù)發(fā)送成功則結(jié)束本次數(shù)據(jù)傳輸，將數(shù)據(jù)從隊(duì)列上清除；如果數(shù)據(jù)發(fā)送失敗則進(jìn)行步驟(1)，直至超時(shí)；超時(shí)則停止本次發(fā)送，同時(shí)將該數(shù)據(jù)在隊(duì)列上清除.

具體算法流程圖10所示：

此時(shí)節(jié)點(diǎn)B由于備用信道被使用，則會(huì)將備用信道轉(zhuǎn)為固定信道，同時(shí)查詢(xún)自己的信道使用表，挑選信道使用數(shù)最少的信道作為自己新的備用信道直到固定信道數(shù)達(dá)到一定的閾值，當(dāng)固定信道數(shù)量達(dá)到閾值時(shí)，從固定信道中挑選信道使用數(shù)量最少的做為備用信道.

圖10 節(jié)點(diǎn)間通信算法流程圖

圖11 新節(jié)點(diǎn)加入算法流程圖

當(dāng)一個(gè)新的節(jié)點(diǎn)加入到WMN中時(shí)，由于該節(jié)點(diǎn)并未指定備用信道，Hello包中的信息為空，其余節(jié)點(diǎn)無(wú)法發(fā)現(xiàn)該節(jié)點(diǎn)，更無(wú)法與之通信.則該節(jié)點(diǎn)在發(fā)送自己的Hello包之前先進(jìn)行監(jiān)聽(tīng)，如果在閾值范圍內(nèi)接收到了來(lái)自鄰居的Hello包，則說(shuō)明是加入已有的WMN，節(jié)點(diǎn)會(huì)根據(jù)收到的Hello包建立起自己的鄰居表和信道使用表，再根據(jù)信道使用表的情況進(jìn)行備用信道的選擇，最后發(fā)送自己Hello包加入到網(wǎng)絡(luò)當(dāng)中；如果在閾值范圍內(nèi)沒(méi)有收到任何鄰居節(jié)點(diǎn)的Hello包，則說(shuō)明這是一個(gè)全新的WMN，這個(gè)節(jié)點(diǎn)不必等到收到鄰居節(jié)點(diǎn)的Hello包即開(kāi)始定期廣播自己的Hello包，同時(shí)隨機(jī)選擇一個(gè)信道作為自己初始的備用信道.具體算法流程圖如圖11所示：

當(dāng)一個(gè)舊的節(jié)點(diǎn)離開(kāi)或者失效時(shí)，這個(gè)節(jié)點(diǎn)已經(jīng)不參與WMN的傳輸，但是該節(jié)點(diǎn)還是存在于鄰居節(jié)點(diǎn)的鄰居表中.為了解決節(jié)點(diǎn)失效的問(wèn)題，各個(gè)節(jié)點(diǎn)再發(fā)送自己的Hello包時(shí)加入一個(gè)時(shí)間戳，節(jié)點(diǎn)設(shè)置一個(gè)自己的鄰居節(jié)點(diǎn)最大存活時(shí)間.當(dāng)節(jié)點(diǎn)收到鄰居節(jié)點(diǎn)發(fā)送的Hello包時(shí)就更新存活時(shí)間，同時(shí)在更新自己的鄰居表時(shí)檢查鄰居節(jié)點(diǎn)的時(shí)間戳，如果超過(guò)了最大存活時(shí)間則認(rèn)為該節(jié)點(diǎn)已經(jīng)失效了，將該節(jié)點(diǎn)從鄰居表中刪除，再更新自己的鄰居表和信道使用表.具體算法流程圖如12所示.

圖12 節(jié)點(diǎn)失效處理流程圖

3 仿真與性能分析

仿真實(shí)驗(yàn)場(chǎng)景設(shè)置為1 000 m×1 000 m的范圍內(nèi)隨機(jī)分配50個(gè)Mesh節(jié)點(diǎn)，所有節(jié)點(diǎn)物理層采用IEEE 802.11a協(xié)議標(biāo)準(zhǔn).對(duì)于DFCA算法，每個(gè)節(jié)點(diǎn)配置有3個(gè)射頻接口，采用CBR流量模式，分別測(cè)試在發(fā)送速率、數(shù)據(jù)流數(shù)不同時(shí)與BFS算法及經(jīng)典的DCA算法的比較.

圖13表示CBR發(fā)送速率與吞吐量的關(guān)系，其中橫坐標(biāo)表示CBR的發(fā)送速率，縱坐標(biāo)表示W(wǎng)MN的吞吐量.通過(guò)對(duì)比可以看出，當(dāng)發(fā)送速率較小時(shí)，DCA、BFS和DFCA算法并無(wú)太大區(qū)別，當(dāng)發(fā)送速率稍微有所提升時(shí)，DCA的吞吐量立刻出現(xiàn)明顯的衰退，當(dāng)發(fā)送速率提升至7MBPS時(shí)，BFS也開(kāi)始出現(xiàn)衰退的現(xiàn)象而DFCA算法則直到9MBPS時(shí)才會(huì)衰退，DFCA在高速率傳輸時(shí)的吞吐量大約比BFS多15%左右.

圖13 CBR發(fā)送速率與吞吐量的關(guān)系

圖14 CBR數(shù)據(jù)流數(shù)與吞吐量的關(guān)系

圖14表示CBR數(shù)據(jù)流數(shù)與吞吐量的關(guān)系，其中橫坐標(biāo)表示CBR的數(shù)據(jù)流數(shù)，縱坐標(biāo)表示W(wǎng)MN的吞吐量.通過(guò)對(duì)比可以看出，當(dāng)WMN中的數(shù)據(jù)流較少時(shí)，三種分配算法的吞吐量并無(wú)太大差別，但是隨著數(shù)據(jù)流數(shù)的增加，DCA算法和BSF算法的吞吐量開(kāi)始出現(xiàn)衰退，而且BFS算法的衰退程度要明顯大于DCA算法，這是因?yàn)锽FS算法是基于連通性的，當(dāng)數(shù)據(jù)流數(shù)增大時(shí)，中心節(jié)點(diǎn)的問(wèn)題變得突出，吞吐量受到嚴(yán)重限制.而DFCA算法雖然也存在中心節(jié)點(diǎn)的問(wèn)題，但由于其采用了動(dòng)態(tài)固定信道的分配策略，其受影響程度遠(yuǎn)遠(yuǎn)小于BFS算法.

4 結(jié)論

本文在BFS算法的基礎(chǔ)上提出DFCA算法，該算法采用動(dòng)態(tài)固定信道的策略來(lái)進(jìn)行信道的分配，在不改變WMN連通性的前提下靈活動(dòng)態(tài)的分配節(jié)點(diǎn)的固定信道，使得節(jié)點(diǎn)可以同時(shí)使用不同的信道進(jìn)行數(shù)據(jù)的接收，很好的解決了中心節(jié)點(diǎn)的問(wèn)題.仿真實(shí)驗(yàn)可以看出DFCA算法性能要優(yōu)于BFS算法和DCA算法，尤其是節(jié)點(diǎn)發(fā)送速率變大，數(shù)據(jù)流數(shù)增多的情況下.

[1] So J,Vaidya N.Multi-channel MAC for ad hoc networks:handling multi-channel hidden terminals using a single transceiver[C].ACM International Symposium on Mobile Ad Hoc Networking and Computing，2004:222-233.

[2] 任遠(yuǎn),董淑福,王耀國(guó).數(shù)據(jù)鏈中隱藏終端問(wèn)題的幾種解決方法[J].通信技術(shù)，2009,20(5):54-56

[3] Wu Y S,Mihaela Cardei.Multi-channel and cognitive radio approaches for wireless sensor networks[J].Computer Communications,2016，94(94):30-45.

[4] Draves R,Padhye J,Zill B.Routing in multi-radio,multi-hop wireless mesh netws[C].Proceedings of the 10th annual international conference on Mobile computing and networking,2004:114-128.

[5] Marina M K,Das S R,Subramanian A P.A topology control approach for utilizing multiple channels in multi-radio wireless mesh networks[J].Computer Networks,2010,54(2):241-256.

[6] 張民,德敏,金康.一種多接口多信道VANET動(dòng)態(tài)信道分配算法研究[J].計(jì)算機(jī)應(yīng)用研究,2014,31(5):1516-1519.

[7] Subramanian A,Gupta H,Das S R.Minimum interference channel assignment in multi-radio wireless mesh networks[J].IEEE Transactions on Mobile Computing,2008,7(12):1459-1473.

[8] 李禮,張春元.多接口多信道無(wú)線網(wǎng)狀網(wǎng)中流量感知的信道帶寬調(diào)制算法[J].電子學(xué)報(bào),2010,38(4).

[9] 邱振謀,姚國(guó)祥,官全龍,等.多信道無(wú)線 Mesh網(wǎng)絡(luò)的多播信道分配算法[J].計(jì)算機(jī)工程,2011,37(6):107-109.

[10] 包學(xué)才,戴伏生,韓衛(wèi)占.多接口多信道無(wú)線Mesh網(wǎng)絡(luò)的邏輯拓?fù)湓O(shè)計(jì)[J].小型微型計(jì)算機(jī)系統(tǒng),2015,36(6):1249-1254.

[11] Sandeep Kour Ahuja.Algorithms for routing and channel assignment in wireless infrastructure networks[D].The university of Arizona.2010.04.

[12] GuPta P,Kumar P.The capacity of wireless networks[J].IEEE Transactions on Information Theory，2010,46(2):388-404.

[13] Kyasanur P,Vaidya N H.Routing and link-layer protocols for multi-channel multi-interface Ad Hoc wireless networks[J].ACM SIGMOBILE Mobile Computing and Communications Review,2010,10(1):31-43.

(責(zé)任編輯鄭綏乾)

DynamicFixedChannelAllocationAlgorithmBasedonConnectivity

YIN Feng-jie,MEI Bing-qian,YANG Hui,ZHANG Ying

(SchoolofInformation,LiaoningUniversity,Shenyang110036,China)

With the increase of hop,delay of WMN began to increase,throughput began to reduce,and the QoS is also difficult to guarantee.In numerous solutions to solve these problems,the channel allocation strategy based on multi-channel multi-interface technology can well solve the interference and the transmission rate problems in traditional WMN.But at present the study of multi-channel WMN tend to ignore the premise of mutual communication between nodes-connectivity.On the basis of the original breadth first search(BFS) algorithm,this paper put forward the dynamic fixed channel allocation(DFCA) algorithm.On the premise of guarantee connectivity,the algorithm allocated fixed channel for each node dynamically,reduced the interference between links,and improved the transmission efficiency.The condition which nodes are new or failure was also considered.Simulation results demonstrate that the algorithm of DFCA can improve the throughput than traditional algorithms in the case of large sending rate and more data flow.

Mesh network;multi-channel;multi-interface;dynamic allocation;fixed channel

TP 393

A

1000-5846(2017)04-0294-08

2017-09-01

遼寧省教育廳科學(xué)研究一般項(xiàng)目資助(項(xiàng)目編號(hào)：L2015204)

尹鳳杰(1965-)，女，博士，教授，從事無(wú)線網(wǎng)絡(luò)和通信網(wǎng)絡(luò)優(yōu)化控制研究；梅丙乾，男，碩士研究生；楊暉，女，碩士，副教授；張穎，女，碩士，講師.