向亦宏，朱燕民

(上海交通大學計算機科學與工程系，上海 200240)

1 概述

由于無線網(wǎng)絡中的節(jié)點是通過廣播信號來傳輸數(shù)據(jù)包的，位于節(jié)點附近的其他節(jié)點可以監(jiān)聽到這些信號，因此如果有2 個相鄰節(jié)點同時進行數(shù)據(jù)傳輸，它們發(fā)出的信號就會互相干擾，造成數(shù)據(jù)包的丟失以及網(wǎng)絡吞吐量的降低。現(xiàn)今，無線傳感器網(wǎng)絡(Wireless Sensor Network，WSN)越來越多地被部署到醫(yī)療、災害管理等數(shù)據(jù)密集型業(yè)務中，這些業(yè)務經(jīng)常因為無線通信信道繁忙而受到嚴重的干擾。對遭受干擾的節(jié)點的性能進行精準刻畫，對擁塞控制、速率分配、信道分配等無線協(xié)議的有效運作具有重要的意義。因此，在無線傳感網(wǎng)絡中準確而快速地對當前的干擾狀況進行建模變得極其重要。

本文分別提出集中式算法和分布式算法，對傳感器網(wǎng)絡中的節(jié)點建立PRR-SINR 模型，并在含有17 個TelosB 節(jié)點的WSN 中對2 種算法進行性能評估。

2 相關(guān)研究

目前，對無線網(wǎng)絡中的干擾進行建模的方法較多，如基于跳數(shù)的模型［1］、基于距離的模型［2］和基于協(xié)議的模型［3］。這些模型都基于一個簡單的假設:數(shù)據(jù)包的接收與干擾之間的關(guān)系是二元的。當符合某種條件時，數(shù)據(jù)包一定會被節(jié)點接收，反之則一定不會被節(jié)點接收。文獻［4-6］中的分析表明這些模型并不精確。

在文獻［5-7］中，一個被稱為物理模型或者PRRSINR 的模型被提出，并被用于MAC 協(xié)議的設計中。文獻［6］比較了PRR-SINR 模型和其他基于二元關(guān)系的模型，得出的結(jié)論是PRR-SINR 性能最優(yōu)，利用PRR-SINR 模型可以有效提高鏈路調(diào)度和網(wǎng)絡拓撲控制的性能［6-9］。

文獻［9-11］通過實驗表明，不同時間、不同地點，節(jié)點所測得的PRR-SINR 模型是不同的，實驗結(jié)果如圖1 所示。其中，圖1(a)為同一個節(jié)點在不同時刻所測得的PRR-SINR 模型;圖1(b)為同一個節(jié)點在不同位置所測得的模型。因此，需要為無線傳感器網(wǎng)絡中的每一個節(jié)點都建立一個PRR-SINR 模型，并周期地更新該模型。

圖1 不同時刻、不同位置節(jié)點測得的PRR-SINR 模型

文獻［6］中采用隨機選取無線傳感器網(wǎng)絡中不同的鏈路的方法來測量PRR-SINR 模型。文獻［10］提出了一種被動式的測量PRR-SINR 模型的方法。它不需要節(jié)點主動發(fā)送測量包，而僅僅是記錄各個節(jié)點發(fā)送正常數(shù)據(jù)包的時間戳以及節(jié)點成功接收數(shù)據(jù)包時的時間戳。每個節(jié)點將所記錄的時間戳發(fā)送給一個中心節(jié)點，由該節(jié)點來為每個節(jié)點生成PRR-SINR模型。上述方法都需要測量很長時間才能獲取整個網(wǎng)絡的PRR-SINR 模型。為此，本文分別提出一個分布式算法和集中式算法，對WSN 中的節(jié)點建立PRR-SINR 模型。集中式算法通過一個中心節(jié)點控制節(jié)點收發(fā)測量包，使每個節(jié)點可以逐步地建立模型，分布式算法則依賴每個節(jié)點自主控制自己的收發(fā)包狀況進行建模。

3 系統(tǒng)模型與問題描述

3.1 系統(tǒng)模型

在無線傳輸中，信號干擾噪聲比(Signal to Interference and Noise Ratio，SINR)的定義如下:

其中，P 為接收節(jié)點測量到的發(fā)送節(jié)點的發(fā)送功率;I代表的是接收節(jié)點測量到的干擾節(jié)點的發(fā)送功率;N是環(huán)境噪聲。PRR-SINR 模型可以用以下公式來描述:

如圖1 所示，PRR-SINR 模型中存在一個過渡區(qū)域。過渡區(qū)域以外的包接收率為0 或者100%。而過渡區(qū)內(nèi)的包接收率在0～100%之間。因此，只需要考慮如何刻畫過渡區(qū)域即可。因為大多數(shù)傳感器節(jié)點的RSSI(接收信號強度寄存器)能夠提供的RSS(接收信號強度)值的精度為1 dBm，所以信號與干擾的RSS 值的差值精度為1 dB，此差值即為所求SINR。文獻［6］經(jīng)過實際測量，得出過渡區(qū)間在［0，5 dB］，因此，僅需要為每個節(jié)點測量6 個整數(shù)SINR 所對應的PRR 即可為該節(jié)點構(gòu)建完整的PRR-SINR模型。

3.2 問題描述

本文的目標是使用最少的測量包來為WSN 中的每一個節(jié)點構(gòu)建PRR-SINR 模型。基本方法如下:在WSN 中選取一些節(jié)點作為一個發(fā)送子集。這個子集中的每個節(jié)點從某個時刻開始需要同時以相同的間隔發(fā)送指定數(shù)目(M)的測量包。從發(fā)包開始到結(jié)束的這段時間稱為一個輪次?？梢哉J為每個節(jié)點事先都已經(jīng)測量了該節(jié)點接收其鄰居節(jié)點發(fā)出的數(shù)據(jù)包的RSS，并且這些RSS 在短期內(nèi)不會變化。

例:圖2 中r1，r2，r3 組成了一個發(fā)送子集，其中，r2 是m 的鄰居節(jié)點，r1 和r3 是干擾節(jié)點，圖中虛線代表干擾鏈路。

圖2 PRR-SINR 點的測量

輪次開始后，這3 個節(jié)點同時發(fā)包。m 節(jié)點在此輪中處于監(jiān)聽模式。它收到r2 發(fā)出的包時，從RSSI 中讀取接收此包的RSS(包含了背景噪聲，r1，r3 的干擾信號強度)。由于r2 是m 的鄰居節(jié)點，因此m 節(jié)點保存了在無干擾的情況下，接收r2 數(shù)據(jù)包的RSS。m 節(jié)點可以據(jù)此計算出接收此包的SINR:

如果得出的SINR 還沒有對應的PRR 值，那么m 在此輪中只統(tǒng)計接收到的r2 發(fā)出的數(shù)據(jù)包的個數(shù)。在該SINR 下，節(jié)點m 的包接收率公式為:

則稱在該發(fā)送子集下，m 獲取了一個PRR-SINR點。

通過上述步驟，可以逐步為網(wǎng)絡中的每一個節(jié)點構(gòu)造PRR-SINR 模型。本文選擇K 個發(fā)送子集組成一個發(fā)送集合S。當一個發(fā)送子集形成的輪次結(jié)束后，節(jié)點m 可以獲取0 個或1 個PRR-SINR 點。令fs(nodem)≥N 代表發(fā)送集合S 中的發(fā)送子集都發(fā)完測量包后，節(jié)點m 總共可以計算出的PRR-SINR點的個數(shù)。每個節(jié)點需要在過渡區(qū)域中獲取至少N 個PRR-SINR 點，即需要滿足以下條件:

因為一個發(fā)送子集中的每個節(jié)點都需要發(fā)送M 個測量包，所以為了達到使用最少測量包的目標，筆者希望選擇K 個發(fā)送子集，這些子集含有的節(jié)點的數(shù)目的和是最少的。本文問題描述如下:

3.3 復雜度分析

引理1 選擇集問題是NP 的。

證明:NP 類由這樣的問題∏組成，對于這些問題存在一個確定性算法A，該算法在對∏的一個實例展示一個斷言解時，它能在多項式時間內(nèi)驗證解的正確性［12］。

在本文的選擇集問題中，如果給定一個發(fā)送集合S={s1，s2，…，sk}，則需要驗證是否有:

引理2 集合覆蓋問題可以歸約到選擇集問題。

證明:給定集合W={w1，w2，…，wm}和V={v1，v2，…，vt}，vi為W 的子集。集合覆蓋問題可以描述為:

其中，S 為V 的一個子集，si為S 中的元素，為si的權(quán)重。集合覆蓋問題即要求從V 中找到一個子集，這些子集中元素的并集包含了W 中的每個元素，并且子集中元素的權(quán)重的和最小。

在本文的選擇集問題中，如果一個發(fā)送子集si可以使節(jié)點i 獲取一個PRR-SINR 點，則稱si覆蓋了節(jié)點i。si的權(quán)重為si中發(fā)送節(jié)點的個數(shù)。令N=1，如果S*={s1，s2，…，sk}是本文選擇集問題的解，也就是說找到了一個集合S*，它滿足每個節(jié)點都被覆蓋一次的條件。顯然，這個解也就是集合覆蓋的解。也即當且僅當S*為選擇集問題的解時，S*為集合覆蓋的解。因此，可以把集合覆蓋問題歸約到選擇集問題。

定理 選擇集問題是一個NP 完全問題。

證明:由引理1 和引理2 可以得出，選擇集問題是一個NP 完全問題。

4 集中式算法

在集中式算法中，要求網(wǎng)絡中每個節(jié)點都需要事先測量收到鄰居節(jié)點數(shù)據(jù)包時的RSS，然后將這些數(shù)據(jù)發(fā)送給一個中心節(jié)點。中心節(jié)點使用這些數(shù)據(jù)模擬出一個發(fā)送子集，測試那些不在發(fā)送子集中的節(jié)點能否通過此發(fā)送子集獲取一個PRR-SINR點，進而計算出建立整個網(wǎng)絡的PRR-SINR 模型所需要的發(fā)送子集的集合。中心節(jié)點完成計算后，在每一個輪次開始之前告訴其他節(jié)點在該輪如何表現(xiàn)，例如直接加入發(fā)送子集充當發(fā)送者，或者只是統(tǒng)計收到某個節(jié)點發(fā)出的數(shù)據(jù)包的個數(shù)，從而構(gòu)建某個PRR-SINR 點。

由于選擇集問題是一個NP 完全問題，因此本文提出一個貪心隨機算法，該算法部署在中心節(jié)點上，能在多項式時間內(nèi)提供一個近似解。算法的具體步驟如下:

(1)發(fā)送子集集合S={}。

(2)發(fā)送子集si清空。

(3)隨機從網(wǎng)絡中選擇一個節(jié)點加入到發(fā)送子集si，將Xmax設置為0。

(4)遍歷所有不在發(fā)送子集中的節(jié)點，測試將該節(jié)點i 臨時加入到發(fā)送子集后，能獲取PRR-SINR 點的節(jié)點的個數(shù)X。

(5)選擇步驟(4)中最大的X 以及對應的節(jié)點i，如果X 大于Xmax，那么將節(jié)點i 正式加入發(fā)送子集si，將Xmax設置為X，繼續(xù)4)。如果Xmax為0 的次數(shù)超過了一個閾值，則跳轉(zhuǎn)到步驟(7)。

(6)如果Xmax大于0，將該發(fā)送子集si加入S，判斷每個節(jié)點是否都已經(jīng)建立了PRR-SINR 模型，如果仍沒有建立，則繼續(xù)執(zhí)行步驟(2)。

(7)結(jié)束。

5 分布式算法

在集中式算法中，由一個中心節(jié)點來決定網(wǎng)絡中的節(jié)點是否加入發(fā)送子集中。而在本文提出的分布式算中，每個節(jié)點需要自己來判斷是否成為發(fā)送子集中的一員。只有當發(fā)送子集形成后，其他節(jié)點才能獲知自己能否通過此子集來得到一個未使用過的SINR 點。因此，節(jié)點不能預知自己做出的決策是如何影響其他節(jié)點的。本文通過一個啟發(fā)式的方法來幫助節(jié)點判斷自己是否加入發(fā)送子集。

如3.1 節(jié)所述，需要為每個節(jié)點測量6 個SINR所對應的PRR。本文根據(jù)這個事實來給每個節(jié)點提供決策依據(jù):當節(jié)點得知它的鄰居還需要計算的PRR-SINR 點數(shù)的平均值大于本節(jié)點剩余PRR-SINR點數(shù)時，節(jié)點以概率P1(大于0.5)加入發(fā)送子集，否則節(jié)點以概率P2(小于0.5)加入。這樣，可以讓那些還需測量更多PRR-SINR 點數(shù)的節(jié)點優(yōu)先充當接收者，從而盡可能地測量出更多的PRR-SINR 點。為了讓節(jié)點更有效地參與建模，定義另一個規(guī)則:如果某個節(jié)點在一輪結(jié)束后發(fā)現(xiàn)它的鄰居節(jié)點的PRR-SINR 點數(shù)與上一輪是一樣的，那么認為該節(jié)點在此輪中的表現(xiàn)是無價值的，需要對該節(jié)點進行懲罰，即如果該節(jié)點在此輪中是發(fā)送者，那么在下一輪中，需要降低該節(jié)點充當發(fā)送者的概率;同樣的，如果該節(jié)點在此輪中是接收者，那么在下一輪中該節(jié)點將更有可能充當發(fā)送者。

實驗結(jié)果表明，上述規(guī)則可使發(fā)送節(jié)點的數(shù)目減少約33%。本文將發(fā)送輪次限制為N，力圖保證模型精度的前提下，使用盡可能少的節(jié)點發(fā)送測量包。

分布式算法部署在網(wǎng)絡中的每個節(jié)點上，算法的具體步驟如下:

(1)節(jié)點以概率P 確定自己是否加入發(fā)送子集充當發(fā)送者，充當發(fā)送者的話，節(jié)點開始以固定頻率發(fā)送測試包。發(fā)送完指定數(shù)目的測試包后，轉(zhuǎn)入步驟(3)。

(2)節(jié)點i 充當接收者，處于監(jiān)聽模式。當成功收到節(jié)點K 發(fā)送的測試包時，計算此時的SINR，如果該SINR 沒有對應的PRR，則接下來節(jié)點i 只統(tǒng)計收到K 發(fā)送的包的個數(shù)，計算PRR。

(3)各個節(jié)點對外廣播自己還剩余的PRR-SINR點數(shù)。其余節(jié)點更新鄰居還剩PRR-SINR 點數(shù)。據(jù)此計算出節(jié)點在下一個輪次充當發(fā)送者的概率。

(4)如果已進行的輪次數(shù)目沒有達到N，則繼續(xù)步驟(1)。

(5)結(jié)束。

6 性能評估

本文實驗平臺由17 個運行TinyOS-2.02 系統(tǒng)的TelosB 節(jié)點構(gòu)成，一個節(jié)點充當中心節(jié)點，其余16 個節(jié)點均勻分布在4 m ×4 m 的空間上。上文所述的集中式算法和分布式算法均在此平臺上進行性能評估。

6.1 精度評估

本文采用文獻［5-7］中使用的一種主動干擾測量方法(簡稱ACTIVE 方法)來與本文提出的方法進行比較。該方法通過m 輪的測量，為一個節(jié)點構(gòu)造生成一個PRR-SINR 模型。當要為節(jié)點m 生成模型時，先為m 節(jié)點選取一些輔助節(jié)點，這些輔助節(jié)點負責在每一輪中以相同的時間間隔廣播數(shù)據(jù)包。m 節(jié)點事先知道接收這些節(jié)點發(fā)出的數(shù)據(jù)包的RSS。這樣，m 節(jié)點在每一輪選取一個輔助節(jié)點r，計算此時的SINR 以及接收到的r 發(fā)出的包的個數(shù)。通過改變輔助節(jié)點的發(fā)送功率，m 節(jié)點可以計算出不同的SINR，從而生成一個完整的PRRSINR 模型。文獻［5-7］的實驗結(jié)果表明，如果輪次足夠多，則上述方法建立的PRR-SINR 模型可達到較高的準確率。

本文以4 096 輪次的ACTIVE 方法所構(gòu)建的PRR-SINR 模型為基準，評估本文提出的方法的精確性。實驗的具體步驟如下:

(1)使用集中式算法測得整個網(wǎng)絡的PRR-SINR模型。

(2)使用分布式算法再次為每個節(jié)點構(gòu)造PRR-SINR模型，重復多次。

(3)通過ACTIVE 方法為每個節(jié)點生成PRRSINR 模型。

(4)將集中式算法和分布式算法為每個節(jié)點所計算的模型與ACTIVE 生成的相比較，計算出節(jié)點過渡區(qū)域中每個SINR 對應的PRR 與ACTIVE 相比的絕對誤差值。

2 種算法為每個節(jié)點生成模型的平均誤差累計分布函數(shù)(Cumulative Distribution Function，CDF)圖如圖3 所示。其中，分布式算法輪次分別限制為30 輪和100 輪?？梢钥闯?，集中式算法得到的PRR-SINR模型精度較高，最大平均誤差為5.7%，中值只有4.6%。30 輪的分布式算法所得模型最大平均誤差9.4%，中值為7.0%。100 輪的分布式算法精度有一定提升，最大平均誤差6.5%，中值降到4.5%。

圖3 2 種算法所得模型的平均誤差CDF 圖

6.2 開銷評估

本文用實驗中收集的數(shù)據(jù)在PC 上窮舉所有可能的發(fā)送子集集合，從滿足條件的集合中，找出最少的發(fā)送者數(shù)目，然后將之與集中式算法和30 輪分布式算法進行比較，結(jié)果如圖4 所示?？梢钥闯?，集中式算法平均所需的發(fā)送者個數(shù)與最優(yōu)解很接近，其最差的表現(xiàn)也不超過最優(yōu)解的2 倍。分布式算法平均只需要2 倍于最優(yōu)解的發(fā)送者，最差時也只需要4 倍的發(fā)送節(jié)點。

圖4 2 種算法所需發(fā)送節(jié)點數(shù)與最優(yōu)解的比較

在集中式算法和分布式算法中，發(fā)送節(jié)點每10 ms發(fā)送一個測量包，每輪一共發(fā)送100 個，每輪耗時1 s。實驗中，集中式算法平均需要14 輪，最多16 輪來完成網(wǎng)絡模型的建立，即集中式算法需要平均耗時14 s，最差時耗時16 s 來建立模型。分布式算法指定使用30 輪來進行測量，因此耗時30 s 構(gòu)建網(wǎng)絡模型。從對文獻［10］方法的實驗結(jié)果看，為達到中值平均誤差7%，其需要耗時2.5 min。因此，可以看出，本文提出的2 種算法在時間開銷上性能較好。

7 結(jié)束語

隨著無線傳感器網(wǎng)絡越來越多的被部署到醫(yī)療、災害管理等各項數(shù)據(jù)密集型業(yè)務之中，網(wǎng)絡中節(jié)點信息傳輸?shù)母蓴_也越來越受到重視，如何高效地為節(jié)點建立干擾模型成為研究熱點。本文提出了2 種高效建立PRR-SINR 干擾模型的方法，一種是集中式的，另一種是分布式的，分別用于不同的場景。從實驗的結(jié)果可以看出，2 種算法都具有較高的精度，而且建立模型所需時間較短，額外的開銷較少。下一步工作將對分布式算法進行優(yōu)化，在提高其精度的同時，進一步減少所需發(fā)送節(jié)點的數(shù)目。

［1］Sharma G，Mazumdar R，Shroff N.On the Complexity of Scheduling in Wireless Networks［C］//Proceedings of MobiCom'06.Los Angeles，USA:ACM Press，2006:227-238.

［2］Alicherry M，Bhatia R，Li L E.Joint Channel Assignment and Routing for Throughput Optimization in Multi-radio Wireless Mesh Networks［C］//Proceedings of MobiCom'05.Cologne，Germany:ACM Press，2005:58-72.

［3］Gupta P，Kumar P R.The Capacity of Wireless Networks［J］.IEEE Transactions on Information Theory，2000，46(2):388-404.

［4］Zhao J，Govindan R.Understanding Packet Delivery Performance in Dense Wireless Sensor Networks［C］//Proceedings of SenSys'03.Los Angeles，USA:ACM Press，2003:1-13.

［5］Son D，Krishnamachari B，Heidemann J.Experimental Study of Concurrent Transmission in Wireless Sensor Networks［C］//Proceedings of SenSys'06.Boulder，USA:ACM Press，2006:237-250.

［6］Maheshwari R，Jain S，Das S R.A Measurement Study of Interference Modeling and Scheduling in Low-power Wireless Networks［C］//Proceedings of SenSys'08.Raleigh，USA:ACM Press，2008:141-154.

［7］Sha Mo，Xing Guoliang，Zhou Gang，et al.C-mac:Model-driven Concurrent Medium Access Control for Wireless Sensor Networks ［C］//Proceedings of INFOCOM'09.Rio de Janeiro，Brazil:IEEE Press，2009:1845-1853.

［8］Brar G.Blough D M，Santi P.Computationally Efficient Scheduling with the Physical Interference Model for Throughput Improvement in Wireless Mesh Networks［C］//Proceedings of MobiCom'06.Los Angeles，USA:ACM Press，2006:2-13.

［9］Rangwala S，Gummadi R，Govindan R，et al.Interference Aware Fair Rate Control in Wireless Sensor Networks［C］//Proceedings of SIGCOMM'06.Pisa，Italy:ACM Press，2006:62-74.

［10］Liu Shucheng，Xing Guoliang，Zhang Hongwei，et al.Passive Interference Measurement in Wireless Sensor Networks［C］//Proceedings of ICNP'10.Kyoto，Japan:IEEE Press，2010:52-61.

［11］Huang J，Liu S，Xing G，et al.Accuracy-aware Interference Modeling and Measurement in Wireless Sensor Networks［C］//Proceedings of ICDCS'11.Minneapolis，USA:IEEE Press，2011:172-181.

［12］Alsuwaiyel M H.算法設計技巧與分析［M］.吳偉昶，方世昌，譯.北京:電子工業(yè)出版社，2010.