一種基于移動(dòng)基站的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集方法

圖3 構(gòu)建支配集的分布式算法簡單示例

2．3路徑優(yōu)化

確定支配集后，基站還需要獲取各個(gè)節(jié)點(diǎn)的位置信息，選擇經(jīng)過這些節(jié)點(diǎn)的一條較短的路徑。在支配集構(gòu)建時(shí)，可以將基站置于網(wǎng)絡(luò)中任一節(jié)點(diǎn)處，并從該節(jié)點(diǎn)開始分布式算法，發(fā)送角色消息的同時(shí)在消息內(nèi)包括從開始節(jié)點(diǎn)計(jì)算的跳數(shù)，從而可以不付出額外的通信代價(jià)建立起任意節(jié)點(diǎn)到開始節(jié)點(diǎn)的最短路徑路由。各個(gè)DOMINATOR節(jié)點(diǎn)可以在確定自己的角色后通過多跳路由將位置信息傳遞回基站。此時(shí)，就可以將路徑優(yōu)化問題轉(zhuǎn)換成旅行商問題，尋找一條最短的圈且經(jīng)過每個(gè)點(diǎn)僅一次。然而，旅行商問題也被證明為NPhard問題。本文中使用kahng等提出的一種近似算法。該算法使用兩次連續(xù)的匹配來選擇完全圖中的一部分邊來將所有必須訪問的位置連接起來。第一次匹配選擇具有最小權(quán)重(本文中使用歐氏距離作為權(quán)重)的邊，是每個(gè)位置僅與一條邊相關(guān)聯(lián)。在將這些邊從圖中清除后再進(jìn)行第二次匹配。兩次匹配所選擇的邊構(gòu)成多個(gè)圈。然后。再將這些圈連接成一個(gè)大圈，即為算法的結(jié)果。在下一節(jié)中，我們將給出基于上述算法的仿真結(jié)果。

3 仿真評(píng)估

本節(jié)中，我們提供了支配集構(gòu)建和路徑優(yōu)化的仿真結(jié)果，并將本文的方法和基于樹形結(jié)構(gòu)的收集方法的負(fù)載分布也通過仿真進(jìn)行了比較。在仿真設(shè)置中，選擇了500×500單位長度的正方形區(qū)域作為傳感器網(wǎng)絡(luò)的部署區(qū)域。假定傳感器的傳輸范圍是圓形區(qū)域，通信半徑為r=50。

使用支配集的勢(shì)和所需使用的消息總數(shù)作為指標(biāo)，首先將2．2節(jié)中的算法與Wan等提出的算法進(jìn)行了比較。在基本場(chǎng)景中，我們使用1000個(gè)隨機(jī)分布的節(jié)點(diǎn)。通過改變節(jié)點(diǎn)數(shù)量使其從500變化到2000，模擬節(jié)點(diǎn)密度的變化。在每個(gè)場(chǎng)景下，我們進(jìn)行10次仿真并取平均值作為實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)結(jié)果如圖4所示。在圖4(a)中，我們提出的算法所生成支配集的勢(shì)比較穩(wěn)定，而Wan等所提出算法的結(jié)果則隨著節(jié)點(diǎn)數(shù)目的增加而略有增加。我們的結(jié)果具有更小的勢(shì)，僅為Wan等結(jié)果的50％～60％。在圖4(b)中，兩種算法的通信消耗都隨著節(jié)點(diǎn)數(shù)的增加而線性增長。我們的算法僅需要約占Wan等提出算法的50％的代價(jià)。我們的算法在支配集的勢(shì)和通信消耗兩個(gè)方面都優(yōu)于Wan等提出的算法。隨后，分別基于上文中兩種算法的結(jié)果，使用kahng等提出的算法生成移動(dòng)路徑。同樣改變節(jié)點(diǎn)數(shù)量從500到2000。在每個(gè)場(chǎng)景下，進(jìn)行1O次仿真，并使用平均值進(jìn)行比較。仿真結(jié)果如圖5所示。兩條曲線都隨著節(jié)點(diǎn)數(shù)的變化而波動(dòng)，其原因是拓?fù)浣Y(jié)構(gòu)是隨機(jī)生成的，各個(gè)拓?fù)淇赡苡胁煌男再|(zhì)。但使用我們算法的結(jié)果要優(yōu)于使用Wan等所提出算法的結(jié)果，即減少支配集的勢(shì)確實(shí)有助于縮短移動(dòng)路徑的長度。

圖4支配集的勢(shì)和通信代價(jià)比較

圖5 移動(dòng)路徑的長度

我們分別對(duì)本文的方法與使用樹形結(jié)構(gòu)且靜態(tài)基站位于網(wǎng)絡(luò)中心的方法進(jìn)行了仿真。仿真使用了具有2500個(gè)節(jié)點(diǎn)的網(wǎng)格拓?fù)?。兩種方案都需要構(gòu)建最短路徑樹作為路由。此處我們忽略了構(gòu)建最短路徑樹的通信消耗，而只考慮數(shù)據(jù)收集過程中的消耗。圖6顯示了我們提出的方案和基于樹形結(jié)構(gòu)收集方案在一次性收集所有節(jié)點(diǎn)上數(shù)據(jù)時(shí)的負(fù)載分布。其中X、y分別表示二維平面的坐標(biāo)軸，使用基于樹形結(jié)構(gòu)的收集方法時(shí)，基站位于網(wǎng)絡(luò)的中心位置。很容易看出我們的方案僅有極低的通信消耗且具有更均衡的負(fù)載分布。在圖6(a)中，所有節(jié)點(diǎn)所需發(fā)送的消息數(shù)都不超過5，而在圖6(b)中相當(dāng)一部分節(jié)點(diǎn)需要發(fā)送超過100個(gè)消息。在圖6(b)靠近中心位置處，有的節(jié)點(diǎn)需要發(fā)送的消息個(gè)數(shù)遠(yuǎn)遠(yuǎn)超出其他節(jié)點(diǎn)。正是這些節(jié)點(diǎn)的壽命限制了網(wǎng)絡(luò)壽命。仿真結(jié)果顯示我們的方案具有很好的可行性。與基于樹形結(jié)構(gòu)的收集方法相比，它具有低通信消耗和更平衡的負(fù)載分布。我們的方案不需要轉(zhuǎn)發(fā)別的節(jié)點(diǎn)生成的數(shù)據(jù)，因此明顯比其他聯(lián)合使用移動(dòng)基站和多跳路由方法更高效。

圖6 本文提出的方法和基于樹形結(jié)構(gòu)收集的負(fù)載分布

4 小結(jié)

我們提出了一種基于移動(dòng)基站而不使用多跳路由的數(shù)據(jù)收集方法。該方法結(jié)合了支配集相逢算法和旅行商問題的近似算法。仿真結(jié)果顯示，所提出的支配集構(gòu)造算法具有更低的通信消耗和更低勢(shì)的支配集結(jié)果，并能生成更短的移動(dòng)路徑。所提出的數(shù)據(jù)收集方法還具有負(fù)載均衡分布的特性。此外，該方法不使用UDG等理想狀態(tài)模型。從而具有很好的實(shí)用性。