一種基于最小生成樹的無(wú)線多跳網(wǎng)絡(luò)信道分配算法

王偉

摘 要：在無(wú)線多跳網(wǎng)絡(luò)環(huán)境下，提出了一種信道分配算法，該算法可優(yōu)先考慮最小生成樹上的可用信道，為每個(gè)節(jié)點(diǎn)分配信道資源，然后考慮利用生成樹外其他可用鏈路為節(jié)點(diǎn)提供信道資源，以提高吞吐量。該算法通過(guò)考慮每個(gè)用戶的通信需求，可充分利用空閑信道資源。仿真結(jié)果顯示，相比于不考慮最小生成樹外鏈路時(shí)，本算法可有效地提高網(wǎng)絡(luò)整體的吞吐量。

關(guān)鍵詞：信道分配；無(wú)線多跳網(wǎng)絡(luò)；最小生成樹；頻譜利用

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2014）10-00-04

0 引 言

在無(wú)線多跳網(wǎng)絡(luò)中，包括無(wú)線自組織網(wǎng)絡(luò)、無(wú)線mesh網(wǎng)絡(luò)和無(wú)線傳感器網(wǎng)絡(luò)，各節(jié)點(diǎn)既可以作為數(shù)據(jù)的終端節(jié)點(diǎn)， 也可以是網(wǎng)絡(luò)的路由節(jié)點(diǎn)。無(wú)線鏈路動(dòng)態(tài)、時(shí)變和丟失特性，導(dǎo)致無(wú)線鏈路質(zhì)量較差且穩(wěn)定性較低，這對(duì)提高無(wú)線多跳網(wǎng)絡(luò)的吞吐量和傳輸可靠性提出了挑戰(zhàn)[1，2]。

1 信道分配

移動(dòng)通信系統(tǒng)發(fā)展至今信道分配技術(shù)一直都是熱門話題，一個(gè)好的信道分配算法可以在特定的服務(wù)等級(jí)下（包括鏈路質(zhì)量，新呼叫阻塞概率和切換阻塞概率）產(chǎn)生很高的頻譜利用率。所謂信道分配是指在采用信道復(fù)用技術(shù)的小區(qū)制蜂窩移動(dòng)通信系統(tǒng)中，在多信道共用的情況下。為每個(gè)小區(qū)的通信設(shè)備安排多少可用信道。信道分配的目的是如何使頻譜利用率更高，信道分配的方式主要有三種：固定信道分配、動(dòng)態(tài)信道分配和混合信道分配。

圖1所示是信道分配技術(shù)的一般方案圖。

圖1 信道分配方案

固定信道分配[3]（ Fixed Channel Assignment，F(xiàn)CA）就是把所有的信道分成幾個(gè)組，每一組固定地分配給某個(gè)小區(qū)。固定的信道分配策略在小區(qū)業(yè)務(wù)量小的時(shí)候會(huì)造成資源浪費(fèi)，同時(shí)由于資源的平均分配會(huì)使得業(yè)務(wù)量大的小區(qū)通話阻塞率高。但是可以采用多種從相鄰小區(qū)借用信道的方法降低這些阻塞概率。其中最基本的方法便是簡(jiǎn)單的借用，即移動(dòng)臺(tái)能從相鄰小區(qū)分配到一個(gè)信道。一旦一個(gè)信道被借用，所有在共道復(fù)用距離內(nèi)的其他小區(qū)將被禁止使用這個(gè)信道。這在大業(yè)務(wù)量的情況下資源效率將會(huì)降低，信道利用率甚至不如FCA。利用混合借用機(jī)制可以部分地解決這類問題?；旌闲诺婪峙涫前逊峙浣o一個(gè)小區(qū)的信道分成兩組：小區(qū)自己所使用的信道為一組，可以被借用的信道為另一組。

動(dòng)態(tài)信道分配[4] （Dynamic Channel Assignment，DCA）把所有的信道組成一個(gè)緩存池，當(dāng)鄰近小區(qū)的信道未分配時(shí)，可以借用給別的小區(qū)使用，以達(dá)到資源的動(dòng)態(tài)分配，提高資源利用率。DCA可以分為集中式DCA，分布式DCA和完全分布式DCA。集中式DCA方案[5]為了進(jìn)行信道分配需要完整的系統(tǒng)信息和控制機(jī)制，它能在理論上提供最好的性能，但是大量的運(yùn)算以及各基站之間的通信導(dǎo)致額外的系統(tǒng)等待時(shí)間使集中式DCA方案實(shí)用效率較低，盡管如此，它能為更加實(shí)用的分布式DCA提供參考比較。完全分布式DCA[6]是另外一種極端，不需要網(wǎng)絡(luò)規(guī)劃或基站問的通信，如DECT系統(tǒng)（Digital Enhanced Cordless Telecommunications System），它們依賴于被動(dòng)監(jiān)視每個(gè)基站的空閑信道，允許小區(qū)占用任意一個(gè)被認(rèn)為有足夠載波干擾比的空閑信道。分布式DCA方案又分為動(dòng)態(tài)資源占用和簡(jiǎn)單動(dòng)態(tài)信道分配。

混合信道分配[7] （Hybrid Channel Assignment，HCA），此算法綜合了固定信道分配和動(dòng)態(tài)信道分配方法，即每個(gè)小區(qū)分配一組固定的信道。另一組信道儲(chǔ)備用于靈活的動(dòng)態(tài)信道分配。預(yù)定的分配方法依賴于已知的業(yè)務(wù)方式的改變，這些靈活的信道分給那些預(yù)定的小區(qū)以解決那些業(yè)務(wù)方式的可預(yù)見的變化。使用預(yù)測(cè)的分配方式，每個(gè)基站的業(yè)務(wù)量被持續(xù)地或周期地檢測(cè)，然后信道根據(jù)這些測(cè)量值分配給小區(qū)。實(shí)際上HCA是FCA和DCA兩者結(jié)合起來(lái)的產(chǎn)物，故稱混合信道分配。

2 算法描述

為了充分利用無(wú)線頻譜，需要有一個(gè)既能增加用戶容量又能減小干擾頻率信道復(fù)用方案。根據(jù)之前介紹的三種信道分配策略，本節(jié)提出一種混合式信道分配算法，即一種基于用戶的信道分配算法，根據(jù)網(wǎng)絡(luò)拓?fù)錁?gòu)造最小生成樹并且在分配信道資源時(shí)優(yōu)先考慮生成樹內(nèi)的鏈路，盡可能滿足節(jié)點(diǎn)的通信需求，以提高網(wǎng)絡(luò)整體吞吐量。

2.1 構(gòu)造最小生成樹

現(xiàn)有構(gòu)造最小生成樹的算法主要有兩種：Prim算法[8]和Kruskal算法[9]。這兩種方法都能在連通圖中構(gòu)造最小生成樹，與Prim算法不同，Kruskal算法先根據(jù)邊的權(quán)值進(jìn)行排序再進(jìn)行構(gòu)造最小生成樹，Prim算法在構(gòu)造過(guò)程中需要對(duì)權(quán)重邊做多次排序，而Kruskal算法只需進(jìn)行一次排序，因此Kruskal算法的效率要優(yōu)于Prim算法。Kruskal算法是一種按照邊的權(quán)值遞增的順序構(gòu)造最小生成樹的方法，其基本思想是：設(shè)無(wú)向連通網(wǎng)為G=（V，E），設(shè)G的最小生成樹為T，其初態(tài)為T=（V，{}），即初始時(shí)，最小生成樹T由圖G中的n個(gè)頂點(diǎn)構(gòu)成，頂點(diǎn)之間沒有一條邊，這樣T中各個(gè)頂點(diǎn)各自構(gòu)成一個(gè)連通分量。然后，按照邊的權(quán)值由小到大的順序，考察G的邊集E中的各條邊。若被考察的邊的兩個(gè)頂點(diǎn)屬于T的兩個(gè)不同的連通分量，則將此邊作為最小生成樹的邊加入到T中，同時(shí)把兩個(gè)連通分量連接為一個(gè)連通分量；若被考察邊的兩個(gè)頂點(diǎn)屬于同一個(gè)連通分量，則舍去此邊，以免造成回路，以此類推，當(dāng)T中的連通分量個(gè)數(shù)為1時(shí)，此連通分量即為G的一棵最小生成樹。

本文采用Kruskal算法進(jìn)行最小生成樹的構(gòu)造，其具體過(guò)程如圖2所示。首先，按照互通網(wǎng)中邊的權(quán)值由小到大的順序，不斷選取當(dāng)前未被選取的邊集中權(quán)值最小的邊，直至構(gòu)成最小生成樹。

圖2 Kruskal算法構(gòu)造最小生成樹過(guò)程

2.2 信道分配算法

在無(wú)線多跳接入網(wǎng)中，網(wǎng)絡(luò)中每條鏈路的可用信道不同，每個(gè)節(jié)點(diǎn)不能同時(shí)收發(fā)，用戶需求可以用信道數(shù)量來(lái)表示，假定節(jié)點(diǎn)的上行和下行業(yè)務(wù)需求相同。在這樣一個(gè)靜態(tài)網(wǎng)絡(luò)中，首先構(gòu)造出一個(gè)最小生成樹，由于最小生成樹中鏈路權(quán)值較小，所以優(yōu)先利用生成樹內(nèi)鏈路分配信道資源能夠有效提高系統(tǒng)整體的性能。在無(wú)線通信網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)都能和與其相距一定范圍內(nèi)的節(jié)點(diǎn)進(jìn)行通信，若只考慮最小生成樹上的信道會(huì)造成一定的信道資源浪費(fèi)，也就是說(shuō)除了最小生成樹以外，還存在許多其他可用信道，這里我們保證優(yōu)先利用最小生成樹的同時(shí)，也要充分利用這些信道資源。所以，優(yōu)先考慮最小生成樹分配信道后，根據(jù)節(jié)點(diǎn)的通信需求是否得到滿足進(jìn)而決定是否通過(guò)給其他符合條件的鏈路分配信道，以滿足節(jié)點(diǎn)需求并達(dá)到提高網(wǎng)絡(luò)吞吐量的目的。這里最小生成樹外鏈路要符合的條件有：與此節(jié)點(diǎn)相連的節(jié)點(diǎn)上還存在可用信道，否則無(wú)法進(jìn)行通信；與此節(jié)點(diǎn)相連的節(jié)點(diǎn)跳數(shù)少于此節(jié)點(diǎn)，否則會(huì)出現(xiàn)延時(shí)太大，以至于影響通信質(zhì)量。

根據(jù)上述Kruskal算法，針對(duì)圖3所示的網(wǎng)絡(luò)拓?fù)?，即一個(gè)AP和8個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中構(gòu)造最小生成樹，其結(jié)果如圖4所示（假設(shè)每條鏈路有三條可用信道，節(jié)點(diǎn)下方標(biāo)注節(jié)點(diǎn)的信道需求）。

圖3 網(wǎng)絡(luò)拓?fù)涫疽鈭D

圖4 最小生成樹示意圖

完成構(gòu)造最小生成樹后，我們根據(jù)節(jié)點(diǎn)的通信需求進(jìn)行信道資源的分配，如圖5所示。這里我們按由上到下，由左到右的順序來(lái)依次分配信道。這里以節(jié)點(diǎn)e和節(jié)點(diǎn)f為例來(lái)說(shuō)明提出的信道分配算法。

節(jié)點(diǎn)e：由于優(yōu)先考慮最小生成樹上的信道，所以節(jié)點(diǎn)e的路徑為e-a-AP，在這里，我們可以看到，即使鏈路（a，AP）已經(jīng)給節(jié)點(diǎn)a分配了一個(gè)信道，最小生成樹仍然可以完全滿足這個(gè)節(jié)點(diǎn)的需求，所以我們查找鏈路（e，a）和（a，AP）上的可用信道，為節(jié)點(diǎn)e分配（e，a）上的可用信道13，和（a，AP）上的可用信道1。由于節(jié)點(diǎn)e的需求已經(jīng)得到滿足，所以這里不需要再考慮為它分配生成樹外鏈路上的可用信道。

圖5 節(jié)點(diǎn)信道分配示意圖

節(jié)點(diǎn)f：與節(jié)點(diǎn)e類似，首先考慮最小生成樹上的信道資源，節(jié)點(diǎn)f的路徑為f-g-c-AP，由于節(jié)點(diǎn)c和節(jié)點(diǎn)g已經(jīng)先于節(jié)點(diǎn)f分配了信道，所以在鏈路（c，AP）上只剩下一條信道（信道9），所以將這條信道分配給節(jié)點(diǎn)f，并且在鏈路（g，f）和鏈路（f，g）上查找一條可用信道，分別是信道29和信道22分配給節(jié)點(diǎn)f。此時(shí)節(jié)點(diǎn)f的需求并沒有得到滿足，所以我們需要利用生成樹外鏈路來(lái)提供信道資源。根據(jù)之前所述的最小生成樹需要符合的條件，首先考慮與f相連的鏈路，鏈路（f，e）符合條件，而節(jié)點(diǎn)e所在的路徑只能提供一條可用信道，所以在鏈路（f，e）、鏈路（e，a）和鏈路（a，AP）上查找一條可用信道，分別為19，14，3分配給節(jié)點(diǎn)f。此時(shí)節(jié)點(diǎn)f的需求仍然沒有滿足，而鏈路（f，g）上還存在可用信道，所以接著查找與節(jié)點(diǎn)g相連的鏈路，可以看到鏈路（g，b）也滿足要求而節(jié)點(diǎn)b所在的路徑上還存在兩條可用信道，所以，分別將鏈路（g，b）和鏈路（b，AP）上的信道25，26和5，6分配給節(jié)點(diǎn)f。此時(shí)，三條跳數(shù)相同的候選路徑聯(lián)合為節(jié)點(diǎn)f提供傳輸服務(wù)，滿足了節(jié)點(diǎn)f的通信需求。

根據(jù)上述算法描述，本算法為節(jié)點(diǎn)分配信道資源的具體流程如圖6所示。

圖6 算法流程圖

3 仿真分析

3.1 網(wǎng)絡(luò)拓?fù)?/p>

本節(jié)采用MATLAB軟件進(jìn)行仿真，仿真場(chǎng)景為在一塊1km×1 km的空間內(nèi)，節(jié)點(diǎn)位置進(jìn)行隨機(jī)部署，節(jié)點(diǎn)個(gè)數(shù)可以根據(jù)仿真需要進(jìn)行調(diào)整。由于節(jié)點(diǎn)之間進(jìn)行的是無(wú)線通信，所以規(guī)定每個(gè)節(jié)點(diǎn)可以和與之距離250 m之內(nèi)的所有節(jié)點(diǎn)通信，因此，在這些能夠通信的節(jié)點(diǎn)間建立鏈路，并將這些信息存儲(chǔ)在鄰接矩陣中。

按照信道分配算法的步驟，針對(duì)網(wǎng)絡(luò)拓?fù)錁?gòu)造最小生成樹并添加最小生成樹外鏈路，如圖7所示。其中，粗實(shí)線為最小生成樹中包含的鏈路，而虛線部分為添加的最小生成樹外的鏈路。

圖7 網(wǎng)絡(luò)拓?fù)鋱D（40個(gè)節(jié)點(diǎn)）

3.2 仿真分析比較

當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)一定，改變每條鏈路上的可用信道時(shí)，分別對(duì)網(wǎng)絡(luò)吞吐量進(jìn)行仿真。設(shè)定網(wǎng)絡(luò)中有60個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)最大的業(yè)務(wù)需求為4，改變每條鏈路上的可用信道數(shù)目從10個(gè)到30個(gè)，網(wǎng)絡(luò)吞吐量仿真結(jié)果如圖8所示。圖中每組柱狀圖中第一條為理想情況下，當(dāng)所有節(jié)點(diǎn)的需求都被滿足，整個(gè)網(wǎng)絡(luò)所獲得的吞吐量；第二條為采用本文提出的算法進(jìn)行信道分配得到的網(wǎng)絡(luò)吞吐量；第三條為不考慮最小生成樹外鏈路信道資源時(shí)得到的網(wǎng)絡(luò)吞吐量；第四條則為前兩者的差值。由仿真結(jié)果可以看出這種算法能有效提高網(wǎng)絡(luò)的吞吐量。當(dāng)每條鏈路上的可用信道太少時(shí)，所有鏈路上的信道使用情況已接近飽和，所以吞吐量提高并不明顯，但在這種情況下吞吐量仍有一定的增長(zhǎng)。另一方面，當(dāng)每條鏈路上的可用信道數(shù)目很多時(shí)，即使不考慮生成樹外的鏈路，用戶需求的滿足狀況也已經(jīng)接近理想狀態(tài)，所以能夠提高的空間并不大，而我們提出的算法同樣能使其得到一定提高。由此可見，這種算法是能夠提升包含60個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)的性能。

當(dāng)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)有20個(gè)可用信道，每個(gè)節(jié)點(diǎn)最大的業(yè)務(wù)需求為4，網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)從40個(gè)到80個(gè)，分別對(duì)網(wǎng)絡(luò)吞吐量進(jìn)行仿真，結(jié)果如圖9所示。由仿真結(jié)果可以看出，不管節(jié)點(diǎn)數(shù)如何發(fā)生變化，我們提出的算法都有效提升了網(wǎng)絡(luò)整體的吞吐量。但當(dāng)節(jié)點(diǎn)個(gè)數(shù)較少時(shí)，由節(jié)點(diǎn)分布比較稀疏，而節(jié)點(diǎn)之間無(wú)線通信的距離限制，相對(duì)于分布比較稠密的網(wǎng)絡(luò)來(lái)說(shuō)，網(wǎng)絡(luò)中存在的可用鏈路數(shù)比較少，那么在添加生成樹外的鏈路時(shí)，可以選擇的個(gè)數(shù)也相對(duì)降低。所以，當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)較少的時(shí)，吞吐量的提升也相對(duì)比較小。而圖中吞吐量之差并不是線性增長(zhǎng)的趨勢(shì)，這是因?yàn)榫W(wǎng)絡(luò)中拓?fù)渖傻臅r(shí)候，節(jié)點(diǎn)的分布并不是完全均勻的，而是隨機(jī)分布的，所以也會(huì)有一定因素的影響，但總的來(lái)說(shuō)節(jié)點(diǎn)個(gè)數(shù)相對(duì)多的時(shí)候吞吐量的差值還是比節(jié)點(diǎn)個(gè)數(shù)少時(shí)較高，而且不管節(jié)點(diǎn)個(gè)數(shù)如何變化，系統(tǒng)的吞吐量都有顯著的提高。

圖8 不同可用信道數(shù)對(duì)應(yīng)的網(wǎng)絡(luò)吞吐量（60個(gè)節(jié)點(diǎn)）

圖9 不同節(jié)點(diǎn)數(shù)對(duì)應(yīng)的網(wǎng)絡(luò)吞吐量（20個(gè)可用信道）

4 結(jié) 語(yǔ)

混合信道分配策略既降低了固定信道分配策略的頻譜規(guī)劃的復(fù)雜性， 又能夠根據(jù)通信業(yè)務(wù)的實(shí)際發(fā)生量以調(diào)整信道的使用情況， 因此混合信道分配策略是一種比較實(shí)際可行的方案。

本文基于混合信道分配策略在無(wú)線多跳接入網(wǎng)環(huán)境下提出了一種應(yīng)用最小生成樹算法的信道分配算法，并且針對(duì)不同節(jié)點(diǎn)數(shù)和不同可用信道情況分別進(jìn)行了仿真比較。仿真結(jié)果表明，這種無(wú)線多跳接入網(wǎng)信道分配算法確實(shí)能夠提高信道的吞吐量。

參考文獻(xiàn)

[1]哈米德·S·A，哈薩尼·H·S，高原·G.無(wú)線多跳網(wǎng)絡(luò)導(dǎo)論[M]. 紐約：Springer New York，2013.

[2]納拉因·B，拍拉特·V·K，庫(kù)馬爾·S·P. 路由協(xié)議在無(wú)線多跳網(wǎng)絡(luò)擁塞的控制節(jié)奏和性能評(píng)價(jià)[J].國(guó)際計(jì)算機(jī)雜志，2010（11）：291-298.

[3]設(shè)拉子·S，阿德邁爾·H.將固定信道分配使用新的動(dòng)態(tài)規(guī)劃方法在蜂窩無(wú)線網(wǎng)絡(luò)明顯構(gòu)造[J].計(jì)算機(jī)與電器工程，2005（4）：303-333.

[4]莫·S，伊薩蘭·I，阿明·M·R.動(dòng)態(tài)信道分配在移動(dòng)蜂窩網(wǎng)絡(luò)中[J].離散數(shù)學(xué)和密碼學(xué)，2008（11）： 705-714.

[5]瑞麗維拉·A，戈帕拉·K，遲麗爾·T.集中式信道分配和多信道無(wú)線Mesh網(wǎng)絡(luò)的路由算法應(yīng)用[J].ACM Sigmobile，2004（4）： 50-65.

[6]KO·B，米斯娜·V，帕德萊·J.在多無(wú)線網(wǎng)狀網(wǎng)絡(luò)相比下的對(duì)應(yīng)頻率[A].802.11分布式信道分配的模式無(wú)線通信與網(wǎng)絡(luò)會(huì)議[C]，2007： 3978-3983.

[7]嘉·Y，蕭萬(wàn)長(zhǎng)，河岸·A.自適應(yīng)混合信道分配的無(wú)線移動(dòng)網(wǎng)絡(luò)應(yīng)用[A].遺傳算法混合智能構(gòu)成系統(tǒng)（HIS）第十一屆國(guó)際會(huì)議[C]，2011：511-516.

[8]楊成輝，如川軍.基于基本Prim算法的通信網(wǎng)絡(luò)仿真研究[J].信息技術(shù)與應(yīng)用，2010（3）：3-6.

[9]鮑勃·P·C，希達(dá)·C·P.廣義最小生成樹問題和對(duì)其高效算法的理解[A].應(yīng)用數(shù)學(xué)國(guó)際會(huì)議[C]，2004：23-26.

根據(jù)上述Kruskal算法，針對(duì)圖3所示的網(wǎng)絡(luò)拓?fù)?，即一個(gè)AP和8個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中構(gòu)造最小生成樹，其結(jié)果如圖4所示（假設(shè)每條鏈路有三條可用信道，節(jié)點(diǎn)下方標(biāo)注節(jié)點(diǎn)的信道需求）。

圖3 網(wǎng)絡(luò)拓?fù)涫疽鈭D

圖4 最小生成樹示意圖

完成構(gòu)造最小生成樹后，我們根據(jù)節(jié)點(diǎn)的通信需求進(jìn)行信道資源的分配，如圖5所示。這里我們按由上到下，由左到右的順序來(lái)依次分配信道。這里以節(jié)點(diǎn)e和節(jié)點(diǎn)f為例來(lái)說(shuō)明提出的信道分配算法。

節(jié)點(diǎn)e：由于優(yōu)先考慮最小生成樹上的信道，所以節(jié)點(diǎn)e的路徑為e-a-AP，在這里，我們可以看到，即使鏈路（a，AP）已經(jīng)給節(jié)點(diǎn)a分配了一個(gè)信道，最小生成樹仍然可以完全滿足這個(gè)節(jié)點(diǎn)的需求，所以我們查找鏈路（e，a）和（a，AP）上的可用信道，為節(jié)點(diǎn)e分配（e，a）上的可用信道13，和（a，AP）上的可用信道1。由于節(jié)點(diǎn)e的需求已經(jīng)得到滿足，所以這里不需要再考慮為它分配生成樹外鏈路上的可用信道。

圖5 節(jié)點(diǎn)信道分配示意圖

節(jié)點(diǎn)f：與節(jié)點(diǎn)e類似，首先考慮最小生成樹上的信道資源，節(jié)點(diǎn)f的路徑為f-g-c-AP，由于節(jié)點(diǎn)c和節(jié)點(diǎn)g已經(jīng)先于節(jié)點(diǎn)f分配了信道，所以在鏈路（c，AP）上只剩下一條信道（信道9），所以將這條信道分配給節(jié)點(diǎn)f，并且在鏈路（g，f）和鏈路（f，g）上查找一條可用信道，分別是信道29和信道22分配給節(jié)點(diǎn)f。此時(shí)節(jié)點(diǎn)f的需求并沒有得到滿足，所以我們需要利用生成樹外鏈路來(lái)提供信道資源。根據(jù)之前所述的最小生成樹需要符合的條件，首先考慮與f相連的鏈路，鏈路（f，e）符合條件，而節(jié)點(diǎn)e所在的路徑只能提供一條可用信道，所以在鏈路（f，e）、鏈路（e，a）和鏈路（a，AP）上查找一條可用信道，分別為19，14，3分配給節(jié)點(diǎn)f。此時(shí)節(jié)點(diǎn)f的需求仍然沒有滿足，而鏈路（f，g）上還存在可用信道，所以接著查找與節(jié)點(diǎn)g相連的鏈路，可以看到鏈路（g，b）也滿足要求而節(jié)點(diǎn)b所在的路徑上還存在兩條可用信道，所以，分別將鏈路（g，b）和鏈路（b，AP）上的信道25，26和5，6分配給節(jié)點(diǎn)f。此時(shí)，三條跳數(shù)相同的候選路徑聯(lián)合為節(jié)點(diǎn)f提供傳輸服務(wù)，滿足了節(jié)點(diǎn)f的通信需求。

根據(jù)上述算法描述，本算法為節(jié)點(diǎn)分配信道資源的具體流程如圖6所示。

圖6 算法流程圖

3 仿真分析

3.1 網(wǎng)絡(luò)拓?fù)?/p>

本節(jié)采用MATLAB軟件進(jìn)行仿真，仿真場(chǎng)景為在一塊1km×1 km的空間內(nèi)，節(jié)點(diǎn)位置進(jìn)行隨機(jī)部署，節(jié)點(diǎn)個(gè)數(shù)可以根據(jù)仿真需要進(jìn)行調(diào)整。由于節(jié)點(diǎn)之間進(jìn)行的是無(wú)線通信，所以規(guī)定每個(gè)節(jié)點(diǎn)可以和與之距離250 m之內(nèi)的所有節(jié)點(diǎn)通信，因此，在這些能夠通信的節(jié)點(diǎn)間建立鏈路，并將這些信息存儲(chǔ)在鄰接矩陣中。

按照信道分配算法的步驟，針對(duì)網(wǎng)絡(luò)拓?fù)錁?gòu)造最小生成樹并添加最小生成樹外鏈路，如圖7所示。其中，粗實(shí)線為最小生成樹中包含的鏈路，而虛線部分為添加的最小生成樹外的鏈路。

圖7 網(wǎng)絡(luò)拓?fù)鋱D（40個(gè)節(jié)點(diǎn)）

3.2 仿真分析比較

當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)一定，改變每條鏈路上的可用信道時(shí)，分別對(duì)網(wǎng)絡(luò)吞吐量進(jìn)行仿真。設(shè)定網(wǎng)絡(luò)中有60個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)最大的業(yè)務(wù)需求為4，改變每條鏈路上的可用信道數(shù)目從10個(gè)到30個(gè)，網(wǎng)絡(luò)吞吐量仿真結(jié)果如圖8所示。圖中每組柱狀圖中第一條為理想情況下，當(dāng)所有節(jié)點(diǎn)的需求都被滿足，整個(gè)網(wǎng)絡(luò)所獲得的吞吐量；第二條為采用本文提出的算法進(jìn)行信道分配得到的網(wǎng)絡(luò)吞吐量；第三條為不考慮最小生成樹外鏈路信道資源時(shí)得到的網(wǎng)絡(luò)吞吐量；第四條則為前兩者的差值。由仿真結(jié)果可以看出這種算法能有效提高網(wǎng)絡(luò)的吞吐量。當(dāng)每條鏈路上的可用信道太少時(shí)，所有鏈路上的信道使用情況已接近飽和，所以吞吐量提高并不明顯，但在這種情況下吞吐量仍有一定的增長(zhǎng)。另一方面，當(dāng)每條鏈路上的可用信道數(shù)目很多時(shí)，即使不考慮生成樹外的鏈路，用戶需求的滿足狀況也已經(jīng)接近理想狀態(tài)，所以能夠提高的空間并不大，而我們提出的算法同樣能使其得到一定提高。由此可見，這種算法是能夠提升包含60個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)的性能。

當(dāng)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)有20個(gè)可用信道，每個(gè)節(jié)點(diǎn)最大的業(yè)務(wù)需求為4，網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)從40個(gè)到80個(gè)，分別對(duì)網(wǎng)絡(luò)吞吐量進(jìn)行仿真，結(jié)果如圖9所示。由仿真結(jié)果可以看出，不管節(jié)點(diǎn)數(shù)如何發(fā)生變化，我們提出的算法都有效提升了網(wǎng)絡(luò)整體的吞吐量。但當(dāng)節(jié)點(diǎn)個(gè)數(shù)較少時(shí)，由節(jié)點(diǎn)分布比較稀疏，而節(jié)點(diǎn)之間無(wú)線通信的距離限制，相對(duì)于分布比較稠密的網(wǎng)絡(luò)來(lái)說(shuō)，網(wǎng)絡(luò)中存在的可用鏈路數(shù)比較少，那么在添加生成樹外的鏈路時(shí)，可以選擇的個(gè)數(shù)也相對(duì)降低。所以，當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)較少的時(shí)，吞吐量的提升也相對(duì)比較小。而圖中吞吐量之差并不是線性增長(zhǎng)的趨勢(shì)，這是因?yàn)榫W(wǎng)絡(luò)中拓?fù)渖傻臅r(shí)候，節(jié)點(diǎn)的分布并不是完全均勻的，而是隨機(jī)分布的，所以也會(huì)有一定因素的影響，但總的來(lái)說(shuō)節(jié)點(diǎn)個(gè)數(shù)相對(duì)多的時(shí)候吞吐量的差值還是比節(jié)點(diǎn)個(gè)數(shù)少時(shí)較高，而且不管節(jié)點(diǎn)個(gè)數(shù)如何變化，系統(tǒng)的吞吐量都有顯著的提高。

圖8 不同可用信道數(shù)對(duì)應(yīng)的網(wǎng)絡(luò)吞吐量（60個(gè)節(jié)點(diǎn)）

圖9 不同節(jié)點(diǎn)數(shù)對(duì)應(yīng)的網(wǎng)絡(luò)吞吐量（20個(gè)可用信道）

4 結(jié) 語(yǔ)

混合信道分配策略既降低了固定信道分配策略的頻譜規(guī)劃的復(fù)雜性， 又能夠根據(jù)通信業(yè)務(wù)的實(shí)際發(fā)生量以調(diào)整信道的使用情況， 因此混合信道分配策略是一種比較實(shí)際可行的方案。

本文基于混合信道分配策略在無(wú)線多跳接入網(wǎng)環(huán)境下提出了一種應(yīng)用最小生成樹算法的信道分配算法，并且針對(duì)不同節(jié)點(diǎn)數(shù)和不同可用信道情況分別進(jìn)行了仿真比較。仿真結(jié)果表明，這種無(wú)線多跳接入網(wǎng)信道分配算法確實(shí)能夠提高信道的吞吐量。

參考文獻(xiàn)

[1]哈米德·S·A，哈薩尼·H·S，高原·G.無(wú)線多跳網(wǎng)絡(luò)導(dǎo)論[M]. 紐約：Springer New York，2013.

[2]納拉因·B，拍拉特·V·K，庫(kù)馬爾·S·P. 路由協(xié)議在無(wú)線多跳網(wǎng)絡(luò)擁塞的控制節(jié)奏和性能評(píng)價(jià)[J].國(guó)際計(jì)算機(jī)雜志，2010（11）：291-298.

[3]設(shè)拉子·S，阿德邁爾·H.將固定信道分配使用新的動(dòng)態(tài)規(guī)劃方法在蜂窩無(wú)線網(wǎng)絡(luò)明顯構(gòu)造[J].計(jì)算機(jī)與電器工程，2005（4）：303-333.

[4]莫·S，伊薩蘭·I，阿明·M·R.動(dòng)態(tài)信道分配在移動(dòng)蜂窩網(wǎng)絡(luò)中[J].離散數(shù)學(xué)和密碼學(xué)，2008（11）： 705-714.

[5]瑞麗維拉·A，戈帕拉·K，遲麗爾·T.集中式信道分配和多信道無(wú)線Mesh網(wǎng)絡(luò)的路由算法應(yīng)用[J].ACM Sigmobile，2004（4）： 50-65.

[6]KO·B，米斯娜·V，帕德萊·J.在多無(wú)線網(wǎng)狀網(wǎng)絡(luò)相比下的對(duì)應(yīng)頻率[A].802.11分布式信道分配的模式無(wú)線通信與網(wǎng)絡(luò)會(huì)議[C]，2007： 3978-3983.

[7]嘉·Y，蕭萬(wàn)長(zhǎng)，河岸·A.自適應(yīng)混合信道分配的無(wú)線移動(dòng)網(wǎng)絡(luò)應(yīng)用[A].遺傳算法混合智能構(gòu)成系統(tǒng)（HIS）第十一屆國(guó)際會(huì)議[C]，2011：511-516.

[8]楊成輝，如川軍.基于基本Prim算法的通信網(wǎng)絡(luò)仿真研究[J].信息技術(shù)與應(yīng)用，2010（3）：3-6.

[9]鮑勃·P·C，希達(dá)·C·P.廣義最小生成樹問題和對(duì)其高效算法的理解[A].應(yīng)用數(shù)學(xué)國(guó)際會(huì)議[C]，2004：23-26.

根據(jù)上述Kruskal算法，針對(duì)圖3所示的網(wǎng)絡(luò)拓?fù)?，即一個(gè)AP和8個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中構(gòu)造最小生成樹，其結(jié)果如圖4所示（假設(shè)每條鏈路有三條可用信道，節(jié)點(diǎn)下方標(biāo)注節(jié)點(diǎn)的信道需求）。

圖3 網(wǎng)絡(luò)拓?fù)涫疽鈭D

圖4 最小生成樹示意圖

完成構(gòu)造最小生成樹后，我們根據(jù)節(jié)點(diǎn)的通信需求進(jìn)行信道資源的分配，如圖5所示。這里我們按由上到下，由左到右的順序來(lái)依次分配信道。這里以節(jié)點(diǎn)e和節(jié)點(diǎn)f為例來(lái)說(shuō)明提出的信道分配算法。

節(jié)點(diǎn)e：由于優(yōu)先考慮最小生成樹上的信道，所以節(jié)點(diǎn)e的路徑為e-a-AP，在這里，我們可以看到，即使鏈路（a，AP）已經(jīng)給節(jié)點(diǎn)a分配了一個(gè)信道，最小生成樹仍然可以完全滿足這個(gè)節(jié)點(diǎn)的需求，所以我們查找鏈路（e，a）和（a，AP）上的可用信道，為節(jié)點(diǎn)e分配（e，a）上的可用信道13，和（a，AP）上的可用信道1。由于節(jié)點(diǎn)e的需求已經(jīng)得到滿足，所以這里不需要再考慮為它分配生成樹外鏈路上的可用信道。

圖5 節(jié)點(diǎn)信道分配示意圖

節(jié)點(diǎn)f：與節(jié)點(diǎn)e類似，首先考慮最小生成樹上的信道資源，節(jié)點(diǎn)f的路徑為f-g-c-AP，由于節(jié)點(diǎn)c和節(jié)點(diǎn)g已經(jīng)先于節(jié)點(diǎn)f分配了信道，所以在鏈路（c，AP）上只剩下一條信道（信道9），所以將這條信道分配給節(jié)點(diǎn)f，并且在鏈路（g，f）和鏈路（f，g）上查找一條可用信道，分別是信道29和信道22分配給節(jié)點(diǎn)f。此時(shí)節(jié)點(diǎn)f的需求并沒有得到滿足，所以我們需要利用生成樹外鏈路來(lái)提供信道資源。根據(jù)之前所述的最小生成樹需要符合的條件，首先考慮與f相連的鏈路，鏈路（f，e）符合條件，而節(jié)點(diǎn)e所在的路徑只能提供一條可用信道，所以在鏈路（f，e）、鏈路（e，a）和鏈路（a，AP）上查找一條可用信道，分別為19，14，3分配給節(jié)點(diǎn)f。此時(shí)節(jié)點(diǎn)f的需求仍然沒有滿足，而鏈路（f，g）上還存在可用信道，所以接著查找與節(jié)點(diǎn)g相連的鏈路，可以看到鏈路（g，b）也滿足要求而節(jié)點(diǎn)b所在的路徑上還存在兩條可用信道，所以，分別將鏈路（g，b）和鏈路（b，AP）上的信道25，26和5，6分配給節(jié)點(diǎn)f。此時(shí)，三條跳數(shù)相同的候選路徑聯(lián)合為節(jié)點(diǎn)f提供傳輸服務(wù)，滿足了節(jié)點(diǎn)f的通信需求。

根據(jù)上述算法描述，本算法為節(jié)點(diǎn)分配信道資源的具體流程如圖6所示。

圖6 算法流程圖

3 仿真分析

3.1 網(wǎng)絡(luò)拓?fù)?/p>

本節(jié)采用MATLAB軟件進(jìn)行仿真，仿真場(chǎng)景為在一塊1km×1 km的空間內(nèi)，節(jié)點(diǎn)位置進(jìn)行隨機(jī)部署，節(jié)點(diǎn)個(gè)數(shù)可以根據(jù)仿真需要進(jìn)行調(diào)整。由于節(jié)點(diǎn)之間進(jìn)行的是無(wú)線通信，所以規(guī)定每個(gè)節(jié)點(diǎn)可以和與之距離250 m之內(nèi)的所有節(jié)點(diǎn)通信，因此，在這些能夠通信的節(jié)點(diǎn)間建立鏈路，并將這些信息存儲(chǔ)在鄰接矩陣中。

按照信道分配算法的步驟，針對(duì)網(wǎng)絡(luò)拓?fù)錁?gòu)造最小生成樹并添加最小生成樹外鏈路，如圖7所示。其中，粗實(shí)線為最小生成樹中包含的鏈路，而虛線部分為添加的最小生成樹外的鏈路。

圖7 網(wǎng)絡(luò)拓?fù)鋱D（40個(gè)節(jié)點(diǎn)）

3.2 仿真分析比較

當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)一定，改變每條鏈路上的可用信道時(shí)，分別對(duì)網(wǎng)絡(luò)吞吐量進(jìn)行仿真。設(shè)定網(wǎng)絡(luò)中有60個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)最大的業(yè)務(wù)需求為4，改變每條鏈路上的可用信道數(shù)目從10個(gè)到30個(gè)，網(wǎng)絡(luò)吞吐量仿真結(jié)果如圖8所示。圖中每組柱狀圖中第一條為理想情況下，當(dāng)所有節(jié)點(diǎn)的需求都被滿足，整個(gè)網(wǎng)絡(luò)所獲得的吞吐量；第二條為采用本文提出的算法進(jìn)行信道分配得到的網(wǎng)絡(luò)吞吐量；第三條為不考慮最小生成樹外鏈路信道資源時(shí)得到的網(wǎng)絡(luò)吞吐量；第四條則為前兩者的差值。由仿真結(jié)果可以看出這種算法能有效提高網(wǎng)絡(luò)的吞吐量。當(dāng)每條鏈路上的可用信道太少時(shí)，所有鏈路上的信道使用情況已接近飽和，所以吞吐量提高并不明顯，但在這種情況下吞吐量仍有一定的增長(zhǎng)。另一方面，當(dāng)每條鏈路上的可用信道數(shù)目很多時(shí)，即使不考慮生成樹外的鏈路，用戶需求的滿足狀況也已經(jīng)接近理想狀態(tài)，所以能夠提高的空間并不大，而我們提出的算法同樣能使其得到一定提高。由此可見，這種算法是能夠提升包含60個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)的性能。

當(dāng)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)有20個(gè)可用信道，每個(gè)節(jié)點(diǎn)最大的業(yè)務(wù)需求為4，網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)從40個(gè)到80個(gè)，分別對(duì)網(wǎng)絡(luò)吞吐量進(jìn)行仿真，結(jié)果如圖9所示。由仿真結(jié)果可以看出，不管節(jié)點(diǎn)數(shù)如何發(fā)生變化，我們提出的算法都有效提升了網(wǎng)絡(luò)整體的吞吐量。但當(dāng)節(jié)點(diǎn)個(gè)數(shù)較少時(shí)，由節(jié)點(diǎn)分布比較稀疏，而節(jié)點(diǎn)之間無(wú)線通信的距離限制，相對(duì)于分布比較稠密的網(wǎng)絡(luò)來(lái)說(shuō)，網(wǎng)絡(luò)中存在的可用鏈路數(shù)比較少，那么在添加生成樹外的鏈路時(shí)，可以選擇的個(gè)數(shù)也相對(duì)降低。所以，當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)較少的時(shí)，吞吐量的提升也相對(duì)比較小。而圖中吞吐量之差并不是線性增長(zhǎng)的趨勢(shì)，這是因?yàn)榫W(wǎng)絡(luò)中拓?fù)渖傻臅r(shí)候，節(jié)點(diǎn)的分布并不是完全均勻的，而是隨機(jī)分布的，所以也會(huì)有一定因素的影響，但總的來(lái)說(shuō)節(jié)點(diǎn)個(gè)數(shù)相對(duì)多的時(shí)候吞吐量的差值還是比節(jié)點(diǎn)個(gè)數(shù)少時(shí)較高，而且不管節(jié)點(diǎn)個(gè)數(shù)如何變化，系統(tǒng)的吞吐量都有顯著的提高。

圖8 不同可用信道數(shù)對(duì)應(yīng)的網(wǎng)絡(luò)吞吐量（60個(gè)節(jié)點(diǎn)）

圖9 不同節(jié)點(diǎn)數(shù)對(duì)應(yīng)的網(wǎng)絡(luò)吞吐量（20個(gè)可用信道）

4 結(jié) 語(yǔ)

混合信道分配策略既降低了固定信道分配策略的頻譜規(guī)劃的復(fù)雜性， 又能夠根據(jù)通信業(yè)務(wù)的實(shí)際發(fā)生量以調(diào)整信道的使用情況， 因此混合信道分配策略是一種比較實(shí)際可行的方案。

本文基于混合信道分配策略在無(wú)線多跳接入網(wǎng)環(huán)境下提出了一種應(yīng)用最小生成樹算法的信道分配算法，并且針對(duì)不同節(jié)點(diǎn)數(shù)和不同可用信道情況分別進(jìn)行了仿真比較。仿真結(jié)果表明，這種無(wú)線多跳接入網(wǎng)信道分配算法確實(shí)能夠提高信道的吞吐量。

參考文獻(xiàn)

[1]哈米德·S·A，哈薩尼·H·S，高原·G.無(wú)線多跳網(wǎng)絡(luò)導(dǎo)論[M]. 紐約：Springer New York，2013.

[2]納拉因·B，拍拉特·V·K，庫(kù)馬爾·S·P. 路由協(xié)議在無(wú)線多跳網(wǎng)絡(luò)擁塞的控制節(jié)奏和性能評(píng)價(jià)[J].國(guó)際計(jì)算機(jī)雜志，2010（11）：291-298.

[3]設(shè)拉子·S，阿德邁爾·H.將固定信道分配使用新的動(dòng)態(tài)規(guī)劃方法在蜂窩無(wú)線網(wǎng)絡(luò)明顯構(gòu)造[J].計(jì)算機(jī)與電器工程，2005（4）：303-333.

[4]莫·S，伊薩蘭·I，阿明·M·R.動(dòng)態(tài)信道分配在移動(dòng)蜂窩網(wǎng)絡(luò)中[J].離散數(shù)學(xué)和密碼學(xué)，2008（11）： 705-714.

[5]瑞麗維拉·A，戈帕拉·K，遲麗爾·T.集中式信道分配和多信道無(wú)線Mesh網(wǎng)絡(luò)的路由算法應(yīng)用[J].ACM Sigmobile，2004（4）： 50-65.

[6]KO·B，米斯娜·V，帕德萊·J.在多無(wú)線網(wǎng)狀網(wǎng)絡(luò)相比下的對(duì)應(yīng)頻率[A].802.11分布式信道分配的模式無(wú)線通信與網(wǎng)絡(luò)會(huì)議[C]，2007： 3978-3983.

[7]嘉·Y，蕭萬(wàn)長(zhǎng)，河岸·A.自適應(yīng)混合信道分配的無(wú)線移動(dòng)網(wǎng)絡(luò)應(yīng)用[A].遺傳算法混合智能構(gòu)成系統(tǒng)（HIS）第十一屆國(guó)際會(huì)議[C]，2011：511-516.

[8]楊成輝，如川軍.基于基本Prim算法的通信網(wǎng)絡(luò)仿真研究[J].信息技術(shù)與應(yīng)用，2010（3）：3-6.

[9]鮑勃·P·C，希達(dá)·C·P.廣義最小生成樹問題和對(duì)其高效算法的理解[A].應(yīng)用數(shù)學(xué)國(guó)際會(huì)議[C]，2004：23-26.