向亦宏，朱燕民

(上海交通大學(xué)計(jì)算機(jī)科學(xué)與工程系，上海 200240)

1 概述

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

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

2 相關(guān)研究

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

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

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

圖1 不同時(shí)刻、不同位置節(jié)點(diǎn)測(cè)得的PRR-SINR 模型

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

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

3.1 系統(tǒng)模型

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

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

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

3.2 問(wèn)題描述

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

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

圖2 PRR-SINR 點(diǎn)的測(cè)量

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

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

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

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

因?yàn)橐粋€(gè)發(fā)送子集中的每個(gè)節(jié)點(diǎn)都需要發(fā)送M 個(gè)測(cè)量包，所以為了達(dá)到使用最少測(cè)量包的目標(biāo)，筆者希望選擇K 個(gè)發(fā)送子集，這些子集含有的節(jié)點(diǎn)的數(shù)目的和是最少的。本文問(wèn)題描述如下:

3.3 復(fù)雜度分析

引理1 選擇集問(wèn)題是NP 的。

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

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

引理2 集合覆蓋問(wèn)題可以歸約到選擇集問(wèn)題。

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

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

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

定理 選擇集問(wèn)題是一個(gè)NP 完全問(wèn)題。

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

4 集中式算法

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

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

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

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

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

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

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

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

(7)結(jié)束。

5 分布式算法

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

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

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

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

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

(2)節(jié)點(diǎn)i 充當(dāng)接收者，處于監(jiān)聽模式。當(dāng)成功收到節(jié)點(diǎn)K 發(fā)送的測(cè)試包時(shí)，計(jì)算此時(shí)的SINR，如果該SINR 沒(méi)有對(duì)應(yīng)的PRR，則接下來(lái)節(jié)點(diǎn)i 只統(tǒng)計(jì)收到K 發(fā)送的包的個(gè)數(shù)，計(jì)算PRR。

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

(4)如果已進(jìn)行的輪次數(shù)目沒(méi)有達(dá)到N，則繼續(xù)步驟(1)。

(5)結(jié)束。

6 性能評(píng)估

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

6.1 精度評(píng)估

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

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

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

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

(3)通過(guò)ACTIVE 方法為每個(gè)節(jié)點(diǎn)生成PRRSINR 模型。

(4)將集中式算法和分布式算法為每個(gè)節(jié)點(diǎn)所計(jì)算的模型與ACTIVE 生成的相比較，計(jì)算出節(jié)點(diǎn)過(guò)渡區(qū)域中每個(gè)SINR 對(duì)應(yīng)的PRR 與ACTIVE 相比的絕對(duì)誤差值。

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

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

6.2 開銷評(píng)估

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

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

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

7 結(jié)束語(yǔ)

隨著無(wú)線傳感器網(wǎng)絡(luò)越來(lái)越多的被部署到醫(yī)療、災(zāi)害管理等各項(xiàng)數(shù)據(jù)密集型業(yè)務(wù)之中，網(wǎng)絡(luò)中節(jié)點(diǎn)信息傳輸?shù)母蓴_也越來(lái)越受到重視，如何高效地為節(jié)點(diǎn)建立干擾模型成為研究熱點(diǎn)。本文提出了2 種高效建立PRR-SINR 干擾模型的方法，一種是集中式的，另一種是分布式的，分別用于不同的場(chǎng)景。從實(shí)驗(yàn)的結(jié)果可以看出，2 種算法都具有較高的精度，而且建立模型所需時(shí)間較短，額外的開銷較少。下一步工作將對(duì)分布式算法進(jìn)行優(yōu)化，在提高其精度的同時(shí)，進(jìn)一步減少所需發(fā)送節(jié)點(diǎn)的數(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.算法設(shè)計(jì)技巧與分析［M］.吳偉昶，方世昌，譯.北京:電子工業(yè)出版社，2010.