WSNs中聯合速率控制與時隙分配的效用優化算法*

劉　韜

(西南民族大學 計算機科學與技術學院, 四川 成都 610041)

?

WSNs中聯合速率控制與時隙分配的效用優化算法*

劉韜

(西南民族大學 計算機科學與技術學院, 四川 成都 610041)

針對無線傳感器網絡(WSNs)，提出了一種聯合節點數據采集速率控制與時隙分配的(JRCTA)算法效用優化。該算法建立統一速率控制與時隙分配的效用優化模型，將節點數據采集速率的優化控制與基于沖突避免的節點發送時隙分配結合起來，在控制網絡延時性能的前提下，最大化匯聚節點在單位時間內所采集到的數據量。仿真實驗結果表明，JRCTA算法具有較好的性能。

無線傳感器網絡; 速率控制； 時隙分配； 效用優化

0　引　言

在環境監測等傳感器網絡應用中，匯聚(sink)節點總是希望能夠盡可能多地接收到來自各節點的感應數據，以達到增加監測準確性的目的。但由于節點間的相互干擾，每個節點的感應數據發送速率會受到限制，這就要求對各節點的感應數據采集速率進行優化控制；另外，為避免不同節點間的信號沖突，還要對各節點的工作時隙進行分配。

文獻[1]針對網絡流量的實時性和可靠性要求，提出一種基于優先級的服務區分速率控制策略，根據上游節點的優先級調整上游節點的發送速率；文獻[2]提出了一種基于云模型的無線傳感器網絡(WSNs)擁塞和速率控制策略，通過節點擁塞度檢測調節節點輸入速率,但是沒有考慮信號沖突及節點間相互干擾對節點發送速率的影響;文獻[3]構建滿足最小重傳時延約束的傳輸層包長調整方程和實現方法，最終建立適合WSNs的速率調整機制，但是該方法并未考慮沖突，也未考慮節點的路由機制；文獻[4]則將WSNs中的最大化吞吐量問題轉換為最大流問題，但該研究同樣沒有考慮沖突、干擾等因素；文獻[5]提出為控制誤碼率，網絡中每個節點自適應的調節自己的數據發送速率，但是該協議只能適用于單跳網絡中；文獻[6]針對太陽能傳感網的分布式數據采樣率控制算法，通過調節節點在每個時段的采樣率來控制節點的能耗，并優化網絡效用。上述算法雖能優化節點的發送速率，但是均沒有考慮信號沖突與數據時延性能。

針對現有研究的不足，本文提出了一種聯合節點數據采集速率控制與時隙分配(joint node data acquiring rate control and timeslot assignment，JRCTA)跨層優化算法。該算法在沖突避免的基礎上，以最大化效用為目標，通過基于對偶分解的分布式求解算法，優化分配節點的工作時隙以及節點的感應數據采集速率，從而在提高匯聚節點單位時間內的數據采集量和節點的延時性能間獲得較佳平衡。

1　網絡模型和傳播模型

整個網絡由一個匯聚節點(Sink)和多個傳感器節點組成，假設網絡具備如下性質：每個節點以一定速率采集數據并直接發送；節點發送數據的路由已由路由算法事先確定；每個節點發射功率固定為Pt；節點可以作為中繼節點，每個節點的數據緩存足夠大。

網絡的整個數據發送過程分割為多個時間長度相等的數據傳送周期，每個傳送周期再劃分為多個時隙。為避免沖突，需要將時隙合理分配給各節點，節點只在其分配的工作時隙內才能經由一條鏈路發送數據。使用二維數據As[L,M]來表示網絡中各鏈路的時隙占用表，L表示網絡中鏈路的數量，M表示一個數據傳送周期內的時隙數量。如節點選擇鏈路l，且在時隙t內發送數據，則As[l,t]=1。若某鏈路在某時隙內沒有數據發送，則As相應的值為0。

2　沖突圖

根據節點的路由,可以建立網絡拓撲圖，實例如圖1中G所示,節點間的邊表示無線鏈路。另外，為表示不同鏈路間的沖突關系，建立了沖突圖。G所對應的沖突圖G′如圖2所示，沖突圖中的節點表示網絡中的無線鏈路，而圖中的邊表示該邊兩端的節點所代表的無線鏈路會發生沖突，不能安排在同一工作時隙。

圖1　網絡拓撲圖G

圖2　沖突圖G′

結合拓撲圖，沖突圖的建立步驟如下:

1)對于G中每條無線鏈路，在G′中建立一個節點；

2)對于G中的任意一條無線鏈路l,發射節點為t(l),接收節點為r(l)。若存在另一條無線鏈路l′,當兩條鏈路同時發射時，出現以下三種情況,兩條無線鏈路會產生沖突:

a.接收端r(l)或r(l′)的信噪比ψ超過門限值。根據文獻[7]，接收端r(l)的信噪比ψ可由式(1)得到

(1)

式中σ2為噪聲功率，θ為正交因子，t為該鏈路的工作時隙，Fl為會對鏈路l產生干擾的鏈路集合，Pt為節點的發射功率。hij為以i為發送節點，j為接收節點的鏈路的增益。可由下式計算

(2)

式中λ為電磁波的波長，dij為傳播距離，η為傳播損耗系數，Gt與Gr分別為節點發送端與接收端的天線增益。

b.一條鏈路的接收節點是另一條鏈路的發射節點，即r(l′)= t(l) 或r(l) = t(l′)。

c.兩條鏈路的接收節點為同一個節點，即r(l′) =r(l)。

3)對于G中沖突的兩條無線鏈路,在沖突圖G′中對應的節點間建立連線。

3　初始化時隙分配算法

為避免不同節點發送信號產生沖突，需要對每個節點在每個傳送周期內的發送時隙進行分配，建立時隙占用表As。針對任一網絡G的初始化時隙分配算法具體流程見算法1。

算法1初始化時隙分配算法

1)建立網絡G對應的沖突圖G′；

2)初始化時隙占用表As，所有元素的值均設置為0；

3)Foreach鏈路lin網絡拓撲圖G

a.t=1;

b.查看時隙占用表，并計算已使用第t個時隙發送數據的鏈路數量N(t);

c.若N(t)=0，則t確定為鏈路l的工作時隙，即設置As[l,t]=1，N(t)= N(t)+1,l設置為下一跳鏈路，返回a；

d.若N(t)=1,則查看沖突圖，正在使用時隙t 的鏈路和l是否沖突：若不沖突，則As[l,t]=1，N(t)= N(t)+1,l設置為下一跳鏈路，返回a；若沖突，則t= t+1,返回b；

e.若N(t)>1,則根據式(1)重新計算增加鏈路l后，每條使用時隙t 的鏈路接收端的信噪比ψ，若ψ仍然小于一門限值，則As[l,t]=1，N(t)= N(t)+1,l設置為下一跳鏈路，返回a；否則，t= t+1,返回b。

End

利用算法1可以獲得圖1中所表示網絡G的時隙占用表As，并根據As建立發送時隙分配示意圖，如圖3所示。其中，每個數據傳送周期內的時隙數量M為3。

圖3　圖1所示網絡的時隙分配示意圖

4　基于效用優化的節點速率的分布式控制

假設網絡中任一節點s的數據采集速率為Xs，節點的效用函數為U(Xs)，它是嚴格凹且單調增的二次可微函數。擬采用網絡效用最大化的辦法來優化各節點的Xs。效用優化模型還必須滿足兩個約束條件：一個是節點的數據采集速率約束條件；另一個是鏈路容量約束條件，鏈路容量由香農公式計算

(3)

Wl表示以節點s為發送節點的鏈路l的帶寬，ψl表示鏈路l的信噪比,它可由式(1)計算。因為節點僅在分配給它的發送時隙內發送數據，節點s的網絡注入速率為MXs；Setchild(s)為節點s在路由樹中的孩子節點集合。經變換，式(3)可以轉換為

(4)

為方便表示，假設

(5)

結合上述約束條件，網絡的效用優化模型可總結為

(6)

s.t.Xmin≤Xs≤Xmax,?s∈N

(7)

Xs≥us,?s∈N

(8)

式中網絡效用為所有節點效用之和，N表示所有傳感器節點的集合；式(7)表示節點的數據采集速率約束條件，Xmin和Xmax分別表示節點的最小和最大數據采集速率；式(8)表示節點的鏈路容量約束條件。

因為效用函數U(Xs)是嚴格凹且單調增的二次可微函數，所以,問題(6)是凸優化問題，采用對偶分解法來求解該問題。該問題對應的拉格朗日函數為

(9)

式中μ≥0為拉格朗日乘子。對于一個確定的μ，各子節點對應的對偶分解子問題的解為

s.t.Xmin≤Xs≤Xmax

(10)

由于U(Xs)是嚴格凹函數，所以,式(10)的最優解唯一。可以使用梯度投影法求解μ

μ(z+1)=[μ(z)-α(Xs-us)]+

(11)

綜上所述，基于對偶分解的節點優化數據采集速率分布式求解算法描述如算法2。

算法2節點數據采集速率分布式求解算法

初始化：設z=1,μ是任意非負值，Xs設置為Xmin，T=Φ,T*=Φ

Repeat

fors=1,2,…,n

a.節點s廣播自己的Xs的值；

b.每個節點接收和轉發來自其干擾節點和孩子節點發來的Xs的值；

c.節點s計算U(Xs)，并使用式(5)計算us；

e.節點s使用式(11)更新μ(z+1)，并廣播；

end

z=z+1;

ifT={Xs,s=1,2,…,n}

T*= T

else

T={Xs,s=1,2,…,n}

end

UntilT*≠?

ReturnT*。

5　JRCTA算法

每個節點到達匯聚節點的路由形成了一顆路由樹，根據本文所提的調度原則，每個數據傳送周期中每個節點僅占用一個發送時隙發送數據，即感應數據在每個數據傳送周期僅前進一跳，那么在路由樹中所處的層次為h的節點的數據需要經過h跳才能到達匯聚節點，所以,該節點發數據到Sink的時延期望為hMT(T為一個發送時隙的長度)。在路由不變的情況下，要減小數據發送到Sink的時延，就要減少每個數據傳送周期的時隙數量M,但時隙數量過低會造成許多節點使用同一個時隙發送數據，這加大了節點間的相互干擾，增加了節點的信噪比，也限制了和節點速率相關的網絡效用的提高。所以，將網絡速率控制和時隙數量M的確定，以及時隙分配歸納為一個效用優化問題，進行聯合優化。優化目標函數F修改為

(12)

優化目標為最大化 F。式(12)采用加權組合法求解這個兩目標的聯合優化問題，其中，w1與w2為加權因子，w1∈[0,1]為本征權，反映各指標相對重要性，而w2為校正權，用來調整兩個優化目標在數量級上差別。這樣，最大化網絡效用與最小化時隙數量M構成了一個兩目標的數學規劃問題。基于上述優化模型，提出了一種JRCTA跨層優化算法(算法3)來求解問題。

算法3JRCTA優化算法

1)利用算法1進行初始化時隙分配，確定初始化的M,計算并獲得時隙占用表As。

2)利用算法2計算當前時隙分配下的最大化網絡效用和節點優化采集速率，并使用式(12)計算優化目標函數F的值。

3)尋找被最多鏈路同時占用的時隙t,如果有k 條鏈路使用該時隙 ，則挑選k/2 條鏈路，將它們的發送時隙設置為第M+1個時隙，并修改時隙占用表As。

4)利用算法2重新計算最大化網絡效用，并使用式(12)計算修改后的優化目標函數F*的值。

5)F與F*比較，若F*>F，則F= F*， M=M+1,確定修改時隙占用表，返回(3)；若F*≤F，則說明擴大M無法增大優化目標函數的值，取消此次修改并退出。

使用算法3對圖1所示網絡在初始化時隙分配的基礎上繼續優化，可得出M 擴大為4，鏈路k的發送時隙變動到第4個發送時隙上。

6　實　驗

利用OPNET作為仿真平臺對JRCTA算法的時延性能進行評估。如無特別指定，實驗中的參數設置如下:Wl=20kHz,噪聲帶寬BN=30kHz,噪聲功率σ2=5×10-10mW,η=2,θ=1/256,λ=0.3m,GtGr=4,節點功率為1mW,節點數據采集速率范圍為[1kb/s,300kb/s]。節點效用U(Xs)=log(Xs)。

首先，網絡采用圖1所示的實驗場景，共7個節點，節點A為匯聚節點。網絡的每個數據傳送周期采用不同數量的發送時隙,根據算法2計算每個節點的優化速率，并經過仿真獲得網絡的效用，其結果如圖4所示。

圖4　不同M值下的網絡優化效用

從圖4可以看出，當節點的每個數據傳送周期內的時隙數量M開始增加時，網絡效用不斷提高，這是由于不同節點可以安排在不同的時隙內發送，減小了節點的相互干擾，可以提高節點速率；但當M增加到等于或超過節點數量時(M≥6)，網絡效用不再增加,實驗結果與分析結果一致。

圖5反映了當本征權w1分別為1和0.5時，不同節點數量的網絡采用JRCTA算法獲得的節點速率后的網絡效用值。w1為1時，根據式(12)，優化過程中實際上并沒有考慮網絡的時延性能。從圖5可以看出：w1取0.5時網絡所獲得的效用要大于w1取1時的網絡效用，這說明JRCTA算法的時隙優化分配通過恰當增加每個數據傳送周期內的時隙數量，減少了同一個時隙發送數據的節點數量， 有效減少了節點間的干擾，提高了網絡效用。

圖5　不同節點數量下的網絡優化效用

7　結　論

提出了一種WSNs中JRCTA的效用優化算法。該算法在沖突避免的基礎上，建立統一速率控制與時隙分配的效用優化模型 ，并通過基于對偶分解的分布式的優化算法求解該模型，優化分配節點的工作時隙，并獲得節點的優化數據采集速率。最后，實驗結果表明：本文所提算法在控制網絡延時性能的前提下，最大化匯聚節點在單位時間內所采集到的數據量。

[1]劉洪濤，程良倫.基于優先級的服務區分和速率控制策略[J].計算機應用，2011,31(6)：1458-1460.

[2]趙永輝，史浩山.基于云模型的無線傳感器網絡擁塞及速率控制策略[J].傳感技術學報,2010,23(1):133-138.

[3]朱曉亮，杜旭，楊宗凱，等.無線傳感器網絡實時媒體傳輸速率控制機制[J].小型微型計算機系統，2007,28(2):199-203.

[4]馬寧,李開宇,吳寅,等.基于最大流的能量采集型無線傳感器網絡路由算法[J].傳感器與微系統，2013，32(1):131-134.

[5]Koutsopoulos I,Stanczak S,Feistel A.Transmit rate control for energy-efficient estimation in wireless sensor networks[C]∥Global Telecommunications Conference,GLOBECOM 2010,Miami,Florida,USA:IEEE,2010:1-5.

[6]Zhang Y M,He S B,Chen J M,et al.Distributed sampling rate control for rechargeable sensor bodes with limited battery capaci-ty[J].IEEE Transactions on Wireless Communications,2013，12(6)：3096-3106.

[7]He Shibo,Chen Jiming,Yau D K Y,et al.Cross-layer optimization of correlated data gathering in wireless sensor networks[J].IEEE Transactions on Mobile Computing,2012，11(11):1678-1691.

An utility optimization algorithm based on joint rate control and timeslot assignment for wireless sensor networks*

LIU Tao

(School of Computer Science and Technology,Southwest University for Nationalities,Chengdu 610041,China)

A joint node data acquiring rate control and timeslot assignment (JRCTA) algorithm is proposed for wireless sensor networks(WSNs).An unified utility optimization model based on rate control and timeslot assignment is established,the optimization control of data sampling rate is combined with timeslot assignment collision avoidance.It can maximize total quantity of data collected by sink node per unit time on the premise that end-to-end delay is restricted.Simulation results show that JRCTA algorithm performs well.

wireless sensor networks(WSNs); rate control; timeslot assignment; utility optimization

10.13873/J.1000—9787(2016)09—0144—04

2015—10—21

國家民委科研項目(14XNZ030);四川省教育廳科研重點項目(15ZA0395)

TP 393

A

1000—9787(2016)09—0144—04

劉韜(1978-),男,四川宣漢人,博士后,副教授,CCF會員,主要研究方向為無線傳感器網絡。