藺 莉,宋三華

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

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

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

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

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

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

1 能量模型

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

(2)

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

(3)

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

ERX(k)=qEelec

(4)

2 OM-SRN算法

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

OM-SRN算法將中繼節(jié)點(diǎn)的選擇進(jìn)行優(yōu)化問(wèn)題處理。通用的優(yōu)化問(wèn)題的數(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)化問(wèn)題的關(guān)鍵,其決定了矢量x。為此,中繼節(jié)點(diǎn)的選擇由式(6)所示的增益函數(shù)表示:

(6)

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

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

(7)

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

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

(8)

式中:RSSIj表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)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é)點(diǎn)數(shù)、數(shù)據(jù)傳輸成功率、信號(hào)強(qiáng)度和節(jié)點(diǎn)的可用能量。

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

(10a)

subject to:Ax≥b

(10b)

Cx=d

(10c)

xi∈{0,1}

(10d)

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

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

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

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

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

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

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

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

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

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

圖2 重傳消息階段

3 性能仿真

3.1 仿真環(huán)境

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

表1 仿真參數(shù)

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

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

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

圖3 消息傳輸成功率

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

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

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

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

圖5 冗余消息率

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

表2 能耗性能

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

4 總結(jié)

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

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