無線網(wǎng)絡(luò)中提高接入公平性的信道分配算法

李雅婧

(山西省新聞出版廣電局監(jiān)管中心，山西 太原 030001)

頻譜是無線通信中的寶貴資源。目前可用的頻譜資源常被劃分為多條信道，采用固定的方式進(jìn)行信道分配。這種分配方法的頻譜利用率較低。對(duì)此有學(xué)者提出了認(rèn)知無線電的概念[1]。采用認(rèn)知無線電技術(shù)的設(shè)備可學(xué)習(xí)周圍環(huán)境，并根據(jù)環(huán)境動(dòng)態(tài)改變使用的頻譜、調(diào)制方式、發(fā)射機(jī)功率等相關(guān)參數(shù)，以提高通信性能。

無線網(wǎng)絡(luò)處在開放的環(huán)境中，網(wǎng)絡(luò)易被攻擊，節(jié)點(diǎn)也易被外界控制[2]。被外界控制的節(jié)點(diǎn)將成為網(wǎng)絡(luò)的惡意節(jié)點(diǎn)。惡意節(jié)點(diǎn)試圖長(zhǎng)期占用通信質(zhì)量較好的信道，使得其他節(jié)點(diǎn)失去了公平接入信道的可能，擾亂了正常的信道分配。針對(duì)這一問題，本文提出了一種可以避免惡意節(jié)點(diǎn)長(zhǎng)期占用信道，提高接入公平性的信道分配算法。該算法采用匈牙利算法計(jì)算信道分配結(jié)果，可在保證各對(duì)節(jié)點(diǎn)互不沖突的前提下獲得最大的通信容量。

1 提高接入公平性的信道分配算法

1.1 通信模型

本文設(shè)計(jì)的信道分配算法采用了以下通信模型：

1) 認(rèn)知無線網(wǎng)絡(luò)中的節(jié)點(diǎn)可分為普通的數(shù)據(jù)收發(fā)節(jié)點(diǎn)和中心控制節(jié)點(diǎn)。設(shè)網(wǎng)絡(luò)中共有2M個(gè)數(shù)據(jù)收發(fā)節(jié)點(diǎn)，其中可分為M個(gè)發(fā)送節(jié)點(diǎn)Si,i∈{1,2,3…,M}和M個(gè)接收節(jié)點(diǎn)Rk,k∈{1,2,3…,M}。此外還有一個(gè)中心控制節(jié)點(diǎn)，該節(jié)點(diǎn)主要負(fù)責(zé)信道分配，不參與數(shù)據(jù)的接收和發(fā)送工作。

2) 認(rèn)知無線網(wǎng)絡(luò)中的信道可分為普通的數(shù)據(jù)通信信道和控制信道。設(shè)供普通收發(fā)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸?shù)男诺罃?shù)為N，各條信道的帶寬分別為Bj。每對(duì)節(jié)點(diǎn)只可接入一條信道，且每條信道只允許一對(duì)節(jié)點(diǎn)接入。此外還有一條控制信道，該信道只用于傳輸和信道分配有關(guān)的信息，普通的收發(fā)節(jié)點(diǎn)不在控制信道上發(fā)送數(shù)據(jù)信息。

3) 網(wǎng)絡(luò)的通信容量可由各對(duì)收發(fā)節(jié)點(diǎn)使用信道的帶寬Bj和對(duì)應(yīng)信道空閑概率pij的乘積之和表示。信道分配的目標(biāo)是尋找可獲得最大通信容量的分配方式。

1.2 算法介紹

本文設(shè)計(jì)的算法可分為以下兩個(gè)階段。

1.2.1 信息匯聚階段

在信息匯聚階段，認(rèn)知無線網(wǎng)絡(luò)中的發(fā)送節(jié)點(diǎn)使用時(shí)分復(fù)用的方法依次向中心控制節(jié)點(diǎn)發(fā)送信道分配請(qǐng)求報(bào)文，報(bào)文中包括該發(fā)送節(jié)點(diǎn)的信道概率向量Wi。發(fā)送節(jié)點(diǎn)的信道概率向量Wi為行向量。Wi共有N個(gè)元素，第i個(gè)發(fā)送節(jié)點(diǎn)Si發(fā)送的信道概率向量如式(1)所示。

Wi=[pi1,pi2,pi3,…,piN]

.

(1)

其中pij是第i個(gè)發(fā)送節(jié)點(diǎn)認(rèn)為第j條信道可能空閑的概率，對(duì)所有的i,j, 均有pij≤1。

1.2.2 信道分配階段

在信道分配階段，為避免惡意節(jié)點(diǎn)長(zhǎng)期占用某些信道，提高節(jié)點(diǎn)接入信道的公平性，網(wǎng)絡(luò)中的中心控制節(jié)點(diǎn)保存了各個(gè)發(fā)送節(jié)點(diǎn)接入每條信道的次數(shù)，用變量C表示，即cij為第i個(gè)發(fā)送節(jié)點(diǎn)接入第j條信道的次數(shù)。對(duì)于所有的發(fā)送節(jié)點(diǎn)，cij的初始值均為0。同時(shí)中心控制節(jié)點(diǎn)還設(shè)置了以發(fā)送節(jié)點(diǎn)接入信道次數(shù)為自變量的公平函數(shù)f(cij)。中心控制節(jié)點(diǎn)在接收到M個(gè)發(fā)送節(jié)點(diǎn)的信道概率向量Wi后，需進(jìn)行如下操作：

1) 中心控制節(jié)點(diǎn)根據(jù)每個(gè)發(fā)送節(jié)點(diǎn)接入信道的次數(shù)cij計(jì)算公平函數(shù)的取值，并將結(jié)果排列成信道公平向量Qi。第i個(gè)發(fā)送節(jié)點(diǎn)的公平向量Qi為行向量，共由N個(gè)元素組成，每個(gè)元素為該發(fā)送節(jié)點(diǎn)接入某一信道次數(shù)cij的函數(shù)f(cij)，具體計(jì)算如式(2)所示。

Qi=[f(ci1),f(ci2),f(ci3),…,f(ciN)]

.

(2)

2) 中心控制節(jié)點(diǎn)將各個(gè)發(fā)送節(jié)點(diǎn)的信道概率向量Wi，公平向量Qi以及帶寬Bj按對(duì)應(yīng)元素相乘，得到行向量Ai，如式(3)所示。

Ai=[pi1f(ci1)B1,pi2f(ci2)B2,…,piNf(ciN)BN]

.

(3)

3) 中心控制節(jié)點(diǎn)將M個(gè)行向量Ai排列成信道分配矩陣S，其中每個(gè)發(fā)送節(jié)點(diǎn)的行向量Ai構(gòu)成矩陣S的一行，如式(4)所示, 矩陣中的每個(gè)元素可表示為Sij。

(4)

若發(fā)送節(jié)點(diǎn)的數(shù)目M與信道數(shù)N不等，則信道分配矩陣S不是方陣，因此需要進(jìn)行矩陣變換。具體操作為增加虛節(jié)點(diǎn)或虛信道。在信道分配矩陣S中，虛節(jié)點(diǎn)和虛信道對(duì)應(yīng)位置的元素均為0。

4) 獲得經(jīng)過變化的信道分配矩陣S后，中心控制節(jié)點(diǎn)即可進(jìn)行信道分配。信道分配的結(jié)果需保證每對(duì)收發(fā)節(jié)點(diǎn)可接入一條信道，且每條信道只有一對(duì)節(jié)點(diǎn)接入。因此分配結(jié)果可用矩陣X表示。X為M×N的矩陣，矩陣中元素xij的取值只有0和1兩種情況，表示第i個(gè)發(fā)送節(jié)點(diǎn)是否接入信道j。具體為：

(5)

6) 中心控制節(jié)點(diǎn)求得信道分配結(jié)果后，需更新各發(fā)送節(jié)點(diǎn)接入信道的次數(shù)cij。當(dāng)?shù)趇個(gè)發(fā)送節(jié)點(diǎn)被分配至第j條信道后，cij的數(shù)值加1，其余位置的接入次數(shù)保持不變。同時(shí)中心控制節(jié)點(diǎn)廣播發(fā)送信道分配結(jié)果。各對(duì)收發(fā)節(jié)點(diǎn)在切換至被分配的信道后即可開始通信。

2 公平函數(shù)的設(shè)計(jì)

當(dāng)信道分配矩陣S中某一元素sij的取值較大時(shí)，則信道j會(huì)有較大的概率被分配給發(fā)送節(jié)點(diǎn)i。若第i個(gè)發(fā)送節(jié)點(diǎn)想長(zhǎng)期占據(jù)信道j，則該節(jié)點(diǎn)可故意增大自己信道概率向量中的pij，使得對(duì)應(yīng)的sij變大，以便盡可能地滿足自己的通信需求。

為避免惡意節(jié)點(diǎn)故意增大某條信道的空閑概率pij以獲得較大的sij，在本文設(shè)計(jì)的信道分配方案中，sij將由節(jié)點(diǎn)發(fā)送的信道空閑概率pij，公平函數(shù)f(cij)以及信道帶寬Bj三者的乘積構(gòu)成。公平函數(shù)f(cij)的取值隨發(fā)送節(jié)點(diǎn)接入信道次數(shù)的增加而減小，即當(dāng)發(fā)送節(jié)點(diǎn)i已多次接入信道j時(shí)，公平函數(shù)f(cij)的取值將會(huì)減小，和信道空閑概率以及帶寬相乘后，信道分配矩陣中對(duì)應(yīng)位置的元素值也將減小，從而降低發(fā)送節(jié)點(diǎn)i再次接入信道j的可能，力求避免惡意節(jié)點(diǎn)長(zhǎng)期占用某條信道。

公平函數(shù)f(cij)應(yīng)為減函數(shù)，且當(dāng)發(fā)送節(jié)點(diǎn)接入該信道的次數(shù)為0時(shí)，公平函數(shù)的取值為1，不對(duì)信道分配矩陣產(chǎn)生影響。負(fù)指數(shù)函數(shù)，反比例函數(shù)等均可選作公平函數(shù)。

3 仿真結(jié)果

在仿真實(shí)驗(yàn)中，設(shè)認(rèn)知無線網(wǎng)絡(luò)中有一個(gè)中心控制節(jié)點(diǎn)，此外還有四個(gè)發(fā)送節(jié)點(diǎn)S1，S2，S3，S4以及4個(gè)接收節(jié)點(diǎn)R1，R2，R3，R4，他們形成四個(gè)收發(fā)節(jié)點(diǎn)對(duì)(S1-R1, S2-R2, S3-R3和S4-R4)。在網(wǎng)絡(luò)中還存在著四條用于數(shù)據(jù)通信的普通信道和一條控制信道。

設(shè)各個(gè)發(fā)送節(jié)點(diǎn)的信道概率向量中元素pij的取值均服從0到1上的均勻分布。當(dāng)四個(gè)發(fā)送節(jié)點(diǎn)均如實(shí)發(fā)送自己的概率向量時(shí)，每條信道被各個(gè)發(fā)送節(jié)點(diǎn)占用的比例約為25%，即在1000次信道分配中，每條信道被各個(gè)節(jié)點(diǎn)占用的次數(shù)應(yīng)為250次左右。

3.1 公平函數(shù)對(duì)信道分配的影響

圖1繪制了在未引入公平函數(shù)的情況下，1000次信道分配后四個(gè)發(fā)送節(jié)點(diǎn)接入各條信道的次數(shù)。由圖1可知，當(dāng)不使用公平函數(shù)(即f(cij)=1)時(shí)，惡意節(jié)點(diǎn)S1接入信道1的次數(shù)遠(yuǎn)遠(yuǎn)高于其他三個(gè)節(jié)點(diǎn)接入信道1的次數(shù)，因此可認(rèn)為節(jié)點(diǎn)S1長(zhǎng)時(shí)間占用了信道1，其他節(jié)點(diǎn)失去了公平使用信道1的機(jī)會(huì)，只能接入其他三條信道。

圖1 未引入公平函數(shù)時(shí)四個(gè)發(fā)送節(jié)點(diǎn)接入各條信道的次數(shù)

圖2 引入公平函數(shù)后四個(gè)發(fā)送節(jié)點(diǎn)接入各條信道的次數(shù)

4 結(jié)論

本文提出了一種無線網(wǎng)絡(luò)中提高節(jié)點(diǎn)接入公平性的信道分配算法。通過保存各個(gè)節(jié)點(diǎn)接入信道的次數(shù)并引入公平函數(shù)，該算法可有效避免惡意節(jié)點(diǎn)對(duì)信道分配的干擾；使用匈牙利算法確保了最終的分配結(jié)果不會(huì)在節(jié)點(diǎn)間產(chǎn)生沖突，且能獲得最大的網(wǎng)絡(luò)通信容量。