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

圖3 構建支配集的分布式算法簡(jiǎn)單示例

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

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

3 仿真評估

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

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

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

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

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

圖6 本文提出的方法和基于樹(shù)形結構收集的負載分布

4 小結

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