無線傳感網絡中的充電節點選取策略研究

曹先波

（四川大學計算機學院，成都 610065）

0 引言

近年來，無線傳感器網絡（Wireless Sensor Net?works，WSNs）受到了世界各國的廣泛關注，特別是隨著微電子機械系統（MEMS）技術的進步，促進了智能傳感器的發展。這些傳感器節點可以感知、測量和收集來自環境的信息，然后，基于某種局部決策過程，將感測到的數據發送給用戶。由于應用場景不同，傳感器也因此種類繁多，針對不同的感知信息，可以使用不同類別的傳感器。感知的信息主要包括：濕度、溫度、壓力、強度等等信息。多數傳感器主要是由傳感器模塊、處理器模塊、能量供應模塊和無線通信模塊組成。傳感器模塊感知周圍環境信息，處理器模塊協調各個模塊之間的工作關系，控制各模塊工作模式。能量供應模塊為傳感器提供能量，保證傳感器的正常運行。無線通信模塊負責與其他傳感器之間的通信工作，接收從其他傳感器傳輸過來的數據，處理后發送給其他的傳感器或基站。

無線傳感器網絡通常由多個傳感器節點組成，共同監視一個區域，以獲取有關環境的數據。無線傳感器網絡一般可分為兩種類型：結構化和非結構化。在非結構化無線傳感器網絡中，傳感器節點隨機部署在需要監視的區域。部署以后，網絡將以無人看管的方式執行監視和報告的任務。這種非結構化類型的無線傳感器網絡由于節點太多，網絡維護（如連接管理和故障檢測）會非常困難。在結構化無線傳感器中，所有或部分傳感器節點都是以預先計劃的方式部署的。這使得結構化類型的無線傳感器網絡可以部署更少的節點，降低網絡維護和管理成本。

在應用方面，無線傳感器網絡應用于軍事目標跟蹤和監視，自然災害救濟，生物醫學健康監測、危險環境探索以及地震感應等多個領域。在軍事目標跟蹤和監視中，無線傳感器網絡可以協助進行入侵檢測和識別。具體示例包括與空間相關且協調的部隊和坦克運動。對于自然災害，傳感器節點可以感知并檢測環境，以在災害發生之前進行預測。在生物醫學應用中，傳感器的外科植入物可以幫助監測患者的健康狀況。對于地震感應，沿著火山區域臨時部署傳感器可以收集地震和爆發的數據。

然而，目前無線傳感器網絡通過電池進行供電，電池能量有限這一特點使得網絡的運行壽命受到限制。部分研究者[1-2]提出從環境中采集能量供傳感器使用，例如：太陽能、風能等，以延長傳感器的壽命。然而這種方式具有很大的不確定性，受到周圍環境的嚴重影響。例如，使用太陽能為傳感器供電將不得不受到天氣的影響，太陽能的能量收集效率在雨天會比晴天達到數十倍差距。另外，隨著無線能量傳輸技術的發展[3]，利用攜帶無線充電設備的移動充電小車為傳感器節點補充能量，延長無線傳感器網絡的壽命的充電研究，吸引了很多學者。這種方式更加可控、高效且對環境的依賴性更低。本文針對小規模的無線傳感器網絡，提出兩種移動充電小車的充電節點選取算法。

1 網絡模型

在一個給定的二維平面上，隨機部署N個傳感器節點，這些傳感器節點表示為s={s1,s2,…,sn} ，基站表示為s0。每個傳感器節點si∈S都是由能量為bi的電池供電，i=1,2,…,N。傳感器節點通過感應、接收和發送數據消耗能量，假定傳感器si的能量消耗速率和剩余能量分別表示為eci和rei。傳感器節點si和sj之間的距離為di,j，移動充電小車每移動一單元距離消耗c的能量。如圖1所示，在一個充電周期中，移動充電小車從基站s0出發，沿著充電路徑為傳感器節點補充能量，最后回到基站s0為下一個周期做準備。過程中，移動充電小車的移動速度為v。本文研究了在小規模的無線傳感網絡中，傳感器節點的選擇問題，找到移動充電小車的充電路徑C。

為了便于表述問題，本文將充電的網絡模型構建成一個網絡圖G=(S,E,D)，其中，S是網絡中的傳感器集合，E是網絡中傳感器之間的邊的集合，D是代表E的權重，即傳感器之間的歐幾里得距離。

圖1

2 充電模型

在無線可充電傳感器網絡中，傳感器裝配能量有限且可以進行無線能量傳輸的電池，完成數據感應、數據收集和數據發送工作。為了能夠保持網絡正常且長時間的運行，需要及時為傳感器補充能量，一種常用的做法是在網絡中加入攜帶無線充電設備的移動充電小車為傳感器進行無線能量傳輸。本文中，移動充電小車從基站出發，以恒定的速率移動到選取的傳感器附近，通過無線能量傳輸為傳感器補充能量。

移動充電小車離開基站，經過（s1,s2,…,sn），最后回到基站，于是移動充電小車的總行駛距離可以表示為：

3 能耗模型

傳感器在網絡中的能量消耗主要集中在數據感應、數據接收和數據發送方面，因此傳感器si的能量消耗可以表示為：

其中，us是傳感器感應一單位數據需要消耗的能量，ri是傳感器si感應數據的速率。傳感器si的數據發送消耗的能量表示為：

其中，N(si)表示在網絡G中，傳感器si的鄰居傳感器集合，是傳感器si發送一單位數據給傳感器sj所消耗的能量，fij是傳感器si到傳感器sj傳輸的數據量。對于傳感器的數據接收的能量消耗可以表示為：

其中，ur是傳感器接收一單位數據所需要消耗的能量，fji是傳感器si接收來自傳感器sj的數據量。

4 問題描述

本文研究了一個具有N個傳感器的無線傳感器網絡中的傳感器選取問題，最終得到移動充電小車的閉合充電回路C。為了提高移動充電小車所攜帶的電池能量，減少網絡中的傳感器節點因為能量耗盡而死亡，影響網絡的性能。針對這兩個方面的內容，本文提出了兩個算法來進行討論。

5 算法描述

在算法一（Sensor Selection Algorithm based on Ant Colony Optimization，SSAACO）中，為了盡可能提高移動充電消息的能量利用效率，需要減少移動充電小車的行駛距離，即式（1）所示。于是本文將充電小車的傳感器選取問題轉化為經典的TSP旅行商問題，構造最短的哈密爾頓環作為移動充電小車的行駛路徑，以使路徑最短，提高小車的能量利用效率。然而尋找到最短的哈密爾頓回路是NP難問題，所有可能的路徑數量是n!，計算的時間復雜度非常高，無法在多項式時間內得到最優解。隨著傳感器的數量增多，基本上已經無法完成最優解的計算。為了在可接受的時間內找到結果，本文利用蟻群算法的優點，通過迭代的方式得到移動充電小車的最佳行駛路徑。

在算法二中（Least Energy Sensor Selection Greedy Algorithm，LESSGA），文章考慮到有些傳感器的能量比較少，需要及時補充能量。為了滿足傳感器的急迫性需求，本文利用貪心策略，當移動充電小車選取下一個傳感器的時候，計算當前環境中所有傳感器的能量狀態信息，將能量最少的傳感器作為下一個待充電傳感器。傳感器si的剩余能量可以表示為：

其中，rei是傳感器si的剩余能量，tci是傳感器si上次補充能量的時間，ti是移動充電小車到達傳感器si的時間。ti可以表示為：

其中，μ是移動充電小車的能量傳輸效率，v是移動充電小車的移動速度。通過貪心策略，每次選取的傳感器加入C中，最后得到移動充電小車的充電回路路徑。

6 實驗結果與分析

本文在這一小節利用仿真實驗進行算法驗證。10-30個傳感器節點隨機部署在50m×50m的二維空間，移動充電小車的移動速率是5m/s，能量傳輸效率是5W。每個傳感器由3.7V/450mAh的堿性可充電電池供電，因此，傳感器的最大電池容量為3,7V×0.45A×3600sec=6kJ，傳感器的能量消耗隨機分布在0.1J/s-1J/s之間。

圖2

圖3

仿真實驗結果如圖2和圖3所示，對比了文章提出的SSAACO算法、LESSGA算法以及沒有使用調度算法的None。如圖2所示，隨著傳感器節點數量的增加，移動充電小車的路徑相應增加。SSAACO算法能夠為充電小車得到最短的行駛路徑，且明顯小于LESS?GA算法和None。在移動充電小車傳輸給傳感器的能量方面，LESSGA算法每次尋找能量最少的傳感器，使得整個充電周期時長最長，傳輸給傳感器的能量也最多。

7 結語

本文介紹了在可充電無線傳感器網絡中，如何調度移動充電小車為傳感器補充能量，傳感器的選取問題。本文在針對希望減少移動充電小車的行駛路徑方面和滿足傳感器的急迫性需求方面提出了兩種算法，并最后通過模擬實驗證明了算法的有效性。