無線可充電傳感器網(wǎng)絡中充電規(guī)劃及其可調(diào)度性研究.pdf

1、無線傳感器網(wǎng)絡是21世紀信息獲取最重要、最基本的技術之一，具有重大的實際應用背景和戰(zhàn)略研究價值。然而由于傳感器節(jié)點體積較小，攜帶的能量有限，并且傳感器網(wǎng)絡中普遍存在能耗不均衡現(xiàn)象，因此能量問題成為當前傳感器網(wǎng)絡實際部署和應用所要克服的最重要的難題之一。無線可充電傳感器網(wǎng)絡解決方案能夠緩解乃至消除無線傳感器網(wǎng)絡的能量瓶頸。已有研究工作利用單個或多個高能量儲備的移動充電節(jié)點（MC，Mobile Charger）為各傳感器節(jié)點實施近距離無線充

2、電來保證傳感器節(jié)點的存活，而MC可以在一個服務站節(jié)點（S，service Station）更新自身能量。這種方案具有高可控性、高可預測性及高效率，并且從理論上能夠徹底解決無線傳感器網(wǎng)絡的能量問題，因此受到廣泛關注和深入研究。其中，充電規(guī)劃是最核心和最基本的研究問題之一，優(yōu)化的充電規(guī)劃能夠利用最少的資源獲得最高的網(wǎng)絡效用。充電規(guī)劃的相關算法和思路還可以用于設計服務分發(fā)、物流運輸?shù)仁芟拶Y源的調(diào)度問題，具有廣泛的應用基礎。
　　本論文從

3、無線可充電傳感器網(wǎng)絡中充電規(guī)劃可調(diào)度性判定問題入手，研究基于單MC和多MC的充電規(guī)劃設計，在保證可靠充電服務的條件下，最小化充電系統(tǒng)的總代價。本論文的主要工作和貢獻包括:
　　(1)提出充電規(guī)劃可調(diào)度性的概念，并提出判定充電規(guī)劃可調(diào)度的充分條件和必要條件。充電規(guī)劃的可調(diào)度性是指給定充電系統(tǒng)的硬件配置，是否能夠讓MC根據(jù)某個充電方案進行充電，使得傳感器網(wǎng)絡達到目標生命期。在設計MC的充電方案之前，根據(jù)本論文提出的充分條件和必要條件，

4、收集傳感器網(wǎng)絡相關參數(shù)后可以直接對充電規(guī)劃的可調(diào)度性進行高效的判定。對于任意充電規(guī)劃，如果它滿足充分條件，則可調(diào)度，同時可構(gòu)造出一個可行的充電方案;如果它不滿足必要條件，則不可調(diào)度，任何充電方案都不能使傳感器網(wǎng)絡達到目標生命期。
　　(2)針對采用單個MC的一般性傳感器網(wǎng)絡，提出可行充電方案的一般性描述方程以及周期性貪心充電方案（PGC，Periodic Greedy Charging scheme）。任何充電方案可行當且僅當它滿

5、足該描述方程;針對不同應用目標，可以將描述方程轉(zhuǎn)化成充電方案的優(yōu)化方程形式進行求解。PGC方案對描述方程進行約束，大大簡化它的形式，從而能夠以線性時間復雜度構(gòu)造出可行的充電方案。
　　(3)針對采用單個MC的能耗不均衡的傳感器網(wǎng)絡，提出按需貪心充電方案(CoD，Charge on Demand scheme)和一種S部署方案。CoD方案充分考慮傳感器網(wǎng)絡能耗不均衡的特點，每一輪只為剩余工作時間小于臨界閾值的傳感器節(jié)點進行充電，在理

6、論上保證所有傳感器節(jié)點不死亡的條件下，能夠顯著降低MC的總移動距離，從而提高其充電效率。實驗數(shù)據(jù)表明，與采用周期性充電方案的相關工作比較，CoD方案能夠降低MC約50％的總移動距離。在采用按需充電方案時，由于每個傳感器節(jié)點的充電頻率相差很大，因此提出一種將S部署在傳感器網(wǎng)絡能耗熱點區(qū)域的方案。實驗數(shù)據(jù)表明，綜合使用CoD方案和S部署方案能夠進一步降低MC約20％的總移動距離。當傳感器網(wǎng)絡能耗較為均衡時，CoD方案退化成PGC方案。

7、>　　(4)針對采用多個MC的大規(guī)模傳感器網(wǎng)絡，提出基于回路的貪心充電方案(TGC，Tour-based Greedy Charging scheme)。本論文指出充電規(guī)劃中所需最少數(shù)量的MC問題與距離受限的多回路運輸問題之間存在本質(zhì)差別，并將前者分解為兩個緊耦合的NP完全子問題。首先基于回路可調(diào)度的充分條件將傳感器網(wǎng)絡劃分成若干可調(diào)度的回路，然后根據(jù)啟發(fā)式規(guī)則將這些回路分配給最少數(shù)量的MC，同時以極低的復雜度構(gòu)造每個MC為各個回路的充

8、電方案。實驗數(shù)據(jù)表明，TGC方案使用的MC數(shù)量僅為相關工作的20％～40％，而并且不超過理論下界的1.1倍。當整個傳感器網(wǎng)絡能夠被單個MC在一輪中充電時，TGC方案退化成PGC方案。
　　(5)提出無線可充電傳感器網(wǎng)絡中充電規(guī)劃的一般性設計思路，并舉例進行驗證?；跓o線可充電傳感器網(wǎng)絡相關工作，歸納出設計充電規(guī)劃軟硬件兩個層面的六個重要維度。分析對比每個維度中不同類型方案的優(yōu)缺點，并指出每種方案的適用場景，為設計不同需求和不同應用