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

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

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

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

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

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

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

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

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