基于優(yōu)化模型的協(xié)作通信的中繼節(jié)點選擇算法*

藺 莉,宋三華

(黃淮學(xué)院信息工程學(xué)院,河南 駐馬店 463000)

無線傳感網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)已廣泛應(yīng)用于工業(yè)自動化系統(tǒng)[1-2]。然而,通常工業(yè)廠房常伴有噪聲以及障礙物,這影響了傳感節(jié)點的數(shù)據(jù)傳輸性能[3]。而協(xié)作分集技術(shù)是提高數(shù)據(jù)傳輸可靠性的不錯選擇。這些技術(shù)充分利用了無線媒介的廣播特性,使部分節(jié)點承擔(dān)中繼節(jié)點的作用。

協(xié)作重傳是提高消息傳輸成功率的有效技術(shù)。而協(xié)作重傳技術(shù)的性能依賴于中繼節(jié)點[4-5]。這些中繼節(jié)點實時監(jiān)聽消息,為后續(xù)協(xié)作重傳做準(zhǔn)備。因此,協(xié)作通信的性能取決于中繼節(jié)點的選擇。若將網(wǎng)絡(luò)內(nèi)所有節(jié)點均作為中繼節(jié)點,固然可提高了協(xié)作分集的參與率,但這必然浪費了帶寬和能耗。據(jù)此,協(xié)作重傳技術(shù)的關(guān)鍵在于如何選擇最合適的節(jié)點作為中繼節(jié)點,進而提高數(shù)據(jù)傳輸?shù)目煽啃訹6]。

目前,研究人員提出不同的中繼節(jié)點選擇算法,如基于鏈路質(zhì)量、基于節(jié)點剩余能量。此外,文獻[7]提出基于總體隨機選擇中繼節(jié)點算法TRT(Totally Random Technique),但是此算法并沒有考慮節(jié)點與協(xié)作者間的通信質(zhì)量。而文獻[8]提出了基于隨機鄰近協(xié)作者算法RAC(Random Around Coordinator),即從協(xié)作者鄰近的節(jié)點中隨機選擇一些節(jié)點作為中繼節(jié)點,并結(jié)合RSSI指標(biāo)。此外,文獻[2]采用機會選擇中繼節(jié)點算法OSA(Opportunistic Selection algorithm)。此算法依據(jù)網(wǎng)絡(luò)誤差率選擇中繼節(jié)點。

此外,國內(nèi)研究人員對協(xié)作通信的中繼節(jié)點選擇也進行了大量的研究。苗春雨等[9]利用啟發(fā)式算法尋找中繼節(jié)點的最優(yōu)位置。而趙玉麗等[10]利用信道系數(shù)選擇中繼節(jié)點,但是該算法通信開銷較大,需不斷地獲取信道系數(shù),尤其是大型的移動傳感網(wǎng)絡(luò)。而孫利娟等[11]利用誤碼率和節(jié)點位置信息,并引用分布式競爭機制產(chǎn)生中繼節(jié)點。王寧等[12]面向簇類的傳感網(wǎng)絡(luò),依據(jù)節(jié)點剩余能量和節(jié)點位置信息,并利用改進的粒子群算法選擇中繼節(jié)點。但是,引入粒子群算法加大算法的運行時間,增加節(jié)點的能耗。

為此,本文提出基于優(yōu)化模型的協(xié)作通信的中繼節(jié)點選擇OM-SRN(Optimization Model-based Selection of Relay Nodes)算法。與現(xiàn)有的中繼節(jié)點選擇算法不同,OM-SRN算法將中繼節(jié)點的選擇問題進行基于增益函數(shù)的優(yōu)化問題處理。OM-SRN算法依據(jù)節(jié)點的鄰居節(jié)點數(shù)、剩余能量以及鏈路質(zhì)量三方面信息選擇中繼節(jié)點。最后,通過實驗仿真分析了OM-SRN算法的性能。本文的主要貢獻可以歸納為兩點:①將中繼節(jié)點的選擇問題模擬成優(yōu)化問題;②不是簡單地采用隨機選擇中繼節(jié)點,而是通過節(jié)點的鄰居數(shù)、能量和鏈路質(zhì)量信息綜合擇優(yōu)選擇中繼節(jié)點。即利用這三方面的信息對的中繼節(jié)點的選擇進行約束。

1 能量模型

采用如圖1所示的能耗模型[12]。收/發(fā)兩端相距dm。若d較短時,采用自由空間傳輸模型,而對于d比較大時,采用多徑衰落信道模型。若在相距dm,發(fā)射端向接收端傳輸q比特消息所消耗的能量:

(2)

式中:Eelec運行發(fā)射器元件時每比特所消耗的能量。Efrris、Etworay分別表示發(fā)射器在自由空間、雙徑傳播模型(two ray ground model)的單位功率放大器的能量消耗,并且do:

(3)

相應(yīng)地,對于接收q比特的消息所消耗的能量:

ERX(k)=qEelec

(4)

2 OM-SRN算法

2.1 優(yōu)化問題的建立

OM-SRN算法將中繼節(jié)點的選擇進行優(yōu)化問題處理。通用的優(yōu)化問題的數(shù)學(xué)表述,如式(5)所示:

minimizef(x)
subject to:
g(x)≤0
h(x)=0
x∈χ

(5)

式中:f為目標(biāo)或增益函數(shù)。而g和h為約束函數(shù),其限制了可行解的空間。而x:(x1,x2,…,xn)是可行解矢量,其中最優(yōu)解表示為x*。

函數(shù)f(x)是優(yōu)化問題的關(guān)鍵,其決定了矢量x。為此,中繼節(jié)點的選擇由式(6)所示的增益函數(shù)表示:

(6)

式中:Gi表示節(jié)點i的增益。ni表示節(jié)點i的鄰居節(jié)點數(shù)。

而ei的定義如式(7)所示,其反映了節(jié)點i的剩余能量歸一化值。

(7)

式中:REi、IEi分別表示節(jié)點i的剩余能量和初始能量。

而si的定義如式(8)所示:

(8)

式中:RSSIj表示節(jié)點i的鄰居節(jié)點j的RSSI值。而Limited_RSSI為常數(shù),表示通信的RSSI的最小值(-87 dBm[13])。

而Hi的定義如式(9)所示,其反映了成功傳輸數(shù)據(jù)的歷史數(shù)據(jù)。

Hi=(1-α)Hi+αSR

(9)

式中:α為控制參數(shù),可依據(jù)不同情況調(diào)整α值。如果成功傳輸了數(shù)據(jù)包,則SR=1,否則為空。

此外,式(6)中的βn、βe、βs和βH分別表示ni、ei、si和Hi的權(quán)重。式(5)所示的目標(biāo)函數(shù)f考慮了鄰居節(jié)點數(shù)、數(shù)據(jù)傳輸成功率、信號強度和節(jié)點的可用能量。

為了使中繼節(jié)點數(shù)最小化,并保證同時每個節(jié)點均有一個轉(zhuǎn)發(fā)節(jié)點。將式(5)所示的優(yōu)化問題轉(zhuǎn)化為:

(10a)

subject to:Ax≥b

(10b)

Cx=d

(10c)

xi∈{0,1}

(10d)

式中:N為總體節(jié)點數(shù)。式(10a)為目標(biāo)函數(shù),函數(shù)值越小,節(jié)點成為中繼節(jié)點的概率越低。式(10b)中的A為鄰接矩陣,且尺寸為N×N。第i行第j列的元素值表示為ai,j。若ai,j=1,表示節(jié)點j是節(jié)點i的鄰居節(jié)點,否則ai,j=0。如果協(xié)調(diào)者沒有收到節(jié)點i的鄰居節(jié)點列表,則矩陣A的第i行的元素值均為零。

而x為N×1維的矢量,如果節(jié)點i是它鄰居節(jié)點,則xi=1,否則為零。b是一個矢量,其元素值bi表示每個節(jié)點的最小中繼節(jié)點數(shù),且至少設(shè)置為1。

式(10c)是由協(xié)調(diào)者設(shè)置的約束項,其中矩陣C表示與協(xié)調(diào)者沒有足夠通信鏈路的節(jié)點集。矩陣C的每一行表示作為節(jié)點i的中繼節(jié)點的候選節(jié)點。

式(10)的優(yōu)化問題將中繼節(jié)點設(shè)置最小增益。由于采用了二值變量,則式(10)所示的優(yōu)化模型為二值整數(shù)規(guī)劃BIP(Binary Integer Programming)問題[14]。由于BIP問題是NP-Hard,可采用Branch 和Bound算法求解。

2.2 OM-SRN算法的執(zhí)行過程

當(dāng)節(jié)點加入網(wǎng)絡(luò),就在每個beacon間隔內(nèi)廣播beacon 消息。一旦接收到其他節(jié)點的beacon,就將其作為自己的鄰居節(jié)點。同時,各節(jié)點計算自己的增益值(式(5)所示),然后,再將這些值傳輸至協(xié)調(diào)者。協(xié)調(diào)者再通過式(10)選擇中繼節(jié)點。一旦接收了中繼節(jié)點,協(xié)調(diào)者就在下一個BI時隙內(nèi)將這些中繼節(jié)點信息公布,使得節(jié)點知道是否成為中繼節(jié)點。

一旦產(chǎn)生了中繼節(jié)點,就開始數(shù)據(jù)傳輸階段。通信階段由傳輸和重傳階段。在第一階段,各節(jié)點開始傳輸數(shù)據(jù),如圖1所示。每個節(jié)點傳輸了它的消息后,中繼節(jié)點就存儲它所監(jiān)聽的消息和發(fā)送節(jié)點的ID。如果節(jié)點不是中繼節(jié)點,當(dāng)它完成了數(shù)據(jù)傳輸后,就進入休眠。

所有節(jié)點完成了第一階段的消息傳輸后,就監(jiān)聽鄰居節(jié)點所傳輸?shù)南?進而更新鄰居節(jié)點集,進而識別協(xié)調(diào)者。

在第二階段,每個中繼節(jié)點重傳消息,其包含了協(xié)調(diào)者所存儲的ID號。如圖2所示,節(jié)點N2重傳消息。

圖1 節(jié)點傳輸消息示例

圖2 重傳消息階段

3 性能仿真

3.1 仿真環(huán)境

為了更好地分析OM-SRN算法性能,建立仿真平臺?？紤]了50 m×50 m仿真區(qū)域,且協(xié)調(diào)者位于仿真區(qū)域中心。利用混合整數(shù)線性規(guī)劃MILP(Mixed Integer Linear Programming)求解優(yōu)化問題。仿真時間為450 s,在這個仿真時間內(nèi),協(xié)調(diào)者發(fā)送50個beacon。其他的仿真參數(shù)如表1所示。

表1 仿真參數(shù)

此外,選擇總體隨機選擇算法TRT、協(xié)調(diào)者的隨機選擇算法RAC、機會選擇算法OSA作為參照,并考慮消息傳輸成功率、每個節(jié)點的平均協(xié)作傳輸?shù)南?shù)以及冗余消息數(shù)三方面的性能。

3.2 數(shù)據(jù)分析

首先分析消息傳輸成功率隨節(jié)點數(shù)的變化曲線,如圖3所示。

圖3 消息傳輸成功率

從圖3可知,所有的采用中繼節(jié)點技術(shù)的算法比沒有采用中繼節(jié)點技術(shù)的算法具有更好性能。而與其他算法相比,提出的OM-SRN具有最高的消息傳輸成功率,原因在于:OM-SRN能夠合理地選擇中繼節(jié)點,使得消息傳輸效率更高。

圖4顯示每個節(jié)點的平均協(xié)作傳輸消息數(shù)。從圖4可知,OM-SRN算法具有最小的平均協(xié)作消息數(shù)。協(xié)作傳輸消息數(shù)越少,說明所選擇的中繼節(jié)點數(shù)越少,降低網(wǎng)絡(luò)成本。結(jié)合圖3不難發(fā)現(xiàn),提出的OM-SRN算法以較少的協(xié)作節(jié)點完成最高的消息傳輸成功率。

圖4 每個節(jié)點的平均協(xié)作傳輸消息數(shù)

最后,分析了冗余消息率隨節(jié)點數(shù)的變化情況,如圖5所示。從圖5可知,當(dāng)節(jié)點為800時,OM-SRN 算法的中繼節(jié)點所產(chǎn)生的冗余消息率接近于零。而TRT算法具有最高的冗余消息率,原因在于:它隨機選擇中繼節(jié)點。

圖5 冗余消息率

最后,分析算法的能耗性能。節(jié)點的初始能量為0.5 J,Eelec=50 nJ/bit、Efs=10 pJ/(bit·m2)、Etworav=0.001 3 pJ/(bit·m4),節(jié)點數(shù)為81。同時,引用網(wǎng)絡(luò)生存時間、穩(wěn)定時長表征能耗。網(wǎng)絡(luò)生存時間是指網(wǎng)絡(luò)內(nèi)最后一個失效節(jié)點所發(fā)生的時間;穩(wěn)定時長是指網(wǎng)絡(luò)內(nèi)第一個失效節(jié)點所發(fā)生的時間。因此,網(wǎng)絡(luò)生存時間、穩(wěn)定時長越長,能耗越低。實驗數(shù)據(jù)如表2所示。

表2 能耗性能

從表2可知,提出的OM-SRN算法的穩(wěn)定時長和網(wǎng)絡(luò)生存時間略低于其他的三類算法。這些數(shù)據(jù)表明,OM-SRN算法的平均能耗高于OSA、RAC和TRT算法。原因在于:OM-SRN采用分布式競爭機制,并需要收集相關(guān)信息,加大了通信開銷,消耗了節(jié)點能量。

4 總結(jié)

合適地選擇中繼節(jié)點是提高WSNs數(shù)據(jù)傳輸質(zhì)量的關(guān)鍵。提出的OM-SRN算法將選擇中繼節(jié)點問題進行優(yōu)化模型處理。同時,考慮多個因素選擇中繼節(jié)點。實驗數(shù)據(jù)表明,提出的OM-SRN算法在消息傳輸成功率、冗余消息數(shù)方面的性能得到提高。這些數(shù)據(jù)表明,OM-SRN算法在選擇中繼節(jié)點方面的優(yōu)勢,即以最少的中繼節(jié)點數(shù)實現(xiàn)可靠的消息傳輸性能。

然而,節(jié)點能耗較大,后期,將進一步優(yōu)化算法,降低能耗。此外,本文僅通過實驗分析了算法的性能,后期將擴展算法的應(yīng)用場景,如高速移動的車聯(lián)網(wǎng),分析算法的實時性。