傳感器網絡中基于跨層調度的數據融合策略

摘要：針對現有的協議都不能在獲得良好的節能效果和低延遲的同時，使每一個節點進行充分的數據融合的問題，提出一種基于跨層調度的數據融合策略，根據建立的路由樹，制訂無碰撞的數據發送調度方案并為每一個傳感器節點設置合理的等待時間。仿真結果表明此策略節能效果明顯、延遲小并且吞吐量大。

關鍵詞：傳感器網絡; 數據融合; 跨層調度; 節能

中圖分類號：TP391文獻標志碼：A

文章編號：1001－3695(2008)01－0168－03

無線傳感器網絡由大量隨機分布的集成傳感器、數據處理單元和通信模塊的微小節點組成，通過自組織的方式構成網絡。無線傳感器網絡中節點的能量資源、計算能力和帶寬都非常有限，而且傳感器節點十分密集，設計有效的策略延長網絡的生命周期成為無線傳感器網絡的首要問題[1]。

在網絡層進行數據融合能夠有效地減少無線傳感器網絡中存在的大量冗余信息。當數據報（原始的或融合處理過的）從許多傳感器節點向單個sink節點發送時，形成多級數據融合。在多級的數據融合中，每一級都會接收到存在時間間隔的多個數據報，等待的時間越長，收到的數據報越多，延遲越大，吞吐量越小。每一個傳感器節點都必須設置合理的等待時間。

若每一個節點的觸發時間都是同一個固定的時間，將增加延遲或降低融合數據的效率。文獻[2]中的MFS（多級融合同步）協議為每一級設置不同的觸發時間，其中sink節點的觸發時間最長。同一級節點的觸發時間相同，同級的兄弟節點會發生碰撞。基于簇的路由協議如LEACH[3]和TEEN[4]在簇頭進行數據融合，以減少網絡流量。簇頭的負載大，并且端到端的延遲大。

為了在保證延遲允許的前提下更加高效地進行數據融合，本文提出一種基于跨層調度的數據融合策略，建立一棵較好的路由樹，制訂無碰撞的數據發送調度方案，為每一個鏈路分配合理的時間片，從而為每一個節點設置適當的等待時間。每一個節點都只會在需要接收或發送數據報時才會蘇醒，這樣能保證在取得良好的性能的同時最大程度地節約能量。

1基于跨層調度的數據融合策略

對于分簇結構的傳感器網絡，每個簇內的傳感器節點周期性地產生數據報文，經簇頭轉發到sink節點，形成樹型路由結構?？刂茍笪暮蛿祿笪亩荚谕粋€信道上傳送。與傳感器節點相比，簇頭具有較強的計算能力和較多的能量。

數據融合策略分為以下兩個階段：

a)建立和重配置階段。在網絡的初始階段和網絡拓撲結構發生變化時，執行建立和重配置階段為平穩調度階段建立準確的調度，包括建立路由樹以及為數據報和ACK制訂無碰撞調度。與平穩調度階段相比，其執行時間很短。

b）平穩調度階段。利用在建立和重配置階段建立的調度表調度數據報。每一個節點在完成接收、融合和發送數據報后進入休眠狀態。當所有的數據報都被轉發到sink節點時，所有的節點都將蘇醒以接收ACK，判斷sink節點是否接收到自己的數據報并且將自己的時間與sink節點進行同步。

網絡拓撲結構發生改變一般是由節點死亡引起的，這種改變并不經常發生。數據融合策略在平穩調度多輪（一秒鐘一輪）后才執行建立和重配置階段（一天一次），將絕大部分的能量用于平穩調度。

1．1建立和重配置階段

每一個傳感器節點交換探測包，本地選擇父節點，并將其一跳的鄰居信息發回sink節點，建立路由樹。在收到每一個節點的鄰居信息后，sink節點根據全局的拓撲信息為每一個傳感器節點進行無碰撞信道分配，包括基于鏈路的數據信道分配和基于節點的ACK信道分配。

1．1．1建立路由樹

每一個傳感器節點都需要選擇父節點，找到一條更好的路徑將自己連同一跳的鄰居節點的信息發送到sink節點。建立一棵好的路由樹能夠有效地融合數據并更好地執行路由和MAC協議，從而節約能量、減少延遲并獲得較高的吞吐量[5]。

傳感器節點發送能量遞減的測試信號，通過檢測應答來確定離自己最近的相鄰節點作為父節點，調整發送功率以減小沖突域，并將其鄰居節點信息發送給sink節點。通過這種方式，網絡中的所有傳感器節點都能夠了解彼此的位置關系，進而依據自己的位置選擇所屬的簇，簇頭再參照位置關系優化出到sink節點的最佳鏈路，建立一棵以sink節點為根節點的路由樹。

1．1．2基于鏈路的數據信道分配

定義1無線傳感器網絡的路由樹可用由節點和鏈路構成的有向圖表示，記為G=（V，E）。其中：

V表示節點集合；

E表示有向鏈路集合；

e(i， j)為節點i和j之間的有向鏈路，即節點i能夠直接發送一個數據報給節點j。

在無線傳感器網中兩個通信的發送者和接收者都不相同，仍然可能沖突，這就是隱藏節點問題[6]。圖1中兩條不相鄰的邊對應的兩條鏈路存在沖突，這兩條邊則不能分配相同的時間片。使用構建路由樹時收集到的每個傳感器節點的鄰居節點信息可以解決無線通信中的隱藏節點問題，基于跨層調度的數據融合策略使用沖突檢測算法[7]來確定圖1中所有可能沖突的邊。

1 n(i):node i in G

2 e(i，j):a transmission from n(i) to n(j) in G;

3 NS(j): the neighbor set of the node j;

4 for each e(i，k)∈G {

5 for each e(j，l) and (i≠j and k≠1){

6 if (n(i)∈NS(l) or n(j)∈NS(k)){

7 adding a broken line e between e(i，k) and e(j，l) in G;

8 }}}

即使保證所有的鄰接和沖突的鏈路都被分配了不同的時間片，這樣的調度也只能確保發送數據報時沒有碰撞，可能會影響數據融合的效果和增加延遲。如圖1所示，若鏈路L1和L11被分配了同一個時間片，簇頭將在沒有融合節點1的數據報的情況下發送數據報，而節點1的數據報只能到下一輪才能發送給sink節點。實際的網絡拓撲結構比圖1復雜得多，因而實際情況可能會更糟。為了解決這個問題，基于跨層調度的數據融合策略從底層的鏈路(即編號小的鏈路)開始分配時間片，并保證每個鏈路分配的時間片都要比其下屬鏈路晚。其具體算法如下：

1 slot(i):the time slot of the link i;

2 is(i):the interfering link set of the link i;

3 as(i): the adjacent link set of the link i;

4 let the initial slot of all the links to be 0;

5 for i=1..MAXLINK {

6 find out the max slot(MAXSLOT) of the underling links of link i;

7 check if MAXSLOT has been assigned to the links of the interfering and adjacent link sets except for its underling links;

8 if yes， let MAXSLOT=MAXSLOT+1 and goto line 7;

9 otherwise， assign slot(i)=MAXSLOT; }

1．1．3基于節點的ACK信道分配

在數據報文全部發送完以后發送ACK，能夠減少數據報文的沖突域，提高數據信道的共用性。在路由樹中一個父節點（接收節點）有多個子節點（發送節點），同時ACK負載相似并且很小，可以將多個ACK放在一個數據報中。另外，無碰撞的數據報調度采用分配時間片的方式，對時間精度要求較高，可將sink節點的時間同步信息也封裝在ACK中。

圖1圖G（基于路由樹）

Sink節點廣播ACK，每一個子節點都能通過檢查這個ACK來查看自己的數據是否被成功地接收并且將自己的時間與sink節點同步，然后再廣播這個ACK。這樣ACK迅速地到達所有節點，減少了延遲，并且發送量少，降低了網絡流量，減少了能耗。

1．2平穩調度階段

節約能量最好的方法是讓節點休眠，然而休眠的節點不再是網絡的一部分，不能再將其鄰居節點的數據報轉發到sink節點，讓節點休眠必須十分謹慎。在平穩調度階段，每一個節點根據在建立和重配置階段制訂的調度表在指定時間片內發送和接收數據報，完成轉發數據報后開始休眠。當所有的數據報都被轉發到sink節點時，所有的節點都將蘇醒以接收ACK，判斷sink節點是否接收到自己的數據報并且將自己的時間與sink節點進行同步。若節點發現sink節點沒有成功接收到自己的數據報，將在下一輪進行重發。

2性能評價

采用OMNeT++[8]作為實驗平臺，模擬實現了基于跨層調度的數據融合策略和SMAC[9]協議（采用相同網絡路由結構）并進行了性能比較（由于SMAC產生虛擬簇，不適用于分簇網絡，在實驗中對SMAC進行了一些修改，但不會影響其性能）。

其實驗場景是：節點均勻分布在800 m×600 m的區域內，通信范圍R=75 m，初始時設置32個節點，以32的增長率一直增加到192個節點。節點的初始能量為2 J，數據報文的長度為512 Byte，ACK的長度為32 Byte，通信帶寬為10 Mbps，采用發送能耗24.75 mW、接收能耗13.5 mW、休眠能耗0 mW的能量模型。

2．1評價指標

1）一輪的能耗傳感器網絡的所有節點在一輪(round)[11]中將數據報文成功轉發到sink節點所消耗的總能量。一輪的能耗越小，表明其網絡的生命周期就會越長。

2）端到端的延遲在一輪中，所有的傳感器節點從產生數據報文到將其成功轉發到sink節點的時間差的總和。端到端的延遲越小，表明其網絡的吞吐量越大。

2．2實驗結果與分析

如圖2所示，基于跨層調度的數據融合策略具有比SMAC協議更好的節能效果。隨著節點數目的增加，其效果更加明顯。因為數據融合策略給每個節點分配了不會產生碰撞的時間片，隨著節點的增多，其仍然沒有碰撞。SMAC協議由于碰撞隨之增多，能耗迅速增加。另外，數據融合策略不需要額外地控制信息，將絕大部分的能量都用于數據報的調度。

如圖3所示，基于跨層調度的數據融合策略的端到端延遲與SMAC協議相比要小得多，隨著節點的增多，兩者之間的差距更加明顯。因為隨著節點的增多，一方面數據融合策略雖然分配的時間片會增多，但是能夠更好地并行無碰撞調度；另一方面SMAC由于碰撞的顯著增多引起了大量重傳。此外，數據融合策略將數據報和ACK調度分開，能夠減少數據報文的沖突域，提高數據信道的共用性。

圖2一輪的能耗與節點數量的關系圖3端到端的延遲與節點數量的關系

3結束語

基于跨層調度的數據融合策略為每一個傳感器節點設置合理的等待時間并提供無碰撞的數據發送調度方案。在完成數據報文發送后采用基于節點的ACK發送方式，不僅充分地利用了無線信道的特點，而且有效地減小了沖突域。仿真實驗結果表明其不僅節能效果顯著而且延遲小、吞吐量大。隨著節點的增多，優勢更加明顯。

靠近簇頭的傳感器節點由于需要轉發數據報文，需要較長時間地處于接收狀態，會比其他節點更早死亡，成為熱點(hot spot)[12]。下一步的工作就是平衡網絡負載，消除熱點，進一步延長網絡生命周期。

參考文獻：

[1]任豐原，黃海寧，林闖.無線傳感器網絡[J].軟件學報，2003，14(7):1282 1291.

[2]WEI Yuan， KRISHNAMURTHY S V， TRIPATHI S K.Synchronization of multiple levels of data fusion in wireless sensor networks[C]//Proc ofIEEE Global Telecommunications Conference. 2003:221－225.

[3]HEINZELMAN W， CHANDRAKASAN A， BALAKRISHNAN H.Ener￣gy efficient communication protocol for wireless sensor networks[C]//Proc of Hawaii Int’l Conf on System Sciences.San Francisco:IEEE Computer Society， 2000:1 10.

[4]MANJESHWAR A，AGRAWAL D P.TEEN:a protocol for enhanced efficiency in wireless sensor networks[C]//Proc of the 15th Parallel and Distributed Processing Symp.San Francisco:IEEE Computer So￣ciety，2001:2009－2015.

[5]LINDSEY S， RAGH C S. Pegasis:power efficient gathering in sensor information systems[C]//Proc of the IEEE Aerospace Conference.Montana:IEEE Computer Society，2002:1－6. 

[6]AKYILDIZ I F，SU W，SANKARASUBRAMANIAM Y. Wireless sensor networks:a survey[J].Computer Networks，2002，38(4):393－422.

[7]CHOU C F， CHAUNG K T. CoLaNet: a cross layer design of energy efficient wireless sensor networks[C]//Proc of IEEE International Conference on Sensor Networks. Washington D C: IEEE Computer Society， 2005:364－369.

[8]OMNeT++ discrete event simulation system[EB/OL].[2006－09]. http://www.omnetpp.org.

[9]YE Wei， HEIDEMANN J， ESTRIN D. An energy efficient MAC protocol for wireless sensor networks[C]//Proc of the 21st Conference of the IEEE Computer and Communications Societies.New York:ACM Press， 2002:1567 1576.

[10]SICHITIU M L. Cross layer scheduling for power efficiency in wireless sensor networks[C]//Proc of the 23rd Annual Joint Conf of the IEEE Computer and Communications Societies.2004:1740 1750.

[11]MADAN R， CUI Shu guang， LALL S， et al.Cross layer design for lifetime maximization

in interference limited wireless sensor networks[J]. IEEE Trans on Wireless Communication，2006，5(11):3142－3152.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”