非對稱占空比傳感網(wǎng)中的廣播能效優(yōu)化算法

徐力杰

(1. 南京郵電大學(xué) 計算機(jī)學(xué)院、軟件學(xué)院、網(wǎng)絡(luò)空間安全學(xué)院, 南京 210023；2. 南京郵電大學(xué) 江蘇省大數(shù)據(jù)安全與智能處理重點(diǎn)實(shí)驗(yàn)室, 南京 210023； 3. 南京大學(xué) 計算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室, 南京 210023)(*通信作者電子郵箱ljxu@njupt.edu.cn)

0 引言

多跳廣播作為無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)中的一項(xiàng)重要基本功能，近些年受到了越來越多研究者的關(guān)注。許多實(shí)際應(yīng)用都要求sink節(jié)點(diǎn)將消息(例如配置命令、更新的代碼等)以能量有效的方式分發(fā)到網(wǎng)絡(luò)中的每一個傳感器節(jié)點(diǎn)。為了極大地減少由于空閑偵聽(idle listening)所帶來的能量浪費(fèi)，實(shí)際中的傳感器節(jié)點(diǎn)通常都是以占空比(duty cycled)的方式進(jìn)行工作[1]，即每個節(jié)點(diǎn)周期性地在工作狀態(tài)和睡眠狀態(tài)之間交替切換, 這樣的占空比工作方式在一定程度上導(dǎo)致廣播能耗的低效性。如何為這樣的網(wǎng)絡(luò)設(shè)計能量高效的廣播調(diào)度算法是一個重要且具有挑戰(zhàn)性的問題。

很多現(xiàn)有工作[2-11]研究了占空比傳感網(wǎng)中的廣播能效優(yōu)化問題。盡管如此，這些工作大多數(shù)都是將所有節(jié)點(diǎn)的廣播總能量消耗作為刻畫網(wǎng)絡(luò)廣播能效性能的準(zhǔn)則。實(shí)際上，總能量消耗并不是傳感網(wǎng)中刻畫能量效率的最有效準(zhǔn)則。很多典型的傳感網(wǎng)應(yīng)用都要求系統(tǒng)長期地部署在一些環(huán)境較為惡劣的場景中，在這樣的場景下通常很難更換節(jié)點(diǎn)電池或給節(jié)點(diǎn)電池充電，這意味著節(jié)點(diǎn)的負(fù)載均衡性是能更有效刻畫能量效率的準(zhǔn)則，這是因?yàn)楣?jié)點(diǎn)間不均衡的負(fù)載可能會讓一部分承擔(dān)了更多工作量的節(jié)點(diǎn)更快地耗盡了它們的能量，從而使得系統(tǒng)過早地失效。當(dāng)前，大多數(shù)現(xiàn)有工作主要關(guān)注在占空比傳感網(wǎng)中如何進(jìn)行負(fù)載均衡的數(shù)據(jù)收集[12-15]，非常少的工作考慮了數(shù)據(jù)分發(fā)(廣播)的負(fù)載均衡問題。在實(shí)際中，一旦廣播調(diào)度確定之后，它通常會被執(zhí)行較長的一段時間，并且由于更新代價較高而通常不會頻繁地動態(tài)更新廣播調(diào)度。顯然，沒有經(jīng)過優(yōu)化設(shè)計的廣播調(diào)度可能會導(dǎo)致節(jié)點(diǎn)間廣播負(fù)載的高度不均衡性，因此，仔細(xì)地設(shè)計出一個面向占空比傳感網(wǎng)的廣播調(diào)度以實(shí)現(xiàn)節(jié)點(diǎn)間廣播負(fù)載的均衡性是重要且具有挑戰(zhàn)性的。

對于占空比傳感網(wǎng)而言，廣播延遲通常是一個首要考慮的性能準(zhǔn)則。對于許多實(shí)際的廣播應(yīng)用，例如配置命令分發(fā)，每個節(jié)點(diǎn)都期望能夠盡快地收到來自sink節(jié)點(diǎn)的廣播消息及時更新自身的配置，以使得新的系統(tǒng)需求能夠盡快地被滿足。換句話說，很多實(shí)際廣播應(yīng)用都期望能夠盡可能地減少從sink節(jié)點(diǎn)到每個傳感器節(jié)點(diǎn)的端到端廣播延遲。本文主要關(guān)注占空比傳感網(wǎng)中最小端到端廣播延遲約束下的廣播能效優(yōu)化問題。值得注意的是，這里的廣播能效優(yōu)化除了考慮了傳統(tǒng)的廣播總能量消耗優(yōu)化之外，還重點(diǎn)考慮了廣播的負(fù)載均衡優(yōu)化，即節(jié)點(diǎn)的最大廣播負(fù)載最小化。

在本文的前期工作[16]中，初步研究了占空比傳感網(wǎng)中最小端到端廣播延遲約束下的廣播負(fù)載均衡問題，證明了該問題是NP難問題并且提出了一個有效的解決方法。盡管如此，文獻(xiàn)[16]中作了一些嚴(yán)格的假設(shè)，例如假設(shè)了所有節(jié)點(diǎn)的占空比是對稱的，即所有節(jié)點(diǎn)的占空比必須相同且每個工作調(diào)度周期里只能嚴(yán)格地包含一個活動時隙，并且還假設(shè)所有節(jié)點(diǎn)的傳輸功率都是相等且固定的。不同于前期工作[16]，本文進(jìn)一步放松了文獻(xiàn)[16]中的假設(shè)，考慮了一個更加一般化的系統(tǒng)模型。具體地說，本文的工作可以適用于節(jié)點(diǎn)的占空比是非對稱的情況，即允許各個節(jié)點(diǎn)可以靈活地定義不同的占空比，每個工作調(diào)度周期里允許包含任意多個活動時隙，并且假設(shè)了每個節(jié)點(diǎn)可以自適應(yīng)地調(diào)節(jié)自身的傳輸功率，這樣的假設(shè)更加具有實(shí)際意義。

1 系統(tǒng)模型與問題描述

本文假設(shè)時間被劃分成一系列大小相等的時隙(time slot)，并且每個時隙的長度設(shè)置能夠保證一次數(shù)據(jù)包的傳輸。為了減少空閑偵聽帶來的能量浪費(fèi)，整個網(wǎng)絡(luò)假設(shè)采用占空比的工作方式，每個節(jié)點(diǎn)在部署之后可以根據(jù)一定的能量管理協(xié)議確定自身的工作調(diào)度。為了簡便性且不失一般性，本文假設(shè)每個節(jié)點(diǎn)的工作調(diào)度是周期性的，且所有節(jié)點(diǎn)工作調(diào)度周期的長度T相同。具體地說，定義任意節(jié)點(diǎn)的每個工作調(diào)度周期由T個時隙組成，其中任意一個時隙t(t∈{0,1,…,T-1})要么是活動時隙要么是睡眠時隙。當(dāng)一個節(jié)點(diǎn)處于活動時隙時，它將會開啟自身的無線通信模塊，并且可以進(jìn)行數(shù)據(jù)的感知、信道的偵聽以及數(shù)據(jù)的發(fā)送和接收；當(dāng)一個節(jié)點(diǎn)處于睡眠時隙時，它將會關(guān)閉自身的無線通信模塊，設(shè)置一個計時器(timer)以便在未來喚醒自己。因此，節(jié)點(diǎn)的占空比可以表示為一個工作調(diào)度周期內(nèi)活動時隙的數(shù)量與一個工作調(diào)度周期內(nèi)所有時隙數(shù)量的比值。這里，用每個工作調(diào)度周期內(nèi)活動時隙的集合W(j)來表示任意節(jié)點(diǎn)j的工作調(diào)度，即:

(1)

圖1 周期性工作調(diào)度示例

不失一般性，本文允許各個節(jié)點(diǎn)定義不同的占空比，即對于任意節(jié)點(diǎn)i和j(i≠j)，可以有|W(i) | ≠|(zhì)W(j) |; 同時假設(shè)每個節(jié)點(diǎn)的傳輸功率共有m個離散的等級，即P1,P2, …,Pm，每個節(jié)點(diǎn)可以根據(jù)到接收節(jié)點(diǎn)的距離自適應(yīng)地調(diào)節(jié)自身的傳輸功率等級。這里用無向圖G(j)=(V,E(j)) (j=1,2,…,m)來表示當(dāng)所有節(jié)點(diǎn)都采用傳輸功率等級Pj時形成的網(wǎng)絡(luò)拓?fù)?，其中V表示包括sink節(jié)點(diǎn)v0和所有感知節(jié)點(diǎn){v1,v2,…,vN-1} 在內(nèi)的N個拓?fù)涔?jié)點(diǎn)的集合，E(j)表示所有通信鏈路的集合，任意兩個節(jié)點(diǎn)之間存在一條通信鏈路當(dāng)且僅當(dāng)它們采用傳輸功率等級Pj時能夠相互通信。

此外，本文也作了如下一些基本假設(shè)：1)網(wǎng)絡(luò)中實(shí)現(xiàn)了時鐘同步[17]，由于只需要保證局部鄰居節(jié)點(diǎn)間的時鐘同步，因此實(shí)際開銷并不大。2)為了便于描述且不失一般性，本文假設(shè)sink節(jié)點(diǎn)v0的每個工作調(diào)度周期內(nèi)只包含一個活動時隙，即表示廣播消息傳輸?shù)钠鹗紩r間。3)假設(shè)節(jié)點(diǎn)廣播負(fù)載僅需考慮發(fā)送廣播數(shù)據(jù)的能耗而無需考慮接收廣播數(shù)據(jù)的能耗，這一假設(shè)在實(shí)際中是合理的，這是因?yàn)楣?jié)點(diǎn)的空閑偵聽模式通常和接收模式具有近乎相同的功率，且在本文的模型中每個節(jié)點(diǎn)僅僅在它調(diào)度的活動時隙內(nèi)接收數(shù)據(jù)，這意味著所有節(jié)點(diǎn)接收數(shù)據(jù)的能耗可以近似地被忽略。4)本文主要面向鏈路質(zhì)量可靠的網(wǎng)絡(luò)，即假設(shè)網(wǎng)絡(luò)中的鏈路質(zhì)量是100%完全可靠的。

本文主要關(guān)注占空比傳感網(wǎng)中最小端到端廣播延遲約束下的廣播能效優(yōu)化問題，分別采用兩種準(zhǔn)則來刻畫廣播能效：一是節(jié)點(diǎn)的總能量消耗，二是節(jié)點(diǎn)的負(fù)載均衡性。這里假設(shè)網(wǎng)絡(luò)中已經(jīng)采用了某個現(xiàn)有的負(fù)載均衡的數(shù)據(jù)收集協(xié)議，該協(xié)議能夠平衡由于節(jié)點(diǎn)間占空比的不同所帶來的能耗差異，這意味著本文只需要考慮節(jié)點(diǎn)間廣播負(fù)載的均衡性即可，而不必考慮節(jié)點(diǎn)間占空比的不同對節(jié)點(diǎn)能耗均衡的影響。

定義1 廣播轉(zhuǎn)發(fā)決策。對于網(wǎng)絡(luò)中任意節(jié)點(diǎn)，它的廣播轉(zhuǎn)發(fā)決策表示為一組廣播消息轉(zhuǎn)發(fā)行為的集合，用f(vi) = {[轉(zhuǎn)發(fā)時隙k，傳輸功率Pj] |k∈{0,1, …,T-1},j∈{1, 2, …,m}}來表示任意節(jié)點(diǎn)vi的廣播轉(zhuǎn)發(fā)決策，其中任意一個轉(zhuǎn)發(fā)行為“[轉(zhuǎn)發(fā)時隙k，傳輸功率Pj]”表示節(jié)點(diǎn)vi在下一個時隙k以傳輸功率等級Pj轉(zhuǎn)發(fā)廣播消息。特殊地，如果廣播轉(zhuǎn)發(fā)決策f(vi)為空集，則表示節(jié)點(diǎn)vi不是廣播消息轉(zhuǎn)發(fā)節(jié)點(diǎn)。

定義2 廣播調(diào)度。 給定一個占空比傳感網(wǎng)的拓?fù)鋱DG(j)=(V,E(j))(j=1,2, …,m)以及V中所有節(jié)點(diǎn)的工作調(diào)度，V中所有節(jié)點(diǎn)的一組廣播轉(zhuǎn)發(fā)決策的集合M= {f(v) |v∈V}被稱之為一個廣播調(diào)度當(dāng)且僅當(dāng)M中的所有廣播轉(zhuǎn)發(fā)決策能夠保證廣播消息從源節(jié)點(diǎn)v0成功傳輸?shù)矫恳粋€感知節(jié)點(diǎn)vi(i∈{1,2,…,N-1})。

本文的目標(biāo)是解決如下兩個問題：

問題1 最小延遲約束最小能量廣播問題。給定一個占空比傳感網(wǎng)的拓?fù)鋱DG(j)=(V,E(j))(j=1,2,…,m)以及V中所有節(jié)點(diǎn)的工作調(diào)度，如何找到一個以sink節(jié)點(diǎn)v0為源節(jié)點(diǎn)的廣播調(diào)度，在保證滿足從v0到每個感知節(jié)點(diǎn)的端到端廣播延遲最小的約束條件下使得所有節(jié)點(diǎn)的廣播總能量消耗最小化。

問題2 最小延遲約束負(fù)載均衡廣播問題。給定一個占空比傳感網(wǎng)的拓?fù)鋱DG(j)=(V,E(j))(j=1,2,…,m)以及V中所有節(jié)點(diǎn)的工作調(diào)度，如何找到一個以sink節(jié)點(diǎn)v0為源節(jié)點(diǎn)的廣播調(diào)度，在保證滿足從v0到每個感知節(jié)點(diǎn)的端到端廣播延遲最小的約束條件下使得節(jié)點(diǎn)的最大廣播負(fù)載最小化。

2 解決方法

2.1 問題建模

(2)

特殊地，定義Si,0=?。此外，用c(Pj)表示當(dāng)任意節(jié)點(diǎn)以傳輸功率等級Pj傳輸一個數(shù)據(jù)包時所消耗的能量。

為了便于問題的建模，本文首先將占空比網(wǎng)絡(luò)的拓?fù)鋱D轉(zhuǎn)換成一個能清晰刻畫廣播時空特征的時空狀態(tài)圖Gs=(Vs,Es)，其中Vs共包含兩類頂點(diǎn)：拓?fù)漤旤c(diǎn)和狀態(tài)頂點(diǎn)。每個拓?fù)漤旤c(diǎn)代表處于某個時間狀態(tài)的V中的某個節(jié)點(diǎn)，用t′(v)表示任意拓?fù)漤旤c(diǎn)v的時間狀態(tài)；每個狀態(tài)頂點(diǎn)代表一個時空狀態(tài)，用一個二元組〈時間狀態(tài)t, 空間狀態(tài)S〉來描述，它表示集合S中的所有節(jié)點(diǎn)在時隙t收到廣播消息。

下面將介紹如何構(gòu)造時空狀態(tài)圖Gs。

步驟1 對于V中的每一個節(jié)點(diǎn)v，分別構(gòu)造|W(v)|個拓?fù)漤旤c(diǎn)與之對應(yīng)。具體地說，對于每個t∈W(v)，將構(gòu)造一個對應(yīng)的拓?fù)漤旤c(diǎn)v′，將其添加進(jìn)Vs，并且定義它的時間狀態(tài)t′(v′)=t。

(3)

而對于Es中任意一條從狀態(tài)頂點(diǎn)u′到拓?fù)漤旤c(diǎn)v′的有向邊(u′,v′)，定義它的延遲權(quán)重d(u′,v′)=0。

這里將用一個簡單的示例來說明時空狀態(tài)圖的構(gòu)造過程。圖2給出了一個簡單的網(wǎng)絡(luò)拓?fù)鋱D示例，其中工作調(diào)度周期長度T=10且任意節(jié)點(diǎn)vi旁邊標(biāo)注的集合表示它的工作調(diào)度W(vi)。圖2(a)表示當(dāng)所有節(jié)點(diǎn)采用傳輸功率等級P1時的網(wǎng)絡(luò)拓?fù)銰(1)，圖2(b)則表示網(wǎng)絡(luò)拓?fù)銰(2),G(3), …,G(m)，其中m≥2。

圖2 網(wǎng)絡(luò)拓?fù)鋱D示例

根據(jù)定義可以得到：S0,1={v1,v2}，S0,2={v1,v2,v3,v4}，S1,1={v3,v4}，S1,2={v2,v3,v4}，S2,1={v3,v4}，S2,2={v1,v3,v4}，S3,1= {v1,v2}，S3,2={v1,v2,v4}，S4,1={v1,v2}，S4,2={v1,v2,v3}。通過對圖2所示的網(wǎng)絡(luò)拓?fù)洳捎蒙鲜龅姆椒ǎ梢缘玫饺鐖D3所示的時空狀態(tài)圖，其中包含了拓?fù)漤旤c(diǎn){v0′,v1′,v2′,v3′,v4′,v5′}和狀態(tài)頂點(diǎn){u1′,u2′,u3′,u4′,u5′,u6′,u7′}。在該示例中，只有節(jié)點(diǎn)v1的工作調(diào)度周期中包含了2個活動時隙，因此根據(jù)步驟1，分別構(gòu)造2個拓?fù)漤旤c(diǎn)v1′和v2′來代表節(jié)點(diǎn)v1，并且定義t′(v1′) = 3，t′(v2′) = 8。節(jié)點(diǎn)v0、v2、v3、v4則可以分別用拓?fù)漤旤c(diǎn)v0′、v3′、v4′、v5′來代表，并且定義t′(v0′) = 0，t′(v3′) = 8，t′(v4′) = 3，t′(v5′) = 6。每條有向邊的延遲權(quán)重由此可以通過步驟3計算得到。

圖3 時空狀態(tài)圖的構(gòu)造

不難發(fā)現(xiàn)，時空狀態(tài)圖很好地刻畫了原始網(wǎng)絡(luò)拓?fù)鋱D中廣播的時空特征。接下來，將在構(gòu)造的時空狀態(tài)圖Gs中找到一棵以代表了sink節(jié)點(diǎn)v0的拓?fù)漤旤c(diǎn)v0′為根的最短延遲權(quán)重胖樹(fat-tree)。本文采用一個類似于Dijkstra算法的方法可以很容易求得這樣一棵最短延遲權(quán)重胖樹。用ParentSet(Gs,v′)表示時空狀態(tài)圖Gs中任意非根頂點(diǎn)v′在最短延遲權(quán)重胖樹上的父頂點(diǎn)集合，并且用ParentSet(G,v)表示原始網(wǎng)絡(luò)拓?fù)鋱DG(j)=(V,E(j)) (j=1,2,…,m)中任意非根節(jié)點(diǎn)v在最短延遲路徑胖樹上的父節(jié)點(diǎn)集合，用node(v)表示時空狀態(tài)圖Gs中的任意拓?fù)漤旤c(diǎn)v所代表的原始網(wǎng)絡(luò)拓?fù)鋱D中的節(jié)點(diǎn)。進(jìn)一步地，通過如下的方式根據(jù)時空狀態(tài)圖中的最短延遲權(quán)重胖樹得到原始網(wǎng)絡(luò)拓?fù)鋱D中的最短延遲路徑胖樹：對于任意非根節(jié)點(diǎn)vi∈V，用Su(vi)表示在時空狀態(tài)圖Gs里其空間狀態(tài)覆蓋了節(jié)點(diǎn)vi的所有狀態(tài)頂點(diǎn)中最短延遲值D*(·)最小的狀態(tài)頂點(diǎn)集合，不難得到vi的最優(yōu)父節(jié)點(diǎn)集合

(4)

已知V中所有非根節(jié)點(diǎn)的最優(yōu)父節(jié)點(diǎn)集合便可以構(gòu)造出原始網(wǎng)絡(luò)拓?fù)鋱D中的一棵最短延遲路徑胖樹。根據(jù)所有非根節(jié)點(diǎn)的最優(yōu)父節(jié)點(diǎn)集合，同樣也可以得到原始網(wǎng)絡(luò)拓?fù)鋱D上任意節(jié)點(diǎn)v的最優(yōu)子節(jié)點(diǎn)集合，用ChildrenSet(G,v)表示。換句話說，節(jié)點(diǎn)vi∈ParentSet(G,vj)當(dāng)且僅當(dāng)節(jié)點(diǎn)vj∈ChildrenSet(G,vi)。此外，對于任意節(jié)點(diǎn)vi∈V，用t′(vi)表示在時空狀態(tài)圖Gs里代表了節(jié)點(diǎn)vi的所有拓?fù)漤旤c(diǎn)中最短端到端延遲值最小的拓?fù)漤旤c(diǎn)的時間狀態(tài)；對于任意節(jié)點(diǎn)vj∈ChildrenSet(G,vi)，用P(vi,vj)表示節(jié)點(diǎn)vi能夠與節(jié)點(diǎn)vj通信的最小傳輸功率等級。

為了更清晰地描述問題，為每個節(jié)點(diǎn)vi∈V定義了一個候選轉(zhuǎn)發(fā)行為集合F(vi)，并且通過如下的方式進(jìn)行構(gòu)造：初始地，定義F(vi)=?。對于每個節(jié)點(diǎn)vj∈ChildrenSet(G,vi)，將轉(zhuǎn)發(fā)行為f=[t′(vj),P(vi,vj)]添加進(jìn)F(vi)，即F(vi) =F(vi)∪{f}，這里用cost(vi,f)、coverage(vi,f)分別表示節(jié)點(diǎn)vi的轉(zhuǎn)發(fā)行為f(即在t′(vj)時隙以P(vi,vj)功率等級轉(zhuǎn)發(fā))的能耗代價和接收節(jié)點(diǎn)覆蓋范圍，并且設(shè)置cost(vi,f) =c(P(vi,vj))，coverage(vi,f) = {v∈ChildrenSet(G,vi) |t′(v)=t′(vj) &&P(vi,v)≤P(vi,vj)}，同時定義timeslot(vi,f) =t′(vj)為節(jié)點(diǎn)vi的轉(zhuǎn)發(fā)行為f的時間狀態(tài)。通過上述的方法，可以得到所有節(jié)點(diǎn)的候選轉(zhuǎn)發(fā)行為集合。

具體地說，目標(biāo)問題1可以等價于如下的最小代價轉(zhuǎn)發(fā)行為子集覆蓋問題(Minimum-Cost Forwarding Decision Subset Coverage Problem, MC-SCP)。

問題3 最小代價轉(zhuǎn)發(fā)行為子集覆蓋問題。已知所有節(jié)點(diǎn)的候選轉(zhuǎn)發(fā)行為集合，如何為每個節(jié)點(diǎn)v∈V選擇一個轉(zhuǎn)發(fā)行為子集f(v)?F(v)，以實(shí)現(xiàn):

(5)

同時滿足如下兩個約束條件：

1)對于每個節(jié)點(diǎn)v∈V的轉(zhuǎn)發(fā)行為子集f(v)中的任意兩個不同的轉(zhuǎn)發(fā)行為fi和fj，都有timeslot(v,fi)≠timeslot(v,fj)；

類似地，目標(biāo)問題2也可以等價于如下的代價均衡轉(zhuǎn)發(fā)行為子集覆蓋問題(Cost-Balanced Forwarding Decision Subset Coverage Problem, CB-SCP)。

問題4 代價均衡轉(zhuǎn)發(fā)行為子集覆蓋問題。已知所有節(jié)點(diǎn)的候選轉(zhuǎn)發(fā)行為集合，如何為每個節(jié)點(diǎn)v∈V選擇一個轉(zhuǎn)發(fā)行為子集f(v)?F(v)，以實(shí)現(xiàn)

(6)

同時滿足如下兩個約束條件：

1)對于每個節(jié)點(diǎn)v∈V的轉(zhuǎn)發(fā)行為子集f(v)中的任意兩個不同的轉(zhuǎn)發(fā)行為fi和fj，都有timeslot(v,fi)≠timeslot(v,fj)；

2.2 問題求解

本節(jié)將介紹如何求解問題3和問題4。

(7)

性質(zhì)1 對于每個節(jié)點(diǎn)v∈V的轉(zhuǎn)發(fā)行為子集f(v)中的任意兩個不同的轉(zhuǎn)發(fā)行為fi和fj，如果滿足timeslot(v,fi) =timeslot(v,fj)且cost(v,fi)

根據(jù)2.1節(jié)中的定義，很容易發(fā)現(xiàn)性質(zhì)1是一定成立的。在圖3的例子中，很顯然一定有coverage(v0, [3,P1])?coverage(v0, [3,P2])。由性質(zhì)1可以得到如下的結(jié)論。

定理1 問題3等價于最小加權(quán)集合覆蓋問題。

證畢。

由于已知最小加權(quán)集合覆蓋問題是NP-hard問題，因此問題3也是NP-hard的。這里可以采用文獻(xiàn)[18]中經(jīng)典的貪婪算法(本文稱之為最小代價轉(zhuǎn)發(fā)行為子集覆蓋算法(Minimum-Cost Forwarding Decision Subset Coverage Algorithm, MC-SCA))來解決問題3，該算法每一輪貪婪地選擇“轉(zhuǎn)發(fā)行為代價/新增覆蓋節(jié)點(diǎn)數(shù)量”值最小的轉(zhuǎn)發(fā)行為，即每一輪選擇的轉(zhuǎn)發(fā)行為能夠以盡可能小的代價覆蓋盡可能多的未被覆蓋的節(jié)點(diǎn)。根據(jù)文獻(xiàn)[18]，可以容易證明該算法是求解問題3的一個H(dmax)-近似算法，其中調(diào)和級數(shù)H(dmax) = 1+1/2+…+1/dmax，且dmax表示在拓?fù)銰(m)中的最大節(jié)點(diǎn)度。

由于問題4是文獻(xiàn)[16]中目標(biāo)問題的一般化問題，且文獻(xiàn)[16]中的目標(biāo)問題已經(jīng)被證明是NP-hard問題，因此不難得出問題4一定是NP-hard問題。這里，本文提出如算法1所示的代價均衡轉(zhuǎn)發(fā)行為子集覆蓋算法(Cost-Balanced Forwarding Decision Subset Coverage Algorithm, CB-SCA)來解決問題4。在算法1中，用COST(v)表示任意節(jié)點(diǎn)v∈V的轉(zhuǎn)發(fā)能耗負(fù)載，并且初始地賦值為0。對于每個節(jié)點(diǎn)v∈V中的每個候選轉(zhuǎn)發(fā)行為f∈F(v)，用z(v,f)表示當(dāng)選擇轉(zhuǎn)發(fā)行為f時節(jié)點(diǎn)v的轉(zhuǎn)發(fā)能耗負(fù)載與轉(zhuǎn)發(fā)行為f帶來的新增覆蓋節(jié)點(diǎn)數(shù)量的比值。在每一輪迭代中，將以z(v,f)為貪婪準(zhǔn)則選擇z(v,f)值最小的轉(zhuǎn)發(fā)行為，這是因?yàn)檩^小的z(v,f)意味著較小的節(jié)點(diǎn)v的轉(zhuǎn)發(fā)能耗負(fù)載以及較多的新增覆蓋節(jié)點(diǎn)數(shù)量。直覺上，每輪迭代選擇一個使得對應(yīng)節(jié)點(diǎn)所產(chǎn)生的轉(zhuǎn)發(fā)能耗負(fù)載越小的轉(zhuǎn)發(fā)行為能夠使得最終所有節(jié)點(diǎn)產(chǎn)生的轉(zhuǎn)發(fā)能耗負(fù)載最大值越?。煌瑫r，每輪迭代選擇帶來更多新增覆蓋節(jié)點(diǎn)數(shù)量的轉(zhuǎn)發(fā)行為在直覺上也能夠減少迭代輪數(shù)，從而帶來更好的能耗性能。

定理2 算法1一定能夠得到問題4的可行解。

證明 由于算法1的每輪迭代都會帶來一定新增的覆蓋節(jié)點(diǎn)且迭代的終止條件是所有的節(jié)點(diǎn){v1,v2,…,vN-1}被覆蓋，因此很容易可知問題4的第2)個約束條件一定可以滿足。這里主要證明算法1的求解結(jié)果一定能夠滿足問題4的第1)個約束條件。在算法1的第6～10行，對節(jié)點(diǎn)v中任意一個候選轉(zhuǎn)發(fā)行為f判斷是否在f(v)中存在一個時間狀態(tài)為timeslot(v,f)的轉(zhuǎn)發(fā)行為f′，如果存在，則有如下兩種情況：1) 若cost(v,f)

證畢。

算法1 代價均衡轉(zhuǎn)發(fā)行為子集覆蓋算法。

輸入 每個節(jié)點(diǎn)v∈V的候選轉(zhuǎn)發(fā)行為集合F(v)，以及每個轉(zhuǎn)發(fā)行為f∈F(v)的能耗代價cost(v,f)和接收節(jié)點(diǎn)覆蓋范圍coverage(v,f)。

輸出 每個節(jié)點(diǎn)v∈V的轉(zhuǎn)發(fā)行為子集f(v)?F(v)。

1)

對于每個v∈V，初始定義f(v)=?以及COST(v)=0;

2)

S=?;

3)

WHILES≠{v1,v2,…,vN-1}

4)

FOR 每個v∈V

5)

FOR 每個f∈F(v)

6)

IF 在f(v)中存在一個時間狀態(tài)為timeslot(v,f)的轉(zhuǎn)發(fā)行為f′

7)

z(v,f)=(COST(v)-cost(v,f′)+

cost(v,f))/|coverage(v,f)-S|;

8)

ELSE

9)

z(v,f)=(COST(v)+

cost(v,f))/|coverage(v,f)-S|;

10)

END

11)

END

12)

END

13)

找到一個v*∈V以及一個f*∈F(v*)，使得z(v*,f*)的值是所有z(v,f) (v∈V,f∈F(v))值中最小的;

14)

IF 在f(v*)中存在一個時間狀態(tài)為timeslot(v*,f*)的轉(zhuǎn)發(fā)行為f″

15)

f(v*) =(f(v*)-{f″}) ∪ {f*};

16)

COST(v*) =COST(v*)-cost(v*,f″)+cost(v*,f*);

17)

ELSE

18)

f(v*) =f(v*) ∪ {f*};

19)

COST(v*) =COST(v*)+cost(v*,f*);

20)

END

21)

S=S∪coverage(v*,f*);

22)

END

3 仿真實(shí)驗(yàn)

實(shí)驗(yàn)假設(shè)所有的傳感器節(jié)點(diǎn)均勻地分布在一個100 m×100 m的監(jiān)測區(qū)域，其中sink節(jié)點(diǎn)位于該監(jiān)測區(qū)域的中心。假設(shè)每個節(jié)點(diǎn)的每個工作調(diào)度周期中最多包含兩個活動時隙，具體地說，在實(shí)驗(yàn)中將每個節(jié)點(diǎn)的每個工作調(diào)度周期中的活動時隙數(shù)量設(shè)為1和2中的隨機(jī)值(即每個節(jié)點(diǎn)的占空比為1/T或2/T)，且每個節(jié)點(diǎn)獨(dú)立且隨機(jī)地確定自身的工作調(diào)度。通過這樣的方式，可以簡單且不失一般性地模擬節(jié)點(diǎn)占空比的非對稱性。特殊地，對于sink節(jié)點(diǎn)v0，假設(shè)其每個工作調(diào)度周期僅包含一個活動時隙，且定義W(v0)={0}。這里除非特別指出，默認(rèn)設(shè)置N=800，T=100。進(jìn)一步地，假設(shè)每個節(jié)點(diǎn)有5個離散的傳輸功率等級{P1,P2,…,P5}，其對應(yīng)的最大傳輸距離分別為10 m、15 m、20 m、25 m和30 m，并且采用如式(8)的經(jīng)典能量消耗模型來計算每個傳輸功率等級對應(yīng)的節(jié)點(diǎn)傳輸能耗：

ET(d)=l·ET-elec+l·εampd2

(8)

其中：d表示傳輸距離，ET-elec=50 nJ/bit,εamp=100 pJ/bit/m2，且廣播數(shù)據(jù)包長度l設(shè)置為1 000 b。這里，所有的實(shí)驗(yàn)結(jié)果均是運(yùn)行20次所得結(jié)果的平均值。

為了便于進(jìn)行性能比較，本文提出了如下的兩個基準(zhǔn)方法：

1)隨機(jī)父節(jié)點(diǎn)選擇算法，該方法通過讓原始網(wǎng)絡(luò)拓?fù)鋱DG上的任意非根節(jié)點(diǎn)v在ParentSet(G,v)中隨機(jī)地選擇一個節(jié)點(diǎn)作為它的父節(jié)點(diǎn)，從而生成一棵以v0為根的最短延遲路徑廣播樹。

2)最小節(jié)點(diǎn)負(fù)載優(yōu)先的貪心算法，該方法類似于算法1，唯一的不同在于對于貪心準(zhǔn)則z(v,f)定義的不同，即將算法1的第7)行更改為z(v,f)=COST(v)-cost(v,f′)+cost(v,f)，并且將第9)行更改為z(v,f)=COST(v)+cost(v,f)。

首先，比較了MC-SCA和隨機(jī)父節(jié)點(diǎn)選擇算法的廣播總能耗性能。通過圖4可以發(fā)現(xiàn)MC-SCA與典型的隨機(jī)父節(jié)點(diǎn)選擇算法相比其廣播總能耗平均降低了24.23%，并且隨著節(jié)點(diǎn)數(shù)量的增多以及節(jié)點(diǎn)工作調(diào)度周期長度的減小，MC-SCA的性能優(yōu)勢會變得更加顯著，這是因?yàn)楣?jié)點(diǎn)數(shù)量的增多和節(jié)點(diǎn)工作調(diào)度周期長度的減小會使得相鄰節(jié)點(diǎn)工作調(diào)度的活動時隙發(fā)生重疊的概率變得更高，且重疊數(shù)量的期望變得更大，這顯然對于本文使用的基于集合覆蓋的方法能夠帶來更大的性能提升空間。

圖4 MC-SCA和隨機(jī)父節(jié)點(diǎn)選擇算法廣播總能量 消耗隨著N和T變化時的性能比較

接著，驗(yàn)證了CB-SCA的性能。圖5顯示了CB-SCA與典型的隨機(jī)父節(jié)點(diǎn)選擇算法、最小節(jié)點(diǎn)負(fù)載優(yōu)先的貪心算法以及MC-SCA相比其節(jié)點(diǎn)最大廣播負(fù)載值分別平均降低了48.69%、10.64%和65.21%，因此CB-SCA具有更好的廣播能量公平性。無論N和T如何變化，CB-SCA性能明顯優(yōu)于隨機(jī)父節(jié)點(diǎn)選擇算法和MC-SCA，這是因?yàn)楹髢煞N算法在設(shè)計過程中并沒有考慮節(jié)點(diǎn)負(fù)載的均衡性。同時也發(fā)現(xiàn)CB-SCA在負(fù)載均衡性能上稍微優(yōu)于最小節(jié)點(diǎn)負(fù)載優(yōu)先的貪心算法，這兩個算法在設(shè)計過程中都考慮了節(jié)點(diǎn)負(fù)載的均衡性，不同的是CB-SCA在貪心準(zhǔn)則中除了考慮節(jié)點(diǎn)轉(zhuǎn)發(fā)能耗負(fù)載外，還考慮了新增的覆蓋節(jié)點(diǎn)數(shù)量，每輪迭代選擇帶來更多新增覆蓋節(jié)點(diǎn)數(shù)量的轉(zhuǎn)發(fā)行為能夠一定程度上減少迭代輪數(shù)，從而可能對節(jié)點(diǎn)最大廣播能量負(fù)載性能產(chǎn)生有利的影響。圖5顯示CB-SCA方法性能要優(yōu)于最小節(jié)點(diǎn)負(fù)載優(yōu)先的貪心算法，盡管如此，其性能優(yōu)勢并不是很明顯。隨著N的減小以及T的增加，相鄰節(jié)點(diǎn)工作調(diào)度中活動時隙發(fā)生重疊的概率變得更小，且重疊的活動時隙數(shù)量期望變得更少，這意味著對于本文方法而言，新增覆蓋節(jié)點(diǎn)數(shù)量在貪心準(zhǔn)則中的作用變得越來越小，這將使得CB-SCA和最小節(jié)點(diǎn)負(fù)載優(yōu)先的貪心算法的性能變得更加接近。

此外，還進(jìn)一步驗(yàn)證了CB-SCA和最小節(jié)點(diǎn)負(fù)載優(yōu)先的貪心算法在廣播總能耗性能上的比較。圖6顯示CB-SCA始終能夠獲得比基準(zhǔn)方法更好的廣播總能耗性能，尤其是隨著N的增加以及T的減小，其性能優(yōu)勢更加明顯，這是因?yàn)橄噜徆?jié)點(diǎn)間更多重疊的活動時隙數(shù)量會使得新增覆蓋節(jié)點(diǎn)數(shù)量在貪心準(zhǔn)則中的作用變得更大，這在一定程度上能夠減少迭代輪數(shù)，從而帶來更好的廣播總能耗性能。由此可見，無論是對于節(jié)點(diǎn)廣播負(fù)載均衡性能還是對于廣播總能耗性能而言，既考慮節(jié)點(diǎn)轉(zhuǎn)發(fā)能耗負(fù)載又考慮新增覆蓋節(jié)點(diǎn)數(shù)量的貪心準(zhǔn)則始終都要優(yōu)于僅考慮節(jié)點(diǎn)轉(zhuǎn)發(fā)能耗負(fù)載的貪心準(zhǔn)則。

圖5 節(jié)點(diǎn)最大廣播能量負(fù)載隨著N和T變化時的性能比較

圖6 兩種面向負(fù)載均衡算法的廣播總能耗 隨著N和T變化時的性能比較

4 結(jié)語

本文主要研究了占空比傳感網(wǎng)中最小端到端延遲約束下的廣播調(diào)度能效優(yōu)化問題，并且分別從總能量消耗和負(fù)載均衡性兩個方面來刻畫廣播調(diào)度的能效。首先, 研究了最小延遲約束最小能量廣播問題，通過構(gòu)造時空狀態(tài)圖將其建模成最小代價轉(zhuǎn)發(fā)行為子集覆蓋問題，同時證明了該問題等價于經(jīng)典的最小加權(quán)集合覆蓋問題; 隨后, 研究了最小延遲約束負(fù)載均衡廣播問題，通過將其建模成代價均衡轉(zhuǎn)發(fā)行為子集覆蓋問題，提出了一個高效的貪心算法解決該問題; 最終, 通過仿真實(shí)驗(yàn)驗(yàn)證了所提出算法的高效性。盡管如此，本文還存在一些不足之處，例如假設(shè)了鏈路質(zhì)量是完全可靠的并且提出的算法是集中式的，如何在鏈路質(zhì)量不可靠的網(wǎng)絡(luò)中設(shè)計高效的分布式廣播算法將是未來計劃研究的方向。