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

引言

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

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ù)的一般方案圖。

固定信道分配(FixedChannelAssignment，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］(DynamicChannelAssignment，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是另外一種極端，不需要網(wǎng)絡(luò)規(guī)劃或基站問的通信，如DECT系統(tǒng)(DigitalEnhancedCordlessTelecommunicationsSystem),它們依賴于被動(dòng)監(jiān)視每個(gè)基站的空閑信道，允許小區(qū)占用任意一個(gè)被認(rèn)為有足夠載波干擾比的空閑信道。分布式DCA方案又分為動(dòng)態(tài)資源占用和簡(jiǎn)單動(dòng)態(tài)信道分配。

混合信道分配(HybridChannelAssignment,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é)合起來的產(chǎn)物，故稱混合信道分配。

2算法描述

為了充分利用無線頻譜，需要有一個(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算法四。這兩種方法都能在連通圖中構(gòu)造最小生成樹，與Prim算法不同，Kruskal算法先根據(jù)邊的權(quán)值進(jìn)行排序再進(jìn)行構(gòu)造最小生成樹，Prim算法在構(gòu)造過程中需要對(duì)權(quán)重邊做多次排序，而Kruskal算法只需進(jìn)行一次排序，因此

Kruskal算法的效率要優(yōu)于Prim算法。Kruskal算法是一種按照邊的權(quán)值遞增的順序構(gòu)造最小生成樹的方法，其基本思想是：設(shè)無向連通網(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)造，其具體過程如圖2所示。首先，按照互通網(wǎng)中邊的權(quán)值由小到大的順序，不斷選取當(dāng)前未被選取的邊集中權(quán)值最小的邊，直至構(gòu)成最小生成樹。

2.2信道分配算法

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

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

節(jié)點(diǎn)e:由于優(yōu)先考慮最小生成樹上的信道，所以節(jié)點(diǎn)e的路徑為e-a-AP,在這里，我們可以看到，即使鏈路(a,AP)已經(jīng)給節(jié)點(diǎn)a分配了一個(gè)信道，最小生成樹仍然可以完系統(tǒng)整體的性能。在無線通信網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)都能和與其全滿足這個(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的需求并沒有得到滿足，所以我們需要利用生成樹外鏈路來提供信道資源。根據(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所示。

C開始］）

圖6算法流程圖

3仿真分析

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

本節(jié)采用MATLAB軟件進(jìn)行仿真，仿真場(chǎng)景為在一塊1kmX1km的空間內(nèi)，節(jié)點(diǎn)位置進(jìn)行隨機(jī)部署，節(jié)點(diǎn)個(gè)數(shù)可以根據(jù)仿真需要進(jìn)行調(diào)整。由于節(jié)點(diǎn)之間進(jìn)行的是無線通信，所以規(guī)定每個(gè)節(jié)點(diǎn)可以和與之距離250m之內(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)之間無線通信的距離限制，相對(duì)于分布比較稠密的網(wǎng)絡(luò)來說，網(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ì)有一定因素的影響，但總的來說節(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é)語

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

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

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