徐力杰

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

0 引言

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

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

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

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

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

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

(1)

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

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

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

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

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

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

本文的目標是解決如下兩個問題：

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

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

2 解決方法

2.1 問題建模

(2)

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

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

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

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

(3)

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

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

圖2 網(wǎng)絡(luò)拓撲圖示例

根據(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ò)拓撲采用上述的方法，可以得到如圖3所示的時空狀態(tài)圖，其中包含了拓撲頂點{v0′,v1′,v2′,v3′,v4′,v5′}和狀態(tài)頂點{u1′,u2′,u3′,u4′,u5′,u6′,u7′}。在該示例中，只有節(jié)點v1的工作調(diào)度周期中包含了2個活動時隙，因此根據(jù)步驟1，分別構(gòu)造2個拓撲頂點v1′和v2′來代表節(jié)點v1，并且定義t′(v1′) = 3，t′(v2′) = 8。節(jié)點v0、v2、v3、v4則可以分別用拓撲頂點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ò)拓撲圖中廣播的時空特征。接下來，將在構(gòu)造的時空狀態(tài)圖Gs中找到一棵以代表了sink節(jié)點v0的拓撲頂點v0′為根的最短延遲權(quán)重胖樹(fat-tree)。本文采用一個類似于Dijkstra算法的方法可以很容易求得這樣一棵最短延遲權(quán)重胖樹。用ParentSet(Gs,v′)表示時空狀態(tài)圖Gs中任意非根頂點v′在最短延遲權(quán)重胖樹上的父頂點集合，并且用ParentSet(G,v)表示原始網(wǎng)絡(luò)拓撲圖G(j)=(V,E(j)) (j=1,2,…,m)中任意非根節(jié)點v在最短延遲路徑胖樹上的父節(jié)點集合，用node(v)表示時空狀態(tài)圖Gs中的任意拓撲頂點v所代表的原始網(wǎng)絡(luò)拓撲圖中的節(jié)點。進一步地，通過如下的方式根據(jù)時空狀態(tài)圖中的最短延遲權(quán)重胖樹得到原始網(wǎng)絡(luò)拓撲圖中的最短延遲路徑胖樹：對于任意非根節(jié)點vi∈V，用Su(vi)表示在時空狀態(tài)圖Gs里其空間狀態(tài)覆蓋了節(jié)點vi的所有狀態(tài)頂點中最短延遲值D*(·)最小的狀態(tài)頂點集合，不難得到vi的最優(yōu)父節(jié)點集合

(4)

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

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

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

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

(5)

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

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

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

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

(6)

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

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

由于問題4是文獻[16]中目標問題的一般化問題，且文獻[16]中的目標問題已經(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é)點v∈V的轉(zhuǎn)發(fā)能耗負載，并且初始地賦值為0。對于每個節(jié)點v∈V中的每個候選轉(zhuǎn)發(fā)行為f∈F(v)，用z(v,f)表示當選擇轉(zhuǎn)發(fā)行為f時節(jié)點v的轉(zhuǎn)發(fā)能耗負載與轉(zhuǎn)發(fā)行為f帶來的新增覆蓋節(jié)點數(shù)量的比值。在每一輪迭代中，將以z(v,f)為貪婪準則選擇z(v,f)值最小的轉(zhuǎn)發(fā)行為，這是因為較小的z(v,f)意味著較小的節(jié)點v的轉(zhuǎn)發(fā)能耗負載以及較多的新增覆蓋節(jié)點數(shù)量。直覺上，每輪迭代選擇一個使得對應(yīng)節(jié)點所產(chǎn)生的轉(zhuǎn)發(fā)能耗負載越小的轉(zhuǎn)發(fā)行為能夠使得最終所有節(jié)點產(chǎn)生的轉(zhuǎn)發(fā)能耗負載最大值越?。煌瑫r，每輪迭代選擇帶來更多新增覆蓋節(jié)點數(shù)量的轉(zhuǎn)發(fā)行為在直覺上也能夠減少迭代輪數(shù)，從而帶來更好的能耗性能。

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

證明 由于算法1的每輪迭代都會帶來一定新增的覆蓋節(jié)點且迭代的終止條件是所有的節(jié)點{v1,v2,…,vN-1}被覆蓋，因此很容易可知問題4的第2)個約束條件一定可以滿足。這里主要證明算法1的求解結(jié)果一定能夠滿足問題4的第1)個約束條件。在算法1的第6～10行，對節(jié)點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é)點v∈V的候選轉(zhuǎn)發(fā)行為集合F(v)，以及每個轉(zhuǎn)發(fā)行為f∈F(v)的能耗代價cost(v,f)和接收節(jié)點覆蓋范圍coverage(v,f)。

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

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。這里，所有的實驗結(jié)果均是運行20次所得結(jié)果的平均值。

為了便于進行性能比較，本文提出了如下的兩個基準方法：

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

2)最小節(jié)點負載優(yōu)先的貪心算法，該方法類似于算法1，唯一的不同在于對于貪心準則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和隨機父節(jié)點選擇算法的廣播總能耗性能。通過圖4可以發(fā)現(xiàn)MC-SCA與典型的隨機父節(jié)點選擇算法相比其廣播總能耗平均降低了24.23%，并且隨著節(jié)點數(shù)量的增多以及節(jié)點工作調(diào)度周期長度的減小，MC-SCA的性能優(yōu)勢會變得更加顯著，這是因為節(jié)點數(shù)量的增多和節(jié)點工作調(diào)度周期長度的減小會使得相鄰節(jié)點工作調(diào)度的活動時隙發(fā)生重疊的概率變得更高，且重疊數(shù)量的期望變得更大，這顯然對于本文使用的基于集合覆蓋的方法能夠帶來更大的性能提升空間。

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

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

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

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

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

4 結(jié)語

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