基于成本優(yōu)化的多跳無(wú)線充電問(wèn)題研究

祝貞陽(yáng)

（杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院，杭州310018)

無(wú)線傳感網(wǎng)；無(wú)線充電；數(shù)據(jù)采集；錨點(diǎn)

0 引言

無(wú)線傳感器網(wǎng)絡(luò)目前應(yīng)用十分廣泛，例如軍事、醫(yī)療、自然環(huán)境監(jiān)測(cè)和野生動(dòng)物生活習(xí)性觀察，等等。一般情況下，傳感器節(jié)點(diǎn)由電池供電，而電池的容量有限，隨著時(shí)間的推移，傳感器節(jié)點(diǎn)將耗盡自身的能量，這樣就導(dǎo)致了無(wú)線傳感器網(wǎng)絡(luò)的生命周期受限。為了保證傳感器網(wǎng)絡(luò)能夠持續(xù)運(yùn)行，我們引進(jìn)了無(wú)線充電技術(shù)的新概念，目前主流的無(wú)線充電技術(shù)主要分為三類：電感耦合、磁共振耦合和電磁波輻射技術(shù)。

第一類是電感耦合技術(shù)[1-2]，電感耦合技術(shù)優(yōu)點(diǎn)在于安全并易于實(shí)現(xiàn)，它通過(guò)兩個(gè)線圈間的感應(yīng)就能實(shí)現(xiàn)能量的傳遞。但電感耦合技術(shù)只能用在非常短的距離間充電，而且充電器和設(shè)備間必須緊密耦合，精確對(duì)準(zhǔn)。

第二類是磁共振耦合技術(shù)[3-10]，磁共振耦合相比電感耦合技術(shù)的初級(jí)線圈和次級(jí)線圈各多了一個(gè)電容，這樣就形成了LC諧振電路，當(dāng)初級(jí)線圈和次級(jí)線圈諧振頻率相等形成共振時(shí)才會(huì)有能量的傳輸，它的缺點(diǎn)是不適合移動(dòng)應(yīng)用、充電距離有限并難以實(shí)現(xiàn)。

第三類是電磁波輻射技術(shù)[11-17]，電磁波輻射技術(shù)適合移動(dòng)應(yīng)用，是一種低功率遠(yuǎn)距離的能量傳輸模式。但當(dāng)無(wú)線電頻率（RF）太高時(shí)會(huì)導(dǎo)致不安全和充電效率低。

以上三種無(wú)線充電技術(shù)都能對(duì)傳感器節(jié)點(diǎn)進(jìn)行無(wú)線充電，從而保證傳感器的持續(xù)運(yùn)行。本文通過(guò)結(jié)合磁共振耦合技術(shù)和移動(dòng)數(shù)據(jù)采集模型來(lái)最小化系統(tǒng)總開銷，SenCar在給傳感器節(jié)點(diǎn)充電的同時(shí)還對(duì)傳感器產(chǎn)生的數(shù)據(jù)進(jìn)行采集，以保證在傳感器網(wǎng)絡(luò)持續(xù)運(yùn)行的前提下最小化系統(tǒng)的總開銷。本文的創(chuàng)新之處體現(xiàn)在如何挑選出最佳的“錨點(diǎn)”，因?yàn)椤板^點(diǎn)”的選擇關(guān)系到充電損耗和SenCar的移動(dòng)損耗。首先根據(jù)能量消耗和能量補(bǔ)充之間的關(guān)系確定好完成所有充電任務(wù)所需最少的SenCar數(shù)量。接下來(lái)再對(duì)所有選出的“錨點(diǎn)”求一條完整的TSP路徑，并規(guī)劃方案用一定數(shù)量的SenCar將路徑進(jìn)行劃分，從而使得完成所有充電任務(wù)的系統(tǒng)總開銷最低。

本文提出一種新的最優(yōu)成本優(yōu)化方案，通過(guò)設(shè)計(jì)并實(shí)現(xiàn)“錨點(diǎn)選擇算法”，該算法首先將傳感器節(jié)點(diǎn)進(jìn)行聚類，分別計(jì)算每個(gè)分類中各傳感器節(jié)點(diǎn)的平均消耗，并將平均消耗最低的節(jié)點(diǎn)作為“錨點(diǎn)”，確保選出的“錨點(diǎn)”能夠覆蓋到整個(gè)無(wú)線傳感器網(wǎng)絡(luò)。最后規(guī)劃方案用適當(dāng)數(shù)量的SenCar使得完成所有充電任務(wù)所需的總開銷最低。

本文的主要貢獻(xiàn)如下：

（1）根據(jù)能量消耗和能量補(bǔ)充之間的關(guān)系確定好完成傳感器網(wǎng)絡(luò)中所有充電任務(wù)所需的最少SenCar數(shù)量。

（2）設(shè)計(jì)并實(shí)現(xiàn)了一種新的“錨點(diǎn)選擇算法”，該算法首先將傳感器節(jié)點(diǎn)進(jìn)行聚類，針對(duì)每個(gè)充電集合，分別計(jì)算各節(jié)點(diǎn)的平均損耗，選擇平均消耗最低的節(jié)點(diǎn)作為“錨點(diǎn)”。同時(shí)為了減少能量的損耗，只考慮聚集一跳以內(nèi)的傳感器節(jié)點(diǎn)。

（3）確定好“錨點(diǎn)”的位置后，再對(duì)所有選出的“錨點(diǎn)”求一條完整的TSP路徑，在完成傳感器網(wǎng)絡(luò)中所有充電任務(wù)所需總時(shí)間一定的條件下，規(guī)劃方案通過(guò)使用適當(dāng)數(shù)量的SenCar將路徑進(jìn)行劃分從而使得完成所有充電任務(wù)所需的總開銷最小。

（4）通過(guò)多次模擬實(shí)驗(yàn)驗(yàn)證和分析了我們提出算法的性能，實(shí)驗(yàn)結(jié)果表明，該算法能以一定SenCar數(shù)量的開銷下最小化系統(tǒng)總開銷。

1 相關(guān)工作

本節(jié)主要回顧了單節(jié)點(diǎn)無(wú)線充電和多跳無(wú)線充電技術(shù)的相關(guān)工作。

過(guò)去的研究工作大多集中在單節(jié)點(diǎn)無(wú)線充電，單節(jié)點(diǎn)無(wú)線充電只允許移動(dòng)充電器一次給單個(gè)傳感器節(jié)點(diǎn)充電，并且移動(dòng)充電器需要緊挨著傳感器進(jìn)行充電，這樣不僅導(dǎo)致了低充電效率以及高延遲，而且后面待充電的節(jié)點(diǎn)可能因?yàn)殚L(zhǎng)期等待得不到能量補(bǔ)充而耗盡能量甚至餓死。在文獻(xiàn)[18]中，作者解決了確定MC的最小數(shù)量以保持每個(gè)傳感器節(jié)點(diǎn)連續(xù)工作的問(wèn)題。首先，作者提出一種基于旅行商問(wèn)題的貪婪算法。接下來(lái)開發(fā)了一個(gè)啟發(fā)式算法以解決Tours的分配問(wèn)題，并將這些Tours分配給最小數(shù)量的MC。在文獻(xiàn)[19]中，作者提出了一個(gè)無(wú)線能量補(bǔ)充和無(wú)線傳感器網(wǎng)絡(luò)中基于“錨點(diǎn)”的移動(dòng)數(shù)據(jù)采集（WerMDG）框架，通過(guò)考慮能量消耗的各種來(lái)源和能量補(bǔ)充的時(shí)變特性。首先確定“錨點(diǎn)”選擇策略和訪問(wèn)“錨點(diǎn)”的序列。然后，將Wer?MDG問(wèn)題制定為受流量，能量平衡，鏈路和電池容量以及移動(dòng)收集器的有限逗留時(shí)間限制的網(wǎng)絡(luò)效用最大化問(wèn)題。在文獻(xiàn)[20]中，作者提出了一種稱為移動(dòng)設(shè)備移動(dòng)算法（MDTA）的新算法，通過(guò)使用有限數(shù)量的移動(dòng)設(shè)備為傳感器充電并收集數(shù)據(jù)。仿真實(shí)驗(yàn)結(jié)果表明，MDTA相比其他方法具有更好的性能。在文獻(xiàn)[21]中，作者探討了為無(wú)線傳感器網(wǎng)絡(luò)提供能量時(shí)的能量不足問(wèn)題，并提出了一種饑餓避免的移動(dòng)能量補(bǔ)給方案（SAMER），可通過(guò)計(jì)算并考慮每個(gè)充電要求的最大可容忍延遲來(lái)避免能量不足。仿真實(shí)驗(yàn)結(jié)果表明，SAMER方案能夠有效地解決無(wú)線傳感器網(wǎng)絡(luò)中能量不足的問(wèn)題，并實(shí)現(xiàn)高效的移動(dòng)能量補(bǔ)充。在文獻(xiàn)[22]中，作者提出了一種智能無(wú)線充電車（IWCV）策略，以動(dòng)態(tài)可擴(kuò)展的方式解決無(wú)線傳感器網(wǎng)絡(luò)的能量限制問(wèn)題。IWCV策略涵蓋一種智能路由策略，用于遍歷傳感器網(wǎng)絡(luò)拓?fù)洳殡姵爻潆娨匝娱L(zhǎng)使用壽命。

考慮到單節(jié)點(diǎn)無(wú)線充電在充電模式上的缺陷，后人在此基礎(chǔ)上提出了多跳無(wú)線充電技術(shù)的新概念，它允許移動(dòng)充電器同時(shí)給多個(gè)傳感器節(jié)點(diǎn)充電，并能夠?qū)崿F(xiàn)能量之間的互換。相比于單節(jié)點(diǎn)無(wú)線充電，多跳無(wú)線充電具有更高的充電效率以及擴(kuò)展性。但目前針對(duì)無(wú)線可充電傳感器網(wǎng)絡(luò)中的多跳無(wú)線充電技術(shù)研究相對(duì)還比較少，主要集中在文獻(xiàn)[23-26]作了相關(guān)研究。在文獻(xiàn)[23]中，作者提出了一個(gè)采用諧振中繼器進(jìn)行多跳無(wú)線充電的新框架。他們構(gòu)建了基于磁共振耦合技術(shù)下的能耗模型，并計(jì)算了多跳無(wú)線充電效率。然后，他們通過(guò)能量消耗和能量補(bǔ)充之間的關(guān)系近似估算出完成所有充電任務(wù)所需SenCar的數(shù)量。接下來(lái)將該問(wèn)題轉(zhuǎn)化為一個(gè)雙目標(biāo)優(yōu)化問(wèn)題，并提出一個(gè)兩步近似算法解決這個(gè)問(wèn)題以最小化系統(tǒng)總開銷。最后，他們還提出一個(gè)后期優(yōu)化算法以進(jìn)一步降低系統(tǒng)總開銷。在文獻(xiàn)[24]中，作者在考慮節(jié)點(diǎn)能量需求，傳輸過(guò)程中產(chǎn)生的能量損失以及充電器容量限制的條件下，提出了一個(gè)優(yōu)化模型來(lái)確定最小充電器的數(shù)量以完成所有充電任務(wù)。在文獻(xiàn)[25]中，作者提出了一種高效節(jié)能的移動(dòng)多跳充電策略。通過(guò)引入基于最優(yōu)中心點(diǎn)的輪詢點(diǎn)選擇算法，為移動(dòng)充電器構(gòu)建了每個(gè)分區(qū)的最佳捕獲點(diǎn)。并且在每個(gè)分區(qū)中，采用多跳無(wú)線充電的方式為這些節(jié)點(diǎn)補(bǔ)充能量。通過(guò)聯(lián)合優(yōu)化移動(dòng)路徑，中繼路由和充電時(shí)間，開發(fā)了一個(gè)充電效率函數(shù)來(lái)分析能效。在文獻(xiàn)[26]中，作者旨在克服無(wú)線傳感器網(wǎng)絡(luò)中的能量限制，介紹了三種多跳無(wú)線能量傳輸技術(shù)，并且推導(dǎo)出它們各自的能量傳輸效率。

2 模型和假設(shè)

我們提出的模型中基站位于無(wú)線傳感器網(wǎng)絡(luò)的中心，SenCar停靠在基站的附近。傳感器節(jié)點(diǎn)隨機(jī)部署在無(wú)線可充電傳感器網(wǎng)絡(luò)中，SenCar給“錨點(diǎn)”補(bǔ)充能量，SenCar自身攜帶充電器和數(shù)據(jù)采集裝置，SenCar在給“錨點(diǎn)”充電的同時(shí)還對(duì)數(shù)據(jù)進(jìn)行采集，并將采集到的數(shù)據(jù)交給基站，而“錨點(diǎn)”獲得能量補(bǔ)充后再對(duì)請(qǐng)求充電的傳感器節(jié)點(diǎn)進(jìn)行充電。SenCar從基站出發(fā)，按照“錨點(diǎn)”提前規(guī)劃好的路徑有序地對(duì)“錨點(diǎn)”進(jìn)行充電，直到“錨點(diǎn)”覆蓋完整個(gè)無(wú)線傳感器網(wǎng)絡(luò)。模型中我們假設(shè)充電過(guò)程中將所有傳感器節(jié)點(diǎn)的電池都充滿。無(wú)線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)模型圖如圖1所示。

圖1 網(wǎng)絡(luò)模型圖

數(shù)據(jù)采集模型：

數(shù)據(jù)采集過(guò)程中涉及到能量消耗，本文的研究工作中只考慮移動(dòng)數(shù)據(jù)采集，周圍的傳感器節(jié)點(diǎn)將產(chǎn)生的數(shù)據(jù)量傳送到“錨點(diǎn)”位置，SenCar在給“錨點(diǎn)”充電的同時(shí)還對(duì)各傳感器產(chǎn)生的數(shù)據(jù)進(jìn)行移動(dòng)采集。傳感器傳送/接收1比特?cái)?shù)據(jù)的能量消耗為：

其中，e0表示傳感器用于感知、編碼和調(diào)制的能耗，e1表示每比特?cái)?shù)據(jù)的損失系數(shù)，dr表示傳輸距離，α表示路徑損耗系數(shù)（通常取2到4），λ表示傳感器節(jié)點(diǎn)單位時(shí)間產(chǎn)生的數(shù)據(jù)量。移動(dòng)數(shù)據(jù)采集局部模型如圖2所示。

能量傳遞模型：

本文考慮磁共振耦合技術(shù)下的能量傳遞模型，能量傳遞的過(guò)程中涉及到能量損耗。計(jì)算多跳無(wú)線充電效率是本文的關(guān)鍵，文獻(xiàn)[1]中采用磁共振耦合模型下的無(wú)線充電技術(shù)計(jì)算多跳無(wú)線充電效率η見表1所示。

圖2 移動(dòng)數(shù)據(jù)采集模型

表1 多跳無(wú)線充電效率

由表1可見，隨著跳數(shù)的增加，無(wú)線充電效率逐漸降低，同時(shí)隨著傳感器節(jié)點(diǎn)之間距離的增加，無(wú)線充電效率也逐漸降低，但隨著距離的增加，無(wú)線充電效率衰減的比較厲害。因此，多跳無(wú)線充電效率與跳數(shù)和傳感器節(jié)點(diǎn)之間的距離相關(guān)，而且后續(xù)的模擬實(shí)驗(yàn)需要用到相關(guān)參數(shù)。

假定節(jié)點(diǎn)j請(qǐng)求dj的能量，那么節(jié)點(diǎn)i需要為節(jié)點(diǎn)j提供dj/ηij的能量，對(duì)于節(jié)點(diǎn)i和節(jié)點(diǎn)k的無(wú)線充電效率ηik=ηijηjk。能量傳遞的局部模型如圖3所示。

圖3 能量傳遞模型

3 問(wèn)題的形式化定義

問(wèn)題描述：

在一個(gè)隨機(jī)部署了N個(gè)傳感器節(jié)點(diǎn)的無(wú)線傳感器網(wǎng)絡(luò)中（N盡量超過(guò)一個(gè)SenCar的服務(wù)能力），每個(gè)傳感器節(jié)點(diǎn)單位時(shí)間內(nèi)的數(shù)據(jù)產(chǎn)生率是確定的。給定完成整個(gè)無(wú)線傳感器網(wǎng)絡(luò)中所有充電任務(wù)（將全部傳感器節(jié)點(diǎn)充滿電）的總時(shí)間T，T要求小于給定的閾值Y。結(jié)合考慮SenCar的使用成本，如何規(guī)劃方案在使用適當(dāng)數(shù)量SenCar的條件下使得完成這些充電任務(wù)所需的系統(tǒng)總開銷最小，且保證每個(gè)傳感器節(jié)點(diǎn)都不會(huì)餓死。

表2 符號(hào)描述

根據(jù)上述符號(hào)定義，我們可以將該問(wèn)題轉(zhuǎn)化成如下的優(yōu)化問(wèn)題。

對(duì)于給定完成整個(gè)無(wú)線傳感器網(wǎng)絡(luò)中所有充電任務(wù)所需的總時(shí)間T（不考慮移動(dòng)數(shù)據(jù)采集的時(shí)間），默認(rèn)將所有傳感器節(jié)點(diǎn)的電池充滿。

目標(biāo)函數(shù)：

其中：

式（1）代表多跳能量傳遞過(guò)程中的充電成本；式（2）代表SenCar的移動(dòng)成本；式（3）代表SenCar的使用成本。

約束條件：

上述約束條件中，（4）、（5）規(guī)定了 SenCar移動(dòng)路徑的連通；（6）規(guī)定了所有傳感器節(jié)點(diǎn)都被唯一的“錨點(diǎn)”充電；（7）確保節(jié)點(diǎn)的充電效率大于效率閾值；（8）確保節(jié)點(diǎn)歸屬于某一錨點(diǎn)；（9）表示SenCar用于充電的總能量；（10）表示SenCar k的移動(dòng)和充電所需的總時(shí)間；（11）表示完成整個(gè)無(wú)線傳感器網(wǎng)絡(luò)中所有充電任務(wù)所需的總時(shí)間；（12）表示完成整個(gè)無(wú)線傳感器網(wǎng)絡(luò)中所有充電任務(wù)所需的總時(shí)間小于閾值Y；（13）表示SenCar需要為傳感器提供的總能量加上SenCar的移動(dòng)損耗之和不能超過(guò)SenCar的充電容量；（14）表示xijk,yia,zik取值為0或1。

4 理論分析

本節(jié)主要理論分析了SenCar在移動(dòng)數(shù)據(jù)采集過(guò)程中的能量消耗以及在能量傳遞過(guò)程中的能量補(bǔ)充，并根據(jù)能量消耗和能量補(bǔ)充之間的關(guān)系確定完成無(wú)線傳感器網(wǎng)絡(luò)中所有充電任務(wù)所需的最少SenCar數(shù)量。

（1）能量消耗

根據(jù)目前數(shù)據(jù)采集的研究現(xiàn)狀，本文只考慮Sen?Car的移動(dòng)數(shù)據(jù)采集。首先，我們分析SenCar在移動(dòng)數(shù)據(jù)采集過(guò)程中產(chǎn)生的能量消耗，由于SenCar的移動(dòng)軌跡具有不確定性，因此很難分析出這個(gè)過(guò)程中的能耗，根據(jù)文獻(xiàn)，我們可以近似得到m個(gè)SenCar在移動(dòng)數(shù)據(jù)采集過(guò)程中的能量消耗，記為Es。

其中，l代表跳數(shù)，λ代表傳感器節(jié)點(diǎn)單位時(shí)間內(nèi)的數(shù)據(jù)產(chǎn)生率，N代表傳感器節(jié)點(diǎn)數(shù)量，ec代表傳送或接收一個(gè)數(shù)據(jù)包的能量消耗。

（2）能量補(bǔ)充

確定好m個(gè)SenCar在移動(dòng)數(shù)據(jù)采集過(guò)程中產(chǎn)生的能耗后，接下來(lái)需要估算出為無(wú)線傳感器網(wǎng)絡(luò)補(bǔ)充的能量，以達(dá)到能量消耗與能量補(bǔ)充之間的平衡。我們假設(shè)m個(gè)SenCar的總充電率為Re。

根據(jù)式（16）可以看出，多跳無(wú)線充電相比于單節(jié)點(diǎn)無(wú)線充電具有更好的擴(kuò)展性。其中，Cb代表傳感器節(jié)點(diǎn)的電池容量，β代表電池容量的閾值，rmax代表最大充電范圍，ρ代表傳感器節(jié)點(diǎn)的分布密度，SenCar的最長(zhǎng)移動(dòng)時(shí)間Tl=2Rc/v（Rc代表感應(yīng)場(chǎng)的半徑，v代表SenCar的移動(dòng)速度），Tr代表將傳感器電池從0到充滿所需的時(shí)間。

（3）確定最少SenCar數(shù)量

理論分析好SenCar在移動(dòng)數(shù)據(jù)采集過(guò)程中的能量消耗和能量補(bǔ)充后，再根據(jù)兩者之間的能量平衡關(guān)系，得出需要為無(wú)線傳感器網(wǎng)絡(luò)補(bǔ)充的能量至少要等于SenCar在移動(dòng)數(shù)據(jù)采集過(guò)程中消耗的能量。因此，我們讓E≤R，結(jié)合式（15）和式（16）可以得到：

根據(jù)式（17）可以看出，針對(duì)固定大小的感應(yīng)場(chǎng)半徑，SenCar的使用數(shù)量與傳感器節(jié)點(diǎn)的數(shù)量無(wú)關(guān)，因此這個(gè)特性允許在未發(fā)生額外的開銷下提高無(wú)線傳感器網(wǎng)絡(luò)的擴(kuò)展性。

5 方案規(guī)劃

本節(jié)我們?cè)O(shè)計(jì)了一套無(wú)線可充電傳感器網(wǎng)絡(luò)中多跳無(wú)線充電結(jié)合移動(dòng)數(shù)據(jù)采集模型的成本優(yōu)化方案。首先，我們提出“錨點(diǎn)”選擇算法并確定好“錨點(diǎn)”的位置，然后對(duì)所有選出的“錨點(diǎn)”求一條完整的TSP路徑，接下來(lái)再將TSP路徑進(jìn)行劃分，并將其分配給相應(yīng)數(shù)量的SenCar。

（1）“錨點(diǎn)”選擇算法

我們首先介紹提出的“錨點(diǎn)”選擇算法，該算法基于能量請(qǐng)求來(lái)獲取“錨點(diǎn)”集合，本章節(jié)中“錨點(diǎn)”的選擇至關(guān)重要，因?yàn)椤板^點(diǎn)”的選擇關(guān)系到充電損耗和SenCar的移動(dòng)損耗，這樣會(huì)間接影響到系統(tǒng)的總開銷。“錨點(diǎn)”選擇方案的示意圖如圖4所示。

圖4 “錨點(diǎn)”選擇算法

算法1“錨點(diǎn)”選擇算法

Input:Recharging node setN,charging setSi,ener?gy demanddi,charging efficiency of nodej.

Output:Set of anchorsAand resultant subsetsB.

1.whileB≠Ndo

4.A←A∪k,B←B∪Sk,Si←Si-B,?ik∈N.

5.end while

（2）成本優(yōu)化策略

①確定TSP路徑

如圖4所示，在一個(gè)隨機(jī)部署了N個(gè)傳感器節(jié)點(diǎn)的無(wú)線傳感器網(wǎng)絡(luò)中，基站位于無(wú)線傳感器網(wǎng)絡(luò)的中心，SenCar停靠在基站的附近。為了選出合適的“錨點(diǎn)”，我們首先定義集合A和B用來(lái)記錄“錨點(diǎn)”和“錨點(diǎn)”所覆蓋的傳感器集合，然后將傳感器節(jié)點(diǎn)進(jìn)行聚類，得到充電集合Si，針對(duì)每個(gè)充電集合，分別計(jì)算各傳感器節(jié)點(diǎn)的平均損耗，并選擇平均損耗最低的節(jié)點(diǎn)作為“錨點(diǎn)”。如果B包含在充電節(jié)點(diǎn)集合N中的所有傳感器節(jié)點(diǎn)，那么算法將終止。否則，繼續(xù)在剩余平均損耗最低的節(jié)點(diǎn)中找到下一個(gè)集合，直到覆蓋完所有的傳感器節(jié)點(diǎn)?！板^點(diǎn)”選擇算法的偽代碼如下所示。

選擇并確定好“錨點(diǎn)”的位置后，接下來(lái)再通過(guò)旅行商算法對(duì)所有選出的“錨點(diǎn)”求一條完整的TSP路徑，SenCar從基站出發(fā)，沿著TSP路徑的位置有序地對(duì)“錨點(diǎn)”進(jìn)行充電，直到挑選出的“錨點(diǎn)”覆蓋到整個(gè)無(wú)線傳感器網(wǎng)絡(luò)。假設(shè)有網(wǎng)絡(luò)模型如圖5所示。

如圖5所示，基站位于無(wú)線傳感器網(wǎng)絡(luò)的中心，SenCar?？吭诨镜母浇G色的節(jié)點(diǎn)代表普通傳感器節(jié)點(diǎn)，紅色的節(jié)點(diǎn)代表“錨點(diǎn)”。SenCar從基站出發(fā)，經(jīng)過(guò)每個(gè)“錨點(diǎn)”的位置，圖5中“錨點(diǎn)”的TSP路徑就是對(duì)所有“錨點(diǎn)”求得完整的一條哈密頓回路。

圖5 “錨點(diǎn)”的TSP路徑

確定好“錨點(diǎn)”的TSP路徑后，考慮到當(dāng)無(wú)線可充電傳感器網(wǎng)絡(luò)的覆蓋區(qū)域足夠大時(shí)，而SenCar的電池容量有限，那么一個(gè)SenCar無(wú)法滿足所有傳感器節(jié)點(diǎn)的充電請(qǐng)求，因此，此時(shí)需要對(duì)整個(gè)Tours進(jìn)行劃分，這個(gè)過(guò)程中我們結(jié)合考慮SenCar的電池容量，SenCar的移動(dòng)成本以及多跳充電成本，從而將充電路線進(jìn)行劃分以分配給m個(gè)SenCar。假設(shè)SenCar的充電路線被分割為k個(gè)tours路徑，其中k取決于SenCar的充電容量。我們假設(shè)讓cmax代表從任何節(jié)點(diǎn)到基站路徑上的最大能量開銷，cr代表使用一個(gè)SenCar在一個(gè)完整路徑r上產(chǎn)生的能量成本。

如圖6所示，確定好“錨點(diǎn)”的TSP路徑后，接下來(lái)對(duì)“錨點(diǎn)”的TSP路徑進(jìn)行劃分，根據(jù)SenCar的服務(wù)能力，將分割好的TSP路徑分配給一定數(shù)量的SenCar。每個(gè)SenCar都沿著對(duì)應(yīng)TSP路徑的位置有序地對(duì)“錨點(diǎn)”進(jìn)行充電。路徑劃分算法的偽代碼如下所示。

算法2路徑劃分算法

Input:Set of anchorsA,SenCarsM,energy de?manddiof nodei,charging efficiency of nodej,ηj,iwhen SenCar is ati.Set of SenCars’initial locationsI,capacityCh,base station b,max energy cost traveling on an edgecmax.

Output:Recharge sequencerjfor SenCar j’s tour.

圖6 劃分TSP路徑

接下來(lái)我們需要對(duì)系統(tǒng)的總開銷進(jìn)行優(yōu)化。首先，我們使用加權(quán)平均法將多跳能量傳遞過(guò)程中的充電成本和SenCar的移動(dòng)成本以及SenCar的使用成本構(gòu)建成一個(gè)單目標(biāo)優(yōu)化問(wèn)題，F(xiàn)=w1(FC+FM)+w2FS，如果w2＞w1，那么我們認(rèn)為更關(guān)心SenCar的使用成本，如果w1＞w2，那么我們認(rèn)為更關(guān)心充電成本和Sen?Car的移動(dòng)成本。如果增加SenCar的使用數(shù)量后，那么SenCar的使用成本將增加，若此時(shí)充電成本和Sen?Car移動(dòng)成本減少的量大于增加SenCar數(shù)量的使用成本，那么我們將多使用SenCar數(shù)量以降低系統(tǒng)總開銷。否則，不考慮增加SenCar的數(shù)量來(lái)優(yōu)化系統(tǒng)總成本。我們讓?fm代表增加SenCar數(shù)量后SenCar移動(dòng)成本的變化，?fc代表增加SenCar數(shù)量后多跳能量傳遞過(guò)程中充電成本的變化，?fs代表增加SenCar數(shù)量后Sen?Car使用成本的變化，然后讓 ΔF=w1(?fm+?fc)+w2?fs，如果ΔF＜0，那么此時(shí)系統(tǒng)的總開銷降低了。該成本優(yōu)化算法的偽代碼如下所示。

算法3成本優(yōu)化算法

Input:Recharge sequencea1,a2,…als,set of an?chorsAs,energy demanddiof node i,charging efficien?cy of j,ηj,iif SenCar is at i,moving costci,jon edge(i,j),time feasibility mark at anchorx←0,objective weightsw1,w2,charging setSafor all anchors.

Output:Total system cost F and the number of in?creased SenCar k.

3.if increase k SenCars then

7.ifΔF＜0then

8.The total system cost is reduced.

9.Find minimum total system costFand the number of increased SenCar k.

10.end if

11.end if

12.end while

6 實(shí)驗(yàn)?zāi)M和分析

本節(jié)在Eclipse平臺(tái)上分別對(duì)上述提出的算法進(jìn)行模擬實(shí)驗(yàn)。本節(jié)主要模擬了不同感應(yīng)場(chǎng)半徑和最大充電范圍對(duì)SenCar數(shù)量的影響，不同SenCar數(shù)量對(duì)SenCar移動(dòng)成本的影響以及不同SenCar數(shù)量對(duì)系統(tǒng)總開銷的影響。

（1）實(shí)驗(yàn)參數(shù)設(shè)置

實(shí)驗(yàn)假定傳感器節(jié)點(diǎn)隨機(jī)拋灑在無(wú)線傳感器網(wǎng)絡(luò)中，我們假設(shè)傳感器節(jié)點(diǎn)的數(shù)量為N=50，SenCar的數(shù)量從2個(gè)增加到8個(gè)。相關(guān)參數(shù)設(shè)置如表3所示。

表3 實(shí)驗(yàn)參數(shù)設(shè)置

實(shí)驗(yàn)參數(shù)設(shè)置好后，根據(jù)表3和模擬結(jié)果，可以估計(jì)出效率超過(guò)30%的有效充電范圍為rmax=3m。此時(shí)將所有參數(shù)代入式（17）中，得到m≥1.48，也就是說(shuō)使用2個(gè)SenCar基本上就能滿足所有傳感器的能量需求。

（2）不同感應(yīng)場(chǎng)半徑和最大充電范圍對(duì)SenCar數(shù)量的影響

我們首先研究了不同感應(yīng)場(chǎng)半徑和最大充電范圍對(duì)SenCar數(shù)量的影響，通過(guò)理論分析結(jié)果可以得到不同感應(yīng)場(chǎng)半徑和最大充電范圍下所需最少的SenCar數(shù)量，假設(shè)感應(yīng)場(chǎng)半徑從25m增加到50m，最大充電范圍從2m增加到4m。理論分析結(jié)果如圖7所示。

圖7描述了不同感應(yīng)場(chǎng)半徑以及最大充電范圍下所需的最少SenCar數(shù)量，如圖7（a）所示，隨著感應(yīng)場(chǎng)半徑的增加，所需的最少SenCar數(shù)量均逐漸增加，但最大充電范圍為2m相比3m變化更明顯。而如圖7（b）所示，隨著最大充電范圍的增加，所需的最少Sen?Car數(shù)量均逐漸減少，但感應(yīng)場(chǎng)半徑為30m相比25m下降的更明顯。由此可見，完成無(wú)線傳感器網(wǎng)絡(luò)中所有充電任務(wù)所需最少的SenCar數(shù)量與感應(yīng)場(chǎng)半徑以及最大充電范圍有關(guān)。

圖7

圖8 不同SenCar數(shù)量下SenCar移動(dòng)成本的變化

圖9 不同SenCar數(shù)量下系統(tǒng)總成本的變化

（3）不同SenCar數(shù)量下SenCar移動(dòng)成本的變化

接下來(lái)我們著重研究不同SenCar數(shù)量對(duì)SenCar移動(dòng)成本的影響，通過(guò)模擬實(shí)驗(yàn)得到不同SenCar數(shù)量在SenCar單位距離移動(dòng)消耗已知條件下SenCar移動(dòng)成本的變化情況，假設(shè)SenCar數(shù)量從2個(gè)增加到8個(gè)，SenCar單位距離的移動(dòng)消耗取值為12J/m和24J/m。模擬實(shí)驗(yàn)結(jié)果如圖8所示。

圖8描述了不同SenCar數(shù)量下SenCar移動(dòng)成本隨SenCar單位距離移動(dòng)消耗取值不同的變化情況，由圖可見，隨著SenCar使用數(shù)量的增加，SenCar的移動(dòng)成本均逐漸下降，因?yàn)殡S著SenCar數(shù)量的增加，SenCar的移動(dòng)路徑變短，因而移動(dòng)成本也隨之降低了。

（4）不同SenCar數(shù)量下系統(tǒng)總成本的變化

最后，我們還研究了不同SenCar數(shù)量對(duì)系統(tǒng)總成本的影響，通過(guò)模擬實(shí)驗(yàn)得到不同SenCar數(shù)量在Sen?Car單位距離移動(dòng)消耗已知的條件下系統(tǒng)總成本的變化情況，假設(shè)SenCar數(shù)量從2個(gè)增加到8個(gè)，SenCar單位距離的移動(dòng)損耗取值為12J/m和24J/m。模擬實(shí)驗(yàn)結(jié)果如圖9所示。

圖9描述了不同SenCar數(shù)量下系統(tǒng)總成本隨SenCar單位距離移動(dòng)消耗取值不同的變化情況，由圖可見，當(dāng)SenCar單位距離移動(dòng)消耗為12J/m時(shí)，隨著SenCar數(shù)量的增加，系統(tǒng)總成本也逐漸升高。當(dāng)Sen?Car單位距離移動(dòng)消耗為24J/m時(shí)，隨著SenCar數(shù)量的增加，系統(tǒng)總成本呈一定波動(dòng)趨勢(shì)。由圖可見，當(dāng)SenCar數(shù)量為2時(shí)，系統(tǒng)的總成本最小。

7 結(jié)語(yǔ)

本文通過(guò)結(jié)合無(wú)線可充電傳感器網(wǎng)絡(luò)中的多跳無(wú)線充電技術(shù)和移動(dòng)數(shù)據(jù)采集模型，提出一個(gè)新的最優(yōu)成本優(yōu)化方案。首先，根據(jù)能量消耗和能量補(bǔ)充之間的關(guān)系可以近似得到完成所有充電任務(wù)所需最少的SenCar數(shù)量。接下來(lái)將傳感器節(jié)點(diǎn)進(jìn)行聚類，針對(duì)每個(gè)充電集合，分別求出各節(jié)點(diǎn)的平均損耗，優(yōu)先選擇平均損耗最低的節(jié)點(diǎn)作為“錨點(diǎn)”，且SenCar在給“錨點(diǎn)”充電的同時(shí)還對(duì)各傳感器節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)進(jìn)行移動(dòng)采集。然后對(duì)所有選出的“錨點(diǎn)”求一條完整的TSP路徑，再根據(jù)SenCar的電池容量，SenCar的移動(dòng)成本和多跳能量傳遞過(guò)程中的充電成本將充電路線進(jìn)行劃分并分配給一定數(shù)量的SenCar，保證每條路徑都在一個(gè)SenCar的服務(wù)范圍內(nèi)，從而得到完成所有充電任務(wù)所需的總成本。最后，我們對(duì)提出的算法進(jìn)行模擬實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，該策略在滿足一定時(shí)間約束下，使用適當(dāng)數(shù)量的SenCar可以使得完成所有充電任務(wù)的總開銷最低。