一種適合Underlay認(rèn)知無線傳感網(wǎng)絡(luò)的跨層路由算法

佘遠(yuǎn)亞，朱宇

一種適合Underlay認(rèn)知無線傳感網(wǎng)絡(luò)的跨層路由算法

佘遠(yuǎn)亞，朱宇

在Underlay認(rèn)知無線傳感網(wǎng)絡(luò)（Underlay Cognitive Radio Sensor Network，Underlay CRSN）中，由于每個信道被主用戶所使用的狀態(tài)隨機(jī)變化，設(shè)計路由算法不僅需要考慮網(wǎng)絡(luò)中節(jié)點的能量消耗以及延長網(wǎng)絡(luò)壽命的需求，還要考慮路由路徑上各鏈路的信道選擇策略對路徑數(shù)據(jù)傳輸可靠性的影響。該文研究了Underlay認(rèn)知無線電模型下的CRSN路由問題，提出了一種適合該路由問題的鏈路Utility函數(shù)，并將這類問題建模為以最小化Utility為目標(biāo)的最優(yōu)化問題。在討論了幾種傳統(tǒng)的無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）路由算法之后，提出了一種適合Underlay CRSN的跨層路由算法，并給出了該算法的分布式實現(xiàn)方案。計算機(jī)仿真表明所提出的路由算法能很好地適應(yīng)UnderlayCRSN中信道可用狀態(tài)的隨機(jī)變化。

認(rèn)知無線傳感網(wǎng)絡(luò)，跨層，路由算法

0 引言

近來，無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSN）技術(shù)快速發(fā)展，但也面臨著可用頻譜資源不足的問題。為解決這個問題，人們提出了基于認(rèn)知無線電技術(shù)的認(rèn)知無線傳感網(wǎng)絡(luò)（Cognitive Radio Sensor Networks，CRSN）[1]。設(shè)計CRSN需要解決諸多問題，現(xiàn)有的CRSN研究工作主要集中在物理層和媒體接入控制（MAC）層[2][3]，而如何在網(wǎng)絡(luò)層設(shè)計具有更高能量使用效率更高傳輸可靠性的路由算法也是非常重要的。

CRSN上的路由設(shè)計問題與WSN有所不同。在WSN上，研究人員多致力于研究如何平衡每個節(jié)點的功率消耗，從而達(dá)到最大化網(wǎng)絡(luò)壽命的目的[4][5]。而在CRSN中，傳統(tǒng)的路由選擇策略將不再有效。這是因為，即使路由路徑可以實現(xiàn)很小的能量消耗，或者避開了具有較低能量的關(guān)鍵傳感器節(jié)點，由于主用戶（Primary Users，PUs）活動而產(chǎn)生的信道可用狀態(tài)的隨機(jī)變化會導(dǎo)致路徑上鏈路中斷，導(dǎo)致該路徑失效。因此，CRSN上的路由算法需要新的設(shè)計考慮。

研究文獻(xiàn)多是考慮 Overlay信道模型下的路由[6][7]。本文研究在Underlay認(rèn)知無線電模型下的CRSN中路由問題。目標(biāo)是為Underlay CRSN的路由問題建模，并設(shè)計一種行之有效的路由算法，能夠在盡可能延長 CRSN網(wǎng)絡(luò)壽命的同時，使網(wǎng)絡(luò)能夠在可用信道狀態(tài)發(fā)生變化前提下可靠傳輸數(shù)據(jù)。本論文的主要貢獻(xiàn)有兩個方面：

1）提出了一種適用于UnderlayCRSN的鏈路Utility函數(shù)，并將路由問題建模為信道 SINR約束下最小化路徑Utility的最優(yōu)化問題。優(yōu)化問題的解是路由路徑以及路徑上各鏈路的信道選擇。

2）提出了一種適合UnderlayCRSN的路由算法，并給出了算法的分布式實現(xiàn)方案。仿真結(jié)果表明路由算法能很好地適應(yīng)UnderlayCRSN中信道可用狀態(tài)的隨機(jī)變化，新算法能夠有效傳輸更多的數(shù)據(jù)流，且網(wǎng)絡(luò)壽命優(yōu)于傳統(tǒng)算法。

1 網(wǎng)絡(luò)模型

多跳UnderlayCRSN如圖1所示：

圖1 網(wǎng)絡(luò)模型

網(wǎng)絡(luò)中每個傳感器節(jié)點具有有限能量，另外還有一個負(fù)責(zé)收集傳感數(shù)據(jù)、具有無限能量的宿節(jié)點。本文將采用Underlay認(rèn)知無線電系統(tǒng)模型[8]。在此模型下，CRSN傳感器節(jié)點可以挑選任意一個已授權(quán)的信道傳輸數(shù)據(jù)，只要傳感器在使用信道時確保對PU的通信干擾低于其可接受的閾值。如圖1中，此時的PU處于活躍狀態(tài)，傳感器節(jié)點如要發(fā)送數(shù)據(jù)，必須降低其發(fā)送功率以控制對PU的干擾，因此它只能與小虛線圓內(nèi)的其他傳感器通信；只有當(dāng)PU不再使用信道時，傳感器才能增大其發(fā)送功率，與大虛線圓內(nèi)的傳感器建立通信鏈接。假設(shè)在信道上沒有PU正在通信時所有傳感器節(jié)點和宿節(jié)點在該信道上具有相同的最大功率。當(dāng)節(jié)點間的信道被某PU占用，則該鏈路通信能否繼續(xù)取決于接收節(jié)點是否處于發(fā)送節(jié)點被降低的發(fā)送功率范圍（“小虛線圓”）內(nèi)?？梢钥吹?，CRSN中由PU存在而引起的信道變化不可避免影響節(jié)點間鏈路的存在與穩(wěn)定性，并因而引起網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的隨機(jī)變化，這給網(wǎng)絡(luò)路由和數(shù)據(jù)采集帶來很大挑戰(zhàn)。

考慮 CRSN是同步時隙系統(tǒng)。在發(fā)送數(shù)據(jù)分組之前，每個時隙開始時傳感器節(jié)點須檢測各信道的狀態(tài)。利用提高頻譜感知的準(zhǔn)確性和能量使用效率的最新技術(shù)[2]，我們假定頻譜感知結(jié)果是精確的，且時間消耗和能量消耗可以忽略不計。在傳輸開始時，發(fā)送者首先選擇一個合適的信道與下一跳傳感器節(jié)點建立傳輸鏈路。重復(fù)執(zhí)行這個過程直到路由路徑構(gòu)建完成。最終，源傳感器開始沿著已建立好的路徑，向宿節(jié)點發(fā)送由一連串比特組成的數(shù)據(jù)流。如果路由路徑上有一個傳輸鏈路因信道被PU占用而導(dǎo)致其連接丟失，則整個數(shù)據(jù)流終止，且該數(shù)據(jù)流被記錄為傳輸失敗。假設(shè)PU狀態(tài)變化頻率遠(yuǎn)低于時隙變化，因此可近似認(rèn)為一個時隙內(nèi)信道狀態(tài)維持不變。

2 信道模型

在本論文中我們使用兩狀態(tài)馬爾可夫過程對信道進(jìn)行建模。當(dāng)信道被PU使用時，它的狀態(tài)被定義為0，反之為1。將信道寫作定義轉(zhuǎn)移概率α為公式(1)：

即 k信道從時隙 n的狀態(tài) 0，到時隙 n+1時狀態(tài)變化為 1的概率。同樣地，我們定義

在Underlay模型下，信道被PU使用后，傳感器仍然可以使用信道。但這時的信道使用具有限制條件，傳感器需要確保發(fā)送數(shù)據(jù)對PU產(chǎn)生的干擾低于一定的閾值，這樣就勢必減少每一跳的距離并增加到達(dá)宿節(jié)點的跳數(shù)，增加路由開銷。因此，為更好設(shè)計路由，考慮將所有可用信道進(jìn)行分類。定義為所有授權(quán)信道的集合。定義未被PU使用的信道為Non-cognitive Channel，記為Ng信道。定義正在被PU使用的信道為Cognitive Channel，記為Cg信道。顯然Ng信道隨時可能轉(zhuǎn)化為Cg信道，反之亦然。Ng信道因為可以使用更大的傳輸功率而在下一跳選擇上范圍更廣，但也面臨被PU使用的風(fēng)險。而Cg信道的傳輸范圍較小，但更穩(wěn)定。

3 問題建模

雖然作為傳感器網(wǎng)絡(luò)，Underlay CRSN對網(wǎng)絡(luò)壽命有著很高的要求，但由于鏈路信道的變化，僅僅將網(wǎng)絡(luò)壽命作為路由設(shè)計的核心目標(biāo)是不夠的。在WSN中，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)只有在網(wǎng)絡(luò)中一個傳感器出現(xiàn)故障之后才會改變。而在UnderlayCRSN中，信道的變化會對鏈路甚至網(wǎng)絡(luò)拓?fù)浒l(fā)生影響，數(shù)據(jù)流的傳輸可能會在傳感器節(jié)點有著充足能量的情況下仍然中斷。因此，路由算法不僅要著眼于減少路由線路上的能量損耗，而且還要考慮網(wǎng)絡(luò)在數(shù)據(jù)傳輸上的性能。

為了兼顧路由算法在網(wǎng)絡(luò)壽命和數(shù)據(jù)傳輸上的設(shè)計目標(biāo)，考慮使用網(wǎng)絡(luò)在整個生存期內(nèi)成功傳輸?shù)臄?shù)據(jù)流的數(shù)量fsuc作路由算法的性能衡量指標(biāo)。這是合理的，因為公式(2)：

為盡可能增大 fsuc，路由的 Utility函數(shù)需要能夠同時反映壽命和數(shù)據(jù)傳輸穩(wěn)定性的需求。定義

4 路由算法設(shè)計

在本節(jié)中，為解決問題（4.2），我們將討論 Underlay模型下 CRSN的不同路由算法和算法的分布式實現(xiàn)。在回顧兩種傳統(tǒng)的路由算法之后，提出了一種新的綜合考慮信道使用和節(jié)點能量消耗的跨層路由算法。最后，給出了各路由算法的分布式實現(xiàn)。

4.1 最小傳輸能量算法

能量損耗問題是WSN，也是CRSN的核心問題。最小傳輸能量算法（Minimum Transmission Energy，MTE）是將路由路徑上的總傳輸能量最小化的算法。其鏈路 Utility函數(shù)為公式(4)：

4.2 最大最小剩余能量算法

作為在WSN中最為常用的算法之一，最大最小剩余能量（Max-min Residual Energy）算法的設(shè)計重點在于考慮傳感器節(jié)點的剩余能量，通過選擇剩余能量較多的下一跳來緩解網(wǎng)絡(luò)關(guān)鍵節(jié)點的能量消耗壓力，并達(dá)到最大化網(wǎng)絡(luò)壽命T的目的。其鏈路Utility函數(shù)為公式(5)：

需要指出，在WSN中MMRE算法在最大化網(wǎng)絡(luò)壽命方面要優(yōu)于MTE算法[7][8]，但在Underlay CRSN新的路由環(huán)境下這一點是不明確的。而且，在本文算法的優(yōu)化目標(biāo)與傳統(tǒng)WSN相比有所變化，如第3節(jié)(問題建模)所述，為適應(yīng)CRSN對數(shù)據(jù)流傳輸穩(wěn)定性的要求，我們使用網(wǎng)絡(luò)壽命T內(nèi)成功傳輸?shù)臄?shù)據(jù)流數(shù)量fsuc作路由算法設(shè)計的性能目標(biāo)，而這可能會影響到對MMRE的評價。后續(xù)仿真中將比較兩種算法在Underlay CRSN中的性能。

4.3 綜合算法

在WSN中，上述兩種算法有效的考慮了能量消耗，并延長了網(wǎng)絡(luò)壽命。然而它們?nèi)鄙賹π诺肋x擇的考慮，而信道選擇策略正如第3節(jié)(問題建模)提到，決定了網(wǎng)絡(luò)在傳輸數(shù)據(jù)流上的表現(xiàn)。為了應(yīng)對信道的可能變化，算法需考慮在MAC層設(shè)計信道選擇策略。

Ng信道由于當(dāng)前不受PU影響，可以選擇更高的信道發(fā)射功率和擁有更大的覆蓋范圍。選擇Ng信道因此可以減少路由路徑的總跳數(shù)，當(dāng)數(shù)據(jù)流很長時可以在減少路徑總消耗的能量上獲得很大優(yōu)勢。然而，當(dāng)PU再次占用信道時，Ng信道卻會退化為 Cg信道，發(fā)射功率也隨之減小，如果這時發(fā)射功率無法滿足接收節(jié)點的SINR要求，鏈路就會斷開，數(shù)據(jù)流便會中斷。反過來，選擇Cg信道由于可以事先保證PU和自身的SINR要求，節(jié)點便不會因PU的信道占用行為發(fā)生變化而中斷；卻由于擁有更小的最大發(fā)射功率許可而勢必增加路徑的跳數(shù)。因此，算法需要權(quán)衡路徑上各鏈路信道的選擇，以在跳數(shù)和路徑穩(wěn)定性上達(dá)到最優(yōu)的結(jié)果。綜合上述考慮，設(shè)計如下的鏈路Utility函數(shù)如公式(6)：

可以看到，公式（6）中的Utility函數(shù)在綜合考慮路徑剩余能量和傳輸所用能量的前提下，兼顧信道選擇對路徑數(shù)據(jù)通信的影響，算法在Underlay CRSN中的適用性大大增加。通過調(diào)整算法因子 x、y，可以進(jìn)一步得到理想的 Utility。最后，將此算法命名為最小鏈路綜合開銷（Minimum Link Overall Cost，MLOC）算法。

4.4 算法的分布式實現(xiàn)

本節(jié)給出前3節(jié)各算法的分布式實現(xiàn)。與傳統(tǒng)WSN分布式算法不同，在Underlay CRSN中節(jié)點間的可選“鏈路”的數(shù)量與總可用信道的數(shù)量是相同的。雖然，傳感器節(jié)點之間物理鏈路只有一條，但同一鏈路選擇不同信道會得到十分不同的路由解，因而在算法實現(xiàn)上必須找到合適的區(qū)分機(jī)制。假設(shè)i0是需要發(fā)送數(shù)據(jù)的宿節(jié)點的傳感器節(jié)點。定義虛擬節(jié)點V(i,k)，其中i是節(jié)點本身具有的編號，在整個網(wǎng)絡(luò)中唯一；k是節(jié)點所準(zhǔn)備使用的信道的編號。定義V是所有虛擬節(jié)點的集合。假設(shè)Χ是任意虛擬節(jié)點的集合，如果是節(jié)點號為i的任意虛擬節(jié)點。定義虛擬鏈路時存在。假設(shè)已經(jīng)根據(jù)鏈路 Utility函數(shù)計算出了任意兩個虛擬節(jié)點之間的利用Dijkstra算法的設(shè)計思想[9]，有如表1所示：

表1 MLOC、MMRERC和MTERC算法分布式實現(xiàn)的偽代碼

5 仿真

假定網(wǎng)絡(luò)在一個時隙同步系統(tǒng)上運行。定義網(wǎng)絡(luò)的生命周期為網(wǎng)絡(luò)內(nèi)第一個節(jié)點失敗時所經(jīng)歷的時隙數(shù)。網(wǎng)絡(luò)在一塊10×10平方米的區(qū)域內(nèi)，其中隨機(jī)放置10個認(rèn)知傳感器。網(wǎng)絡(luò)宿節(jié)點位于該區(qū)域的左下角。所有傳感器節(jié)點使用固定的發(fā)射功率。隨機(jī)選擇的傳感器節(jié)點以每個時隙一個比特的速率產(chǎn)生數(shù)據(jù)流，即 Pcr為1比特每時隙。傳感器每發(fā)送一個比特消耗1單位能量，而接收一個分組則消耗0.5單位。在仿真開始時，所有的傳感器具有相同數(shù)量初始能量，為10000個單位。根據(jù)4.1節(jié)中的假設(shè)，可以認(rèn)為與數(shù)據(jù)流傳輸相比，頻譜感知和建立路由所消耗的能量和時間可以被忽略?；谕瑯拥脑?，忽略頻譜感知和建立路由路徑所消耗的能量，并假設(shè)頻譜感知是及時的、準(zhǔn)確的。設(shè)置總的可用授權(quán)信道數(shù)為5。為簡單起見，假設(shè)無論Ng還是Cg信道，信道吞吐量相同，為1比特/時隙。假定5個獨立的信道有相同的狀態(tài)轉(zhuǎn)移概率，并在初始時刻時都處于空閑狀態(tài)。

圖2 MLOC、MMRERC和MTERC在成功傳輸?shù)臄?shù)據(jù)流數(shù)量方面的性能比較

在仿真中，設(shè)定2節(jié)中轉(zhuǎn)移概率值α為0.1，β值為0.05。設(shè)定MLOC算法因子x,y的值為1。從圖2中可以看出，隨著數(shù)據(jù)流長度 KPc的增加，fsuc快速下降。這是因為，隨著數(shù)據(jù)流變長，由于信道可用狀態(tài)的變化而導(dǎo)致的路徑不穩(wěn)定性增加，許多數(shù)據(jù)流在傳輸過程中中斷，使得fsuc降低。同時可以看到，MMRERC與MTERC變化幾乎一致，這是因為雖然兩種算法在網(wǎng)絡(luò)能量消耗上有所應(yīng)對，但在信道可用狀態(tài)在Ng和Cg之間變化時缺少有效的策略，導(dǎo)致最終在fsuc表現(xiàn)一致較差。而MLOC比之MMRERC與MTERC要得到更高的fsuc，這是因為隨機(jī)信道選擇策略無法區(qū)分不同穩(wěn)定性的信道，也就無法選擇穩(wěn)定性更好的鏈路，MLOC通過為各信道分配不同的信道穩(wěn)定因子，而在路由選擇上更契合網(wǎng)絡(luò)對數(shù)據(jù)流傳輸穩(wěn)定的要求，從而達(dá)到更好的fsuc。

不同數(shù)據(jù)流長度KPc下，MLOC、MMRERC和MTERC路由算法在網(wǎng)絡(luò)壽命方面的表現(xiàn)如圖3所示：

圖3 MLOC、MMRERC和MTERC在網(wǎng)絡(luò)壽命方面的性能比較

與圖2相似，MLOC在網(wǎng)絡(luò)壽命上要好于MMRERC和MTERC。這是因為，在Underlay CRSN中，由于信道可用狀態(tài)的變化，網(wǎng)絡(luò)拓?fù)鋾o跟著發(fā)生相應(yīng)的變化，與MMRERC和MTERC相比，MLOC能夠識別這種拓?fù)渥兓⒓右岳茫瑥亩x擇在能量消耗和信道穩(wěn)定性之間均衡的路由路徑，并最終達(dá)到更為均衡的網(wǎng)絡(luò)能量消耗且延長網(wǎng)絡(luò)壽命。需要指出的是，在數(shù)據(jù)流長度變化時，三種算法在網(wǎng)絡(luò)壽命上的表現(xiàn)基本保持不變，即使在數(shù)據(jù)流很長的時候網(wǎng)絡(luò)中成功傳輸?shù)臄?shù)據(jù)流的數(shù)量已經(jīng)大大降低。這正好印證了我們在第3節(jié)問題建模部分對 fsuc和網(wǎng)絡(luò)壽命T之間的比較結(jié)論，驗證了選擇成功傳輸?shù)臄?shù)據(jù)流數(shù)量作為算法主要性能依據(jù)的合理性。

6 總結(jié)

Underlay CRSN上的路由問題研究是一個較新穎的領(lǐng)域。由于問題的特殊性，跨層設(shè)計的路由算法是必要選擇。本文首先將 CRSN路由問題建模為最優(yōu)化問題，并在問題建模中體現(xiàn)出在MAC層和網(wǎng)絡(luò)層進(jìn)行路由交叉設(shè)計的必然性。通過綜合考慮路由在能量消 耗上的開銷和路徑上各鏈路的信道選擇策略，提出了一種新型路由算法 MLOC，并給出了其在Underlay CRSN上的分布式實現(xiàn)方案。仿真結(jié)果表明，相比傳統(tǒng)的WSN路由算法MMRERC和MTERC，MLOC算法能夠適應(yīng)并利用Underlay CRSN中信道可用狀態(tài)變化所產(chǎn)生的網(wǎng)絡(luò)拓?fù)渥兓谘娱L網(wǎng)絡(luò)壽命的同時，增加了網(wǎng)絡(luò)成功傳輸?shù)臄?shù)據(jù)流的數(shù)量。

[1] B. Akan, O. B. Karli, and O. Ergul, "Cognitive radio sensor networks," [J]IEEE Networking, vol. 23, pp. 34-40, July 2009.

[2] Maleki, Sina, Ashish Pandharipande, and Geert Leus. "Energy-efficient distributed spectrum sensing for cognitive sensor networks." Sensors Journal, [J]IEEE 11, no. 3 (2011): 565-573.

[3] M. C. Oto and O. B. Akan, “Energy-efficient packet size optimization for cognitive radio sensor networks,”[J]IEEE Transactions on Wireless Communication, vol. 11, no. 4, pp. 1544-1553, Apr. 2012.

[4] 林愷, 趙海, 尹震宇,張希元. "無線傳感器網(wǎng)絡(luò)路由中的能量預(yù)測及算法實現(xiàn)." [J]通信學(xué)報 27, no. 5 (2006): 21-27.

[5] J.-H. Chang and L. Tassiulas, “Maximum lifetime routing in wireless sensor networks,” [C]IEEE/ACM Transaction on Networking, vol. 12, no. 4, pp. 609-619, Aug. 2004.

[6] S. M. Kamruzzaman, E. Kim, D. G. Jeong, and W. S. Jeon, "Energy-aware routing protocol for cognitive radio ad hoc networks," [J]IET Communications, Vol. 6, Iss. 14, pp. 2159-2168, 2012

[7] R. Yu, Y. Zhang, W. Yao, L. Song and S. Xie, “Spectrum-aware routing for reliable end-to-end communications in cognitive sensor networks,” [J]in Proc. of IEEE Globcom’2010, Miami, Florida, U.S.A., Dec. 2010.

[8] A.Goldsmith, S. A. Jafary, I. Maric and S. Srinivasay,“Breaking spectrum gridlock with cognitive radios: an information theoretic perspective,” [J]Proc. IEEE, vol. 97, no. 5, pp. 894–914, May 2009.

[9] Dijkstra, Edsger W. "A note on two problems in connection with graphs." [J]Numerische mathematik 1, no. 1 (1959): 269-271.

A Cross-layer Routing Algorithm for Underlay Cognitive Radio Sensor Networks

She Yuanya, Zhu Yu
(Department of Communication Science and Engineering, Fudan University, Shanghai 200433, China)

In underlay cognitive wireless sensor networks (Underlay CRSN), due to random state variation of each available channel, routing algorithm design needs to consider not only the energy consumption of nodes and network lifetime enhancement, but also the reliability of the data transmission on the routing path directly impacted by channel selection strategy in each link. This paper studies the routing problem of CRSN under underlay cognitive radio model. A suitable link Utility function is proposed for the routing problem. Based on the utility function, we formulate the Underlay CRSN routing problem as an optimization problem with the objective of minimizing the Utility. After discussing several routing algorithms used in traditional wireless sensor networks (WSNs), we finally propose a cross-layer routing algorithm considering both network lifetime and channel state variation for Underlay CRSN, and present a distributed implementation for the algorithm. The computer simulation shows that the proposed routing algorithm can outperform other traditional algorithms in adapting to the random change of channel available state in Underlay CRSN.

Cognitive Radio Sensor Network; Cross-Layer; Routing Algorithms

TP311

A

1007-757X(2014)06-0026-05

2014.05.05)

佘遠(yuǎn)亞 (1987-)，男，荊州市人，復(fù)旦大學(xué)通信科學(xué)與工程系，碩士研究生，研究方向：無線通信、傳感器網(wǎng)絡(luò)，上海，200433

朱 宇 (1977-)，男，揚州市人，復(fù)旦大學(xué)通信科學(xué)與工程系，副教授，博士，研究方向：寬帶無線通信系統(tǒng)與網(wǎng)絡(luò)、通信中的信號處理等，上海，200433