宋　宇，陳　劍，威　力，劉　炯

（1.西安通信學(xué)院，西安　710106；2.解放軍理工大學(xué)指揮信息系統(tǒng)學(xué)院，南京　210007）

?

適用于認(rèn)知無線傳感器網(wǎng)絡(luò)的高效頻譜分配方法*

宋宇1，2，陳劍2，威力2，劉炯1

（1.西安通信學(xué)院，西安710106；2.解放軍理工大學(xué)指揮信息系統(tǒng)學(xué)院，南京210007）

摘要：廣泛工作在ISM（Industrial，Scientific and Medical）頻段的無線傳感器網(wǎng)絡(luò)面臨嚴(yán)重的頻譜稀缺問題。在無線通信中，動態(tài)頻譜分配被認(rèn)為是提高頻譜效能的重要途徑。針對典型集中式管理的認(rèn)知無線傳感器網(wǎng)絡(luò)設(shè)計(jì)了基于圖著色結(jié)合負(fù)載強(qiáng)度的高效頻譜分配算法。首先在協(xié)議干擾模型下確保頻譜資源在空間上充分利用，隨后綜合考慮節(jié)點(diǎn)負(fù)載強(qiáng)度與公平性建立優(yōu)化模型并按照乘子法加擬牛頓法框架求解最優(yōu)值。仿真實(shí)驗(yàn)表明算法與固定頻譜分配方式和傳統(tǒng)自適應(yīng)頻譜分配算法相比，在系統(tǒng)吞吐量和節(jié)點(diǎn)緩沖區(qū)隊(duì)列長度兩個(gè)關(guān)鍵性能指標(biāo)上具有顯著優(yōu)勢。

關(guān)鍵詞：認(rèn)知無線傳感器網(wǎng)絡(luò)，頻譜效能，圖著色，自適應(yīng)，凸規(guī)劃

0　引言

認(rèn)知無線電作為目前提高頻譜利用效能的主要技術(shù)發(fā)展方向［1］，可以從時(shí)間和空間上挖掘和利用空閑頻譜。為此，認(rèn)知無線傳感器網(wǎng)絡(luò)（Cognitive WSN，CWSN）概念油然而生［2］，并被認(rèn)為是與其他工作于ISM頻段的其他網(wǎng)絡(luò)（如WiFi，Bluetooth，Zigbee等）共享稀缺頻譜資源的一種重要解決途徑。CWSN相對于WSN來說，傳感器節(jié)點(diǎn)附加了一個(gè)感知（或被分配）頻譜的階段，隨后利用該頻譜資源按照網(wǎng)絡(luò)拓?fù)浣⑼ㄐ胚B接。

根據(jù)分配方式的不同，頻譜分配主要可分為分布式和集中式兩類。在分布式機(jī)制中，每個(gè)傳感器節(jié)點(diǎn)必須具備感知全局或者局部空間可用頻譜的能力，并執(zhí)行競爭，博弈以及協(xié)同等操作實(shí)現(xiàn)頻譜效用的最優(yōu)或者次優(yōu)［3］。但是傳感器節(jié)點(diǎn)能量受限約束往往難以應(yīng)對分布式頻譜分配所帶來的巨大通信開銷。在許多應(yīng)用場合中，集中式的在全網(wǎng)部署一個(gè)專門網(wǎng)絡(luò)協(xié)調(diào)器（Network Coordinator）更加適合［4-5］，網(wǎng)絡(luò)協(xié)調(diào)器收集各傳感器節(jié)點(diǎn)的鏈路狀態(tài)，頻譜需求等信息，根據(jù)相關(guān)準(zhǔn)則執(zhí)行頻譜分配決策以及協(xié)調(diào)各傳感器節(jié)點(diǎn)機(jī)會的頻譜使用。比較有代表性的工作有：Rayanchu等人針對集中式企業(yè)無線網(wǎng)絡(luò)提出了一種報(bào)文傳輸調(diào)度和頻譜分配聯(lián)合優(yōu)化算法［6］，通過構(gòu)建鏈路沖突模型，預(yù)測不同信道頻寬組合下的網(wǎng)絡(luò)并發(fā)傳輸容量，結(jié)合報(bào)文傳輸調(diào)度的優(yōu)化，可以大幅提升系統(tǒng)吞吐量。Chen等人針對集中式的無線網(wǎng)絡(luò)提出一種速率控制和頻譜分配聯(lián)合解決方案［7］，該方案通過引入虛擬子網(wǎng)隊(duì)長的概念來衡量AP負(fù)載，據(jù)此調(diào)整AP的信道頻寬，結(jié)合傳輸速率控制，在優(yōu)化系統(tǒng)吞吐量的同時(shí)減少傳輸時(shí)延。Murty等設(shè)計(jì)并實(shí)現(xiàn)的一種基于地理位置的頻譜分配系統(tǒng)等［8］。

與上述研究工作不同，本文針對傳感器網(wǎng)絡(luò)典型部署場景，綜合考慮傳感器網(wǎng)絡(luò)采集節(jié)點(diǎn)的空間位置以及負(fù)載大小，實(shí)現(xiàn)頻譜復(fù)用的同時(shí)優(yōu)化頻譜效能，兼顧節(jié)點(diǎn)公平性，仿真實(shí)驗(yàn)表明，該方法在網(wǎng)絡(luò)吞吐率和節(jié)點(diǎn)緩沖區(qū)隊(duì)列長度兩個(gè)指標(biāo)上具有明顯優(yōu)勢。

1　系統(tǒng)模型及問題描述

在報(bào)文傳輸中，每個(gè)用戶維持緩沖報(bào)文隊(duì)列，其值反映用戶對匯聚節(jié)點(diǎn)產(chǎn)生的負(fù)載大小，本文關(guān)于負(fù)載強(qiáng)度的定義見3.1節(jié)。

圖1典型傳感器網(wǎng)絡(luò)拓?fù)淠Ｐ?/p>

典型無線傳感器網(wǎng)絡(luò)拓?fù)淠Ｐ椭饕?個(gè)組件：匯聚節(jié)點(diǎn)（網(wǎng)絡(luò)協(xié)調(diào)器），中繼節(jié)點(diǎn)以及采集節(jié)點(diǎn)。如圖1所示，將網(wǎng)絡(luò)協(xié)調(diào)器部署于匯聚節(jié)點(diǎn)，并假設(shè)有公共信道用于管理信息，且采集節(jié)點(diǎn)位置相對固定。

采集節(jié)點(diǎn)（文章后面部分提到的“節(jié)點(diǎn)”，如無特別說明，均指采集節(jié)點(diǎn)）周期性的通過公共信道將位置，功率，以及負(fù)載大小等信息報(bào)告給網(wǎng)絡(luò)協(xié)調(diào)器。網(wǎng)絡(luò)協(xié)調(diào)器將全網(wǎng)可用的頻譜帶寬采用bw表示。定義A節(jié)點(diǎn)集合，網(wǎng)絡(luò)中有N個(gè)節(jié)點(diǎn)，ai采集節(jié)點(diǎn)編號，其中i=1，…，N。w（a）為節(jié)點(diǎn)i的頻譜分配解。F={w（ai）|ai∈A}為其解的集合。采用干擾模型，即假定鏈路間的干擾范圍已知，且為定值。

將高效頻譜分配問題進(jìn)行形式化描述如下：

其中，式（1）為目標(biāo)函數(shù)，NUM（w（ai））表示節(jié)點(diǎn)ai的效用函數(shù)。約束條件式（2）中I（ai）表示與節(jié)點(diǎn)ai干擾范圍內(nèi)節(jié)點(diǎn)的集合，本文采用協(xié)議干擾模型，要求所有節(jié)點(diǎn)的干擾集合必須為空。約束條件（3）表明，所有節(jié)點(diǎn)分配的頻譜并集必須屬于整個(gè)可用頻譜空間。而約束條件式（4）采用文獻(xiàn)［9］比例公平性的定義，w'（ai）表示另外一個(gè)可行頻譜分配解，只要式（3）的值小于0，則解{w'（ai）}a∈A滿足比例公平性，可以證明，若效用函數(shù)采用對數(shù)函數(shù)，即log（w（ai））的形式，則可以獲得約束條件（3）所需的比例公平性。比例公平性的目的是確保重載用戶不會獨(dú)占資源，輕載用戶也不會被餓死的情況出現(xiàn)。

2　模型求解

遵照文獻(xiàn)［10］中負(fù)載感知以及滿足約束（4）的思路，可將頻譜分配問題的目標(biāo)函數(shù)設(shè)置為∑ai∈AQa·ilog（1+w（a）i）的形式，其中Qai代表采集節(jié)點(diǎn)ai的緩沖區(qū)隊(duì)列長度。這里在log函數(shù)的自變量加1是為了在運(yùn)算時(shí)確保分配解w（a）i不出現(xiàn)負(fù)數(shù)，且效用值不為負(fù)。該目標(biāo)函數(shù)兼顧了頻譜分配的效用和公平性。但是，由于節(jié)點(diǎn)間干擾存在，在約束（3）下求解該目標(biāo)函數(shù)是一個(gè)帶干擾的最大權(quán)匹配問題，該類問題是NP-難問題。為此，采用集中式著色法確保干擾用戶采用不同信道，非干擾用戶可以復(fù)用信道。具體實(shí)現(xiàn)描述如下：

算法1：集中式著色算法

（1）根據(jù)節(jié)點(diǎn)的位置信息和通信范圍構(gòu)建節(jié)點(diǎn)的干擾圖I；

（2）在干擾圖I中，將節(jié)點(diǎn)按照順時(shí)針方向排序，用數(shù)組Nodes［］表示，即節(jié)點(diǎn)i用Nodes［i］表示，初始信道標(biāo)號chn=1；

（3）針對每個(gè)節(jié)點(diǎn)i=1，…，N，分配給其鄰居未使用的最少可用顏色，當(dāng)需要更多顏色時(shí)，chn=chn+1。

經(jīng)過第一部分的信道分配，可以消除干擾約束條件（2），將原問題重寫如下：

從上述形式不難看出，目標(biāo)函數(shù)是非線性凸函數(shù)，且決策變量的取值空間是凸集，該問題是一個(gè)凸規(guī)劃問題。求解該問題常用的方法有罰函數(shù)法（外點(diǎn)罰函數(shù)，內(nèi)點(diǎn)罰函數(shù)），乘子法等，前者結(jié)構(gòu)簡單，只需在每一步迭代時(shí)構(gòu)造由原始目標(biāo)函數(shù)和約束函數(shù)組成的增廣目標(biāo)函數(shù)，隨后可以直接調(diào)用無約束優(yōu)化算法的通用程序，但是算法中與障礙函數(shù)（表征各個(gè)約束）相乘的罰參數(shù)隨著迭代次數(shù)增加使得增廣目標(biāo)函數(shù)的病態(tài)性越來越嚴(yán)重，對無約束優(yōu)化子問題的求解帶來了數(shù)值實(shí)現(xiàn)上的困難。乘子法則引入拉格朗日函數(shù)以及附加的適當(dāng)罰函數(shù)有效地克服了該問題。

此外，在求解無約束優(yōu)化問題上，牛頓法由于其不低于二階的收斂速度被廣泛應(yīng)用，但是算法要求目標(biāo)函數(shù)的Hess矩陣Gk=塄f（xk）在每個(gè)迭代點(diǎn)處正定，否則不能保證所產(chǎn)生的方向是目標(biāo)函數(shù)在xk的下降方向，并且，牛頓法每一步迭代都需要目標(biāo)函數(shù)的二階導(dǎo)數(shù)，對于大規(guī)模問題其計(jì)算量較大。為此，求解無約束優(yōu)化時(shí)常將其改進(jìn)為擬牛頓法，其核心思想是將基本牛頓法中的Hess矩陣用某個(gè)秩1或秩2近似矩陣代替，該近似矩陣顯然滿足對稱正定，且方向近似牛頓方向。具體算法實(shí)現(xiàn)偽碼如下：

算法2：頻譜分配算法

（1）初始化x0∈Rn，λ1∈R，σ1＞0，0≤ε＜1，諄∈（0，1），η＞1，k：=1。

（2）利用拉個(gè)朗日乘子λk將不等式約束（6）作為g（xk），構(gòu)建拉格朗日增廣函數(shù)

（3）求解無約束優(yōu)化問題minψ（xk，λk，σk）。

%BFGS擬牛頓法

①令參數(shù)δ∈（0，1），σ∈（0，0.5），初始指定對稱正定矩陣B0，使用單位矩陣In；

②計(jì)算‖塄ψ（xk）‖，若‖塄ψ（xk）‖≤ε，跳轉(zhuǎn)至④，否則繼續(xù)③~⑤；

③利用Bk·dk=-gk，求解dk；//dk為Armijo線性搜索方向；（9）

⑤xk+1=xk+αk·dk；（11）

其中，sk=xk+1-xk，zk=gk+1-gk。（12）

需要注意的是，Armijo線性搜索準(zhǔn)則并不能確保zTksk＞0，所以在zTksk≤0時(shí)不考慮Bk更新；

⑦k：=k+1，跳轉(zhuǎn)至②。

①如果βk≥諄·βk-1，則σk+1：=η·σk，否則σk+1：=σk；//更新懲罰因子；

②λk+1=max {0，（λk-σk+1·gi（xk）}；//更新乘子參數(shù)；（13）

③k：=k+1，跳轉(zhuǎn)至1步驟。

3　仿真及結(jié)果分析

由于算法非啟發(fā)式算法，且求得的結(jié)果即為最優(yōu)值。為此，將算法性能與固定頻譜寬度分配法以及僅考慮負(fù)載的自適應(yīng)頻譜寬度分配法進(jìn)行橫向比較。

3.1仿真數(shù)據(jù)

為驗(yàn)證算法的自適應(yīng)性，各用戶的流量強(qiáng)度需在不同的時(shí)間步發(fā)生變化，且速率從局部看為變速率流。NS-2提供了指數(shù)流，帕累托流，以及恒定數(shù)據(jù)流3種流量產(chǎn)生模式，但無變速率流量生成模塊，為此，本文采取將指數(shù)流進(jìn)行疊加的方式生成變速率流量。

定義1由NS-2軟件按照如下規(guī)則生成的流量稱為基準(zhǔn)流量。

表1基準(zhǔn)流量參數(shù)

由定義1可知，基準(zhǔn)流量忙時(shí)平均時(shí)間是1 s，閑時(shí)平均時(shí)間是10 s，二者均服從指數(shù)分布，在忙時(shí)的流量速率時(shí)10 kb/s，而在閑時(shí)不產(chǎn)生流量。據(jù)此，可以得到一個(gè)基準(zhǔn)流量速率統(tǒng)計(jì)平均的流量強(qiáng)度為：

按照式（14），仿真中用戶基準(zhǔn)負(fù)載強(qiáng)度為：

0.090 9k bit/s≈900 bit/s

定義2基準(zhǔn)流量強(qiáng)度疊加的倍數(shù)稱為流量強(qiáng)度個(gè)數(shù)。

由于各基準(zhǔn)流量間相互獨(dú)立，所以基準(zhǔn)流量疊加產(chǎn)生的流量強(qiáng)度在統(tǒng)計(jì)平均意義上是基準(zhǔn)流量強(qiáng)度的線性疊加。

圖2不同流量強(qiáng)度示意圖

如圖2所示，0 s~199 s，200 s~399 s，400 s~599 s三個(gè)時(shí)間段分別展示了1，5，10個(gè)流量強(qiáng)度負(fù)載大小。

仿真總時(shí)間設(shè)置為1 200 s，認(rèn)知傳感器節(jié)點(diǎn)數(shù)為5個(gè)，按照協(xié)議干擾模型采用著色法分離出2個(gè)節(jié)點(diǎn)組，組內(nèi)節(jié)點(diǎn)間通信具有干擾關(guān)系，不能復(fù)用頻譜；而節(jié)點(diǎn)組之間無干擾關(guān)系，總頻譜可以在節(jié)點(diǎn)組之間實(shí)現(xiàn)復(fù)用。分組關(guān)系如圖3所示。

圖3仿真節(jié)點(diǎn)部署

3.2仿真結(jié)果

為充分體現(xiàn)算法的自適應(yīng)性，采用如表2所示流量強(qiáng)度分配方式：

表2流量強(qiáng)度分配表

其中，采集節(jié)點(diǎn)1和采集節(jié)點(diǎn)2在整個(gè)仿真時(shí)間內(nèi)流量強(qiáng)度不變，分別為1和10。而采集節(jié)點(diǎn)3~5則每隔400 s改變一次流量強(qiáng)度，每個(gè)時(shí)間步總頻譜數(shù)量為5 KHz。仿真實(shí)驗(yàn)中各參數(shù)取值為：最大迭代次數(shù)500，算法終止參數(shù)ε取10-4，罰因子σ為2.0，乘子法中的實(shí)參數(shù)η為2.0，諄為0.8，λ的初始值為0.1，Armijo線搜索參數(shù)為0.5，β的初始值為10。在每個(gè)時(shí)間步優(yōu)化算法的迭代次數(shù)如表3所示。

表3每個(gè)時(shí)間步頻譜分配算法的迭代次數(shù)統(tǒng)計(jì)

3.2.1平均吞吐率對比

下頁圖4展示了3種算法在不同時(shí)間步中各采集節(jié)點(diǎn)平均吞吐率變化曲線，從圖中可以看出，所提出的頻譜分配算法在不同的流量變化環(huán)境下均能有效提升系統(tǒng)吞吐率。與固定頻譜分配法相比，本算法的平均吞吐量提升約20%~30%，最高達(dá)到50%（第11時(shí)間步）；與僅考慮隊(duì)列長度的自適應(yīng)頻譜分配法相比，平均吞吐量提升約10%~15%，最高達(dá)到30%（第11時(shí)間步）。

圖4不同時(shí)間步的吞吐率比較

3.2.2緩沖區(qū)隊(duì)列長度對比

3種算法各采集節(jié)點(diǎn)的平均緩沖區(qū)隊(duì)列長度在不同時(shí)間步的變化曲線如圖5所示，本文算法在降低各采集節(jié)點(diǎn)緩沖區(qū)隊(duì)列長度方面有明顯優(yōu)勢。與固定頻譜寬度分配法比較，采用本算法的各采集節(jié)點(diǎn)平均緩沖區(qū)隊(duì)列長度降低了近一個(gè)數(shù)量級，與僅考慮隊(duì)列長度的自適應(yīng)頻譜分配算法比較也有至少3倍~5倍的降低量。

圖5不同時(shí)間步各用戶平均緩沖區(qū)隊(duì)列長度對比

4　結(jié)論

本文針對集中式認(rèn)知無線傳感器網(wǎng)絡(luò)提出了一種高效的頻譜分配方法。首先，按照協(xié)議干擾模型采用著色法劃分干擾域，實(shí)現(xiàn)非干擾域之間的頻譜復(fù)用，并在此基礎(chǔ)上根據(jù)傳感器采集節(jié)點(diǎn)負(fù)載強(qiáng)度進(jìn)行頻譜分配。仿真實(shí)驗(yàn)表明，該方法能夠較好地適配用戶負(fù)載強(qiáng)度的變化，并且在網(wǎng)絡(luò)平均吞吐率以及緩沖區(qū)隊(duì)列長度兩個(gè)關(guān)鍵指標(biāo)上相比固定頻譜分配法和僅考慮緩沖區(qū)隊(duì)列長度的頻譜分配算法具有明顯優(yōu)勢。

參考文獻(xiàn)：

［1］AKYILDIZ I F，LEE W，VURAN M C，et al. A survey on spectrum management in cognitive radio networks［J］. IEEE Communications Magazine，2008，46（4）：40-48.

［2］VIJAY G，BDIRA A，IBNKAHLA M. Cognitive in wireless sensor networks：a perspective［J］. IEEE Sensors Journal，2011，11（3）：582-592.

［3］TIMMERS M，POLLIN S，DEJONGHE A，et al. A distributed multichannel MAC protocol for multi-hop cognitive radio networks［J］. IEEE Trans，Veh，Technol，2010，59（1）：446-459.

［4］ZAHMATI A S，HUSSIAN S，F(xiàn)ERNANDO X . Cognitive wireless sensor networks：emerging topics and recent challenges［C］// 2009 IEEE Toronto International Conference on Science and Technology for Humanity

（TIC-STH），2009.

［5］OZGER M，AKAN O B . Event-driven spectrum-aware clustering in cognitive radio sensor networks［C］// In proceedings of the IEEE International Conference on Computer Communications（INFOCOM2013），IEEE Communication Society，2013.

［6］RAYANCHU S，SHRIVASTAVA V，BANERJEE S. Improving throughputs in enterprise wireless LANs through flexible channelization［C］// In：Proc. of the 17th ACM Int’l Conf. on Mobile Computing and Networking （MobiCom 2011），2011.

［7］CHEN J，WU J P，LI H W. SES：stable and efficient solution for rate control and spectrum allocation in wireless LANs［J］. Wireless Personal Communications，2012，66（1）：81-99.

［8］MRTY R，CHANDRA R，MOSCIBRODA T，et al. SenseLess：a database-driven white spaces network［C］// In proceedings of the IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks （DySPAN2011）. IEEE Communication Society，2011.

［9］NANDAGOPAL T，KIM T E，GAO X. Achieving MAC layer fairness in wireless packet networks［C］// In：Proc. of the 6th ACM Int’l Conf. on Mobile Computing and Networking （MobiCom 2000），New York：ACM，2000.

［10］MOSCIBRODA T，CHANDRA R，WU Y，et al. Load-aware spectrum distribution in wireless LANs［C］// In proceedings of the IEEE International Conference on Network Protocols （ICNP2008），IEEE Communication Society，2008.

歡迎訂閱本刊歡迎刊登廣告

An Efficient Spectrum Allocation Method for Cognitive Wireless Sensor Network

SONG Yu1，2，CHEN Jian2，WEI Li2，LIU Jiong1
（1. Xi’an Communications Institute，Xi’an 710106，China；2. Institute of Command Information Systems，PLA University of Science and Technology，Nanjing 210007，China）

Abstract：WSN widely working in ISM spectrum band is facing serious problem of spectrum scarcity，in wireless communication，Dynamic Spectrum Allocation（DSA）is considered as an important way to improve spectrum utility. In this paper，an efficient spectrum allocation algorithm based on graph coloring combining with users’load intensity for the typical centralized cognitive WSN is designed. To start with，we ensure the frequency resource fully reused among users on the geographical space. Then load intensity and fairness of users are integrated together to set a optimization model，it is solved through multiplier plus quasi-Newton algorithm structure and obtain and optimal value. Simulation experiments demonstrate that our algorithm has the remarked superiority in the system throughput and node buffer queue length（the two major optimizing objectives）when compare with the fixed spectrum allocation method and the traditional adaptive spectrum allocation algorithm.

Key words：cognitive WSN，spectrum utility，graph coloring，adaptive allocation，convex programming

作者簡介：宋宇（1983-），男，陜西西安人，碩士。研究方向：無線網(wǎng)絡(luò)。

*基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目（61301159，61402520）

收稿日期：2015-01-04

文章編號：1002-0640（2016）02-0013-05

中圖分類號：TP393

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

修回日期：2015-02-24