文獻(xiàn)標(biāo)識(shí)碼: A
文章編號(hào): 0258-7998(2015)02-0127-04
0 引言
水下傳感器網(wǎng)絡(luò)(UWSNs)[1]由通過(guò)聲音鏈路進(jìn)行通信的大量水上和水下傳感器組成。在該網(wǎng)絡(luò)中,,傳感器節(jié)點(diǎn)的主要通信模式是利用聲音調(diào)制解調(diào)器向岸上的數(shù)據(jù)采集基站發(fā)送數(shù)據(jù)[2-4],。這種模式中報(bào)文只要生成便能發(fā)送,因此數(shù)據(jù)傳輸的延時(shí)較低,。然而,,這種通信模式的BER較高,且通信帶寬不到10 kb/s,。為此,,傳感器節(jié)點(diǎn)只能通過(guò)聲學(xué)鏈路發(fā)送被采集數(shù)據(jù)的數(shù)據(jù)摘要。另一種通信方法就是使用自主式水下航行器(AUV)[5]。AUV航行器訪問(wèn)節(jié)點(diǎn),,通過(guò)高速短距離光學(xué)通信下載數(shù)據(jù),。最后,AUV航行器周期性地浮出水面,,通過(guò)無(wú)線通信把數(shù)據(jù)傳輸給陸地基站來(lái)下載采集到的數(shù)據(jù),。這種場(chǎng)景的示意圖見(jiàn)圖1。
實(shí)踐證明[6-7],,傳感器節(jié)點(diǎn)采集到的信息的規(guī)模,、價(jià)值和優(yōu)先級(jí)有很大區(qū)別。人們很難預(yù)測(cè)何時(shí)何地將會(huì)發(fā)生重大事件,,哪些節(jié)點(diǎn)能夠檢測(cè)到這些事件,。而傳感信息的原始價(jià)值會(huì)隨著時(shí)間的推移不斷下降,因此應(yīng)該將數(shù)據(jù)盡快傳輸給陸地基站和最終用戶,。數(shù)據(jù)到達(dá)用戶的時(shí)間越晚,,數(shù)據(jù)的價(jià)值越低。所以,,每個(gè)傳感器節(jié)點(diǎn)必須確定采集到的數(shù)據(jù)塊中的次要數(shù)據(jù)(比如較低分辨率的鏈路或照片)何時(shí)通過(guò)聲學(xué)鏈路發(fā)送給陸地基站,,以及該數(shù)據(jù)塊中的哪些主干部分應(yīng)該優(yōu)先傳輸。
本文針對(duì)水下傳感器獲得的數(shù)據(jù)塊信息價(jià)值(VoI)提出多種調(diào)度算法,,對(duì)聲學(xué)傳輸調(diào)度策略的復(fù)雜性問(wèn)題進(jìn)行研究,,并設(shè)計(jì)了不同傳感器調(diào)度策略以確定何時(shí)通過(guò)聲學(xué)路由傳輸哪些數(shù)據(jù)。本文總體目標(biāo)是設(shè)計(jì)合適的調(diào)度策略使傳輸給陸地基站的數(shù)據(jù)信息價(jià)值最大,。最后,,基于真實(shí)場(chǎng)景的仿真研究表明了本文方案的有效性。
1 UWSN的信息價(jià)值
1.1 相關(guān)定義
假設(shè)某一傳感器節(jié)點(diǎn)記錄的數(shù)據(jù)收集于尺寸為|D|的數(shù)據(jù)塊D內(nèi),。tr(D)表示數(shù)據(jù)塊的創(chuàng)建時(shí)間,。直觀來(lái)講,數(shù)據(jù)塊中的信息是指該次之前的觀測(cè)數(shù)據(jù),?!谋硎舅锌赡艿臄?shù)據(jù)塊組成的集合。
尺寸為b的主干數(shù)據(jù)dig(D,,b)是數(shù)據(jù)塊D中的部分?jǐn)?shù)據(jù),。當(dāng)b>|D|時(shí),假設(shè)主干數(shù)據(jù)為初始數(shù)據(jù)塊本身,。
用V(D,,t)表示陸地基站(客戶)在時(shí)間t時(shí)接收到的數(shù)據(jù)塊D的信息價(jià)值(VoI)。將信息價(jià)值與客戶采取的行動(dòng)的價(jià)值V(a)關(guān)聯(lián)起來(lái),,進(jìn)而得到信息價(jià)值的實(shí)際定義,。
定義1:信息價(jià)值V(D,,t)表示客戶在知道了D這一必備信息后根據(jù)客戶策略采取的所有行動(dòng)ai的價(jià)值之和:
定義2:有條件信息價(jià)值V(D,t|(D1,,t1)…(Dk,,tk))表示在之前時(shí)間ti接收到數(shù)據(jù)塊Di后,在時(shí)間t時(shí)接收到數(shù)據(jù)塊D的價(jià)值,。
1.2 信息價(jià)值的形式
本文希望找到時(shí)間t時(shí)主干數(shù)據(jù)dig(D,b)的信息價(jià)值的閉型表達(dá)式,。該價(jià)值將會(huì)低于初始價(jià)值V(D,,tr),一方面是因?yàn)樾畔⒌木o迫性使得信息價(jià)值隨著時(shí)間遞減,,另一方面是因?yàn)樾畔⒌目筛爬ㄐ裕枋鰯?shù)據(jù)被主干數(shù)據(jù)替代后信息價(jià)值如何減弱),。下文始終假設(shè)信息的緊迫性和可概括性互相獨(dú)立。這是因?yàn)?,信息的緊迫性取決于觀察現(xiàn)象的含義(被觀察到的真實(shí)事件),,而數(shù)據(jù)塊的可概括性主要取決于數(shù)據(jù)結(jié)構(gòu)。根據(jù)這一假設(shè),,可以將信息價(jià)值表述為如下形式:
其中,,dd表示主干數(shù)據(jù)價(jià)值衰減函數(shù),dt表示時(shí)間價(jià)值衰減函數(shù),。不失一般性,,本文將dd定義為主干數(shù)據(jù)尺寸和初始數(shù)據(jù)塊尺寸之比,而將tr定義為數(shù)據(jù)采集的時(shí)間,。
本文認(rèn)為數(shù)據(jù)塊的信息價(jià)值內(nèi)容由初始價(jià)值,、主干數(shù)據(jù)價(jià)值衰減函數(shù)和時(shí)間價(jià)值衰減函數(shù)三元組構(gòu)成。使用一種指數(shù)衰減模型來(lái)模擬時(shí)間價(jià)值衰減函數(shù):
dt(t-t0)=exp(Ptd·(t-t0))(3)
其中,,Ptd表示時(shí)間衰減參數(shù),。尤其地,Ptd=0表示信息對(duì)延時(shí)不敏感,,Ptd>>0表示信息衰減的速度很快,。
1.3 有條件信息價(jià)值
直觀來(lái)講,有條件信息價(jià)值表示假設(shè)之前已經(jīng)接收到小規(guī)模主干數(shù)據(jù)后,,新主干數(shù)據(jù)提供的新信息,。如果在同一時(shí)刻接收到所有主干數(shù)據(jù),則結(jié)果就是實(shí)現(xiàn)的兩個(gè)價(jià)值之差,。然而,,因?yàn)樾∫?guī)模主干數(shù)據(jù)的接收時(shí)間較早,不是與它們的到達(dá)時(shí)間價(jià)值相減,,而是與它們?cè)诋?dāng)前時(shí)間的價(jià)值相減,。有條件信息價(jià)值表示為:
V(dig(D,,b2),t2|(dig(D,,b1),,t1))
=V(dig(D,b2),,t2)-V(dig(D,,b1),t2)(4)
2 傳輸調(diào)度算法
對(duì)所有傳感器節(jié)點(diǎn)持續(xù)進(jìn)行觀察,,并在具體的時(shí)間點(diǎn)記錄觀察數(shù)據(jù)(D1,,t1),…,,(Di,,ti)。假設(shè)傳感器節(jié)點(diǎn)沒(méi)有內(nèi)存約束,,可以存儲(chǔ)所有觀察數(shù)據(jù)直到AUV航行器到達(dá),。傳感器節(jié)點(diǎn)使用聲學(xué)解調(diào)器傳輸它們采集的數(shù)據(jù)塊主干數(shù)據(jù)。當(dāng)AUV航行器訪問(wèn)傳感器節(jié)點(diǎn)時(shí),,節(jié)點(diǎn)把從上次AUV航行器訪問(wèn)迄今的所有數(shù)據(jù)塊傳輸給AUV航行器(光學(xué)傳輸),。每當(dāng)完成一次傳輸時(shí),節(jié)點(diǎn)必須調(diào)度一個(gè)新的主干數(shù)據(jù)用于傳輸,。確定傳輸哪個(gè)主干數(shù)據(jù)及傳輸時(shí)間,,決定了陸地基站接收到的信息價(jià)值。設(shè)計(jì)調(diào)度算法的總體目標(biāo)是使傳輸數(shù)據(jù)的總體信息價(jià)值最大化,。本節(jié)首先研究利用聲學(xué)鏈路進(jìn)行主干數(shù)據(jù)傳輸調(diào)度的計(jì)算復(fù)雜性,,然后給出問(wèn)題的啟發(fā)式求解方法。
2.1 調(diào)度復(fù)雜度
假設(shè)有一個(gè)由數(shù)據(jù)塊,、時(shí)間和信息價(jià)值內(nèi)容組成的靜態(tài)集合{(D1,,t1,P1),,…,,(Dn,tn,,Pn)}及一個(gè)時(shí)間段[ts,,td]。在td之后不會(huì)記錄任何新的主干數(shù)據(jù),,在ts之前也不會(huì)傳輸任何數(shù)據(jù)塊或主干數(shù)據(jù),。假設(shè)節(jié)點(diǎn)統(tǒng)一通過(guò)帶寬B進(jìn)行數(shù)據(jù)傳輸。
文中需要解決的調(diào)度問(wèn)題實(shí)際上就是確定一種調(diào)度策略,,即一個(gè)有序元組序列S={(ji,,bi)},,使聲學(xué)鏈路上進(jìn)行的第i次傳輸?shù)葍r(jià)于在下述時(shí)間傳輸數(shù)據(jù)dig(D,bi):
實(shí)現(xiàn)傳輸?shù)目傮w信息價(jià)值最大化的公式如下:
其中,,i表示在先前調(diào)度策略S中傳輸?shù)闹鞲蓴?shù)據(jù)D,。
屬性:調(diào)度問(wèn)題是NP難題。
證明:假設(shè)問(wèn)題不是NP難題,。眾所周知,,背包問(wèn)題的優(yōu)化問(wèn)題是NP難題[8]??梢詫⒈嘲鼏?wèn)題看成是所有主干數(shù)據(jù)價(jià)值為0且函數(shù)衰減參數(shù)也為0的特例(無(wú)時(shí)間衰減),。因此,可在多項(xiàng)式時(shí)間內(nèi)求解調(diào)度問(wèn)題的算法也將可以求解背包問(wèn)題,,這于假設(shè)矛盾,命題得證,。
上述問(wèn)題的計(jì)算成本很高,,所以在數(shù)據(jù)塊不斷生成的條件下對(duì)主干數(shù)據(jù)進(jìn)行傳輸調(diào)度也將導(dǎo)致較高計(jì)算成本。下文將定義3種可行的傳輸調(diào)度啟發(fā)式算法,。
2.2 調(diào)度算法1:只利用AUV航行器(AUVO)
只通過(guò)AUV航行器不斷浮上水面來(lái)將數(shù)據(jù)傳輸給陸地基站,,該種啟發(fā)式策略(AUVO)作為可以使用聲學(xué)調(diào)制解調(diào)器和多跳水下路由的其他策略的基準(zhǔn)策略。在AUVO中,,用戶接收到的信息價(jià)值即是AUV接收到數(shù)據(jù)時(shí)的數(shù)據(jù)塊信息價(jià)值,。研究發(fā)現(xiàn),通過(guò)使用聲學(xué)路由在AUV航行器傳遞數(shù)據(jù)前成功傳輸數(shù)據(jù)塊的策略可以提高被采集數(shù)據(jù)的信息價(jià)值,。AUVO在實(shí)踐中也具有顯著優(yōu)勢(shì),。例如,傳感器節(jié)點(diǎn)無(wú)需配備昂貴的聲學(xué)調(diào)制解調(diào)器(每個(gè)上千美元),,因此成本更低,;傳感器節(jié)點(diǎn)的電池壽命更長(zhǎng),因?yàn)槁晫W(xué)傳輸非常消耗能量,;最后,,節(jié)點(diǎn)的協(xié)議棧更為簡(jiǎn)單,因?yàn)樵谕ㄐ艜r(shí)通過(guò)單跳光學(xué)鏈路下載數(shù)據(jù),,無(wú)需水下MAC和路由功能,。
2.3 調(diào)度算法2:漸進(jìn)式數(shù)據(jù)摘要調(diào)度(UPD)
在該策略下,傳感器節(jié)點(diǎn)無(wú)法對(duì)數(shù)據(jù)塊的信息價(jià)值內(nèi)容進(jìn)行本地評(píng)估,。然而,,它既知道dt函數(shù)的形狀,又知道可使信息價(jià)值的降低速度低于摘要規(guī)模的數(shù)據(jù)摘要步進(jìn)量,。由于節(jié)點(diǎn)只掌握了上述信息,,所以節(jié)點(diǎn)的最優(yōu)選擇就是在任意給定時(shí)刻發(fā)送手頭最小的數(shù)據(jù)摘要,,然后是更大一些(增加了步進(jìn)量)的數(shù)據(jù)摘要,依次類(lèi)推,,通過(guò)到達(dá)時(shí)間來(lái)破除關(guān)聯(lián)(tie),。此時(shí)的調(diào)度算法如下:
list:={};
When AUV到達(dá) do
將列表中所有完整的數(shù)據(jù)塊發(fā)送給AUV,;
list:={},;
End
When 采集了數(shù)據(jù)塊D do
對(duì)所有b創(chuàng)建數(shù)據(jù)摘要dig(D,b),;
list:=list∪digests∪D
End
When 當(dāng)前傳輸任務(wù)完成 do
list:=按照尺寸排序的列表,;
current-transmission=list[0];
list:=list[1:end],;
end
2.4 啟發(fā)式算法3:基于貪婪的平均信息價(jià)值(GAVI)調(diào)度
該策略假設(shè)節(jié)點(diǎn)可以確定被感知的數(shù)據(jù)塊的價(jià)值情況,。利用這一信息,該策略可貪婪地實(shí)現(xiàn)傳輸數(shù)據(jù)的平均信息價(jià)值最大化,。依次調(diào)度數(shù)據(jù)傳輸,,于是下次傳輸將是單位時(shí)間的信息價(jià)值量最大的傳輸。這里的信息價(jià)值是考慮了之前相同數(shù)據(jù)塊傳輸?shù)挠袟l件信息價(jià)值,。對(duì)于靜態(tài)數(shù)據(jù)塊集合,,該策略實(shí)際上是個(gè)最優(yōu)策略。然而,,對(duì)于不斷接收到新數(shù)據(jù)塊的節(jié)點(diǎn)來(lái)說(shuō),,一個(gè)新的價(jià)值更高的數(shù)據(jù)摘要可能因?yàn)楦L(zhǎng)的數(shù)據(jù)塊當(dāng)前正在傳輸而需等待一段時(shí)間。該算法如下:
list:={},;
When AUV到達(dá) do
將列表中所有完整的數(shù)據(jù)塊發(fā)送給AUV,;
list:={};
End
When 采集了數(shù)據(jù)塊D do
為所有b創(chuàng)建數(shù)據(jù)摘要dig(D,,b),;
list:=list∪digests∪D;
End
When 當(dāng)前傳輸任務(wù)結(jié)束 do
t=current time,;
For 列表中的每個(gè)數(shù)據(jù)摘要d do
估計(jì)V:=V(d,,t);
估計(jì)ttrans(d):=size(d)/帶寬,;
Vavg(d,,t):=V/ttrans(d);
End
list:=根據(jù)Vavg(d,,t)排序的列表,;
current-transmission=list[0];
list:=list[1:end],;
End
3 仿真實(shí)驗(yàn)
假設(shè)網(wǎng)絡(luò)在面積為6×7 km2的海床上部署40個(gè)傳感器節(jié)點(diǎn),,節(jié)點(diǎn)間距1 500 m,。每個(gè)節(jié)點(diǎn)配備一個(gè)聲學(xué)解調(diào)器。節(jié)點(diǎn)和陸地基站間的平均傳輸率為10 kb/s,。AUV航行器為Odyssey-IV系列航行器,,航行速度為1.8 m/s[2]。于是,,AUV航行器需要13 min左右從一個(gè)節(jié)點(diǎn)到達(dá)另一個(gè)節(jié)點(diǎn),。當(dāng)AUV與傳感器節(jié)點(diǎn)相距不到100 m(清晰的水下通信)時(shí),光學(xué)傳輸?shù)乃俾士蛇_(dá)10 Mb/s[9],。航行器如果要下載傳感器在一天內(nèi)采集的1.1 GB數(shù)據(jù),,需要在傳感器周?chē)鷾艏s13 min[10]。于是,,AUV在一天內(nèi)可以按照固定次序訪問(wèn)40個(gè)節(jié)點(diǎn),,然后回到船塢加載燃料、下載數(shù)據(jù),。
本文的模擬場(chǎng)景是,,傳感器使用攝像機(jī)拍攝部署區(qū)域的視頻,以進(jìn)行入侵檢測(cè),。傳感器節(jié)點(diǎn)以720p的高分辨率來(lái)存儲(chǔ)監(jiān)測(cè)數(shù)據(jù)(1 280×720像素分辨率,29.97幀/s),。錄像被分割為1 min視頻大小的數(shù)據(jù)塊,。假設(shè)視頻基于標(biāo)準(zhǔn)的H.264編解碼器進(jìn)行編碼??紤]4種類(lèi)型的數(shù)據(jù)摘要,,每種表示一種或數(shù)種從關(guān)鍵的視頻幀中提取出來(lái)的圖像,并用WEBP編解碼器進(jìn)行編碼,。首先就能對(duì)從各個(gè)圖像中提取出來(lái)的信息量和這些信息對(duì)用戶的有用度做出主觀判斷,,然后為這些數(shù)據(jù)分配摘要價(jià)值dd。表1列出了這些價(jià)值及其他參數(shù)的數(shù)值,。
為了確定數(shù)據(jù)塊的價(jià)值,,本文將其分為3種觀測(cè)類(lèi)別C1、C2和C3,,每種類(lèi)別有不同的緊迫性和基本信息價(jià)值水平,,如表2所示。觀測(cè)類(lèi)別的分布不遵守均勻隨機(jī)分布:例如,,入侵者很有可能在傳感器覆蓋的范圍內(nèi)滯留1 min以上,。因此,使用圖2中給出的馬爾科夫鏈來(lái)模擬觀測(cè)數(shù)據(jù)分布,。假設(shè)在大多數(shù)時(shí)間內(nèi),,系統(tǒng)的觀測(cè)事件均是非重要事件(C1),。事件的發(fā)生概率為PE。這些事件中有部分事件(比例為HEF)的優(yōu)先級(jí)較高,。自我躍遷Plst和Phst確定事件的平均長(zhǎng)度,。
在本文實(shí)驗(yàn)中,改變信息價(jià)值最高的事件比例HEF,,并且運(yùn)行3種啟發(fā)式算法AUVO,、UPD和GAVI。對(duì)每種設(shè)置,,使用不同的隨機(jī)種子生成10個(gè)場(chǎng)景然后取均值,,實(shí)驗(yàn)結(jié)果見(jiàn)圖3。
圖3(a)給出了HEF取不同值時(shí)陸地基站接收到的總體信息價(jià)值情況,。如預(yù)期,,當(dāng)HEF上升時(shí)優(yōu)先級(jí)較高的事件的基本信息價(jià)值較高,所以各啟發(fā)式算法的信息價(jià)值量均有上升,。沒(méi)有進(jìn)行聲學(xué)傳輸?shù)腁UVO策略的信息價(jià)值最低,,而GAVI策略利用了各數(shù)據(jù)摘要的本地信息價(jià)值,所以總體信息價(jià)值量最高,。
本文根據(jù)數(shù)據(jù)到達(dá)陸地基站的方式研究了信息價(jià)值的構(gòu)成,。圖3(b)和3(c)給出了UPD和GAVI實(shí)現(xiàn)的信息價(jià)值的構(gòu)成??傮w信息價(jià)值曲線與圖3(a)相同,。該數(shù)值是通過(guò)聲學(xué)路由傳輸?shù)男畔r(jià)值和AUV實(shí)現(xiàn)的有條件信息價(jià)值之和。請(qǐng)注意,,AUV在兩種情況下傳輸?shù)模o(wú)條件)信息價(jià)值相同(即圖3(a)中AUVO的價(jià)值),。研究UPD的性能曲線,發(fā)現(xiàn)當(dāng)HEF較低時(shí)UPD和AUVO策略之所以比較接近,,并不是因?yàn)橥ㄟ^(guò)聲學(xué)鏈路傳輸?shù)膬r(jià)值較低,,而是因?yàn)锳UV航行器攜帶的無(wú)條件價(jià)值與有條件價(jià)值之間的落差完全掩蓋了這種增益。當(dāng)攜帶的大多數(shù)數(shù)據(jù)不夠緊急時(shí)更是如此,。相反,,GAVI維護(hù)了這種增益,根據(jù)信息價(jià)值情況智能化選擇聲學(xué)傳輸內(nèi)容,,于是通過(guò)聲學(xué)路由傳輸高信息價(jià)值的數(shù)據(jù)的時(shí)間提前,。
4 總結(jié)
本文研究了UWSN下的信息價(jià)值傳輸調(diào)度算法。具體來(lái)說(shuō),,證明了當(dāng)節(jié)點(diǎn)可以通過(guò)多跳聲學(xué)路由傳輸數(shù)據(jù)并將數(shù)據(jù)傳輸給過(guò)往的AUV航行器時(shí),,制定合適的調(diào)度策略可以使傳感器節(jié)點(diǎn)通過(guò)聲學(xué)技術(shù)傳輸傳感數(shù)據(jù)的數(shù)據(jù)摘要,進(jìn)而實(shí)現(xiàn)傳遞給用戶的信息價(jià)值最大化。下一步將研究一個(gè)和多個(gè)AUV航行器的線路規(guī)劃問(wèn)題,,以實(shí)現(xiàn)信息價(jià)值最大化,,同時(shí)全面評(píng)估不同方法的性能。
參考文獻(xiàn)
[1] 郭忠文,,羅漢江,,洪鋒,等.水下無(wú)線傳感器網(wǎng)絡(luò)的研究進(jìn)展[J].計(jì)算機(jī)研究與發(fā)展,,2010,,47(3):377-389.
[2] 劉亞,劉功亮,,康文靜.壓縮感知和LEACH結(jié)合的水下傳感器網(wǎng)絡(luò)信息采集方案[J].傳感技術(shù)學(xué)報(bào),,2013,26(3):388-395.
[3] 洪璐.水下傳感器網(wǎng)絡(luò)高效數(shù)據(jù)傳輸協(xié)議研究[D].青島:中國(guó)海洋大學(xué),,2011.
[4] 劉玉梁,,潘仲明.水下無(wú)線傳感器網(wǎng)絡(luò)能量路由協(xié)議的仿真研究[J].傳感技術(shù)學(xué)報(bào),2011,,24(6):905-908.
[5] ESKESEN J,,OWENS D,SOROKA M,,et al.Design andperformance of Odyssey IV:a deep ocean hover-capableAUV[J].jge,,2009,617:253-3438.
[6] KULHANDJIAN H,,MELODIA T,,KOUTSONIKOLAS D.CDMA-based analog network coding through interferencecancellation for underwater acoustic sensor networks[C].Proceedings of the Seventh ACM International Conference onUnderwater Networks and Systems.ACM,2012:7-16.
[7] HEIDEMANN J,,STOJANOVIC M,ZORZI M.Underwatersensor networks: applications,,advances and challenges[J].Philosophical Transactions of the Royal Society A:Mathe-matical,,Physical and Engineering Sciences,2012,,370(1958):158-175.
[8] 陶新民,,付丹丹,劉玉,,等.雙尺度變異離散粒子群算法求解背包問(wèn)題[J].系統(tǒng)仿真學(xué)報(bào),,2013,25(1):12-17.
[9] FARR N,,BOWEN A,,WARE J,et al.An integrated, under-water optical/acoustic communications system[C].OCEANS2010 IEEE-Sydney.IEEE,2010:1-6.
[10] DUNBABIN M,,CORKE P,,VASILESCU I,et al.Datamuling over underwater wireless sensor networks using anautonomous underwater vehicle[C].Robotics and Automa-tion,,2006.ICRA 2006.Proceedings 2006 IEEE InternationalConference on.IEEE,,2006:2091-2098.