0 引言

　　水下傳感器網(wǎng)絡(luò)(UWSNs)[1]由通過聲音鏈路進(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)只能通過聲學(xué)鏈路發(fā)送被采集數(shù)據(jù)的數(shù)據(jù)摘要。另一種通信方法就是使用自主式水下航行器(AUV)[5]。AUV航行器訪問節(jié)點(diǎn)，通過高速短距離光學(xué)通信下載數(shù)據(jù)。最后，AUV航行器周期性地浮出水面，通過無線通信把數(shù)據(jù)傳輸給陸地基站來下載采集到的數(shù)據(jù)。這種場景的示意圖見圖1。

　　實(shí)踐證明[6-7]，傳感器節(jié)點(diǎn)采集到的信息的規(guī)模、價(jià)值和優(yōu)先級有很大區(qū)別。人們很難預(yù)測何時(shí)何地將會(huì)發(fā)生重大事件，哪些節(jié)點(diǎn)能夠檢測到這些事件。而傳感信息的原始價(jià)值會(huì)隨著時(shí)間的推移不斷下降，因此應(yīng)該將數(shù)據(jù)盡快傳輸給陸地基站和最終用戶。數(shù)據(jù)到達(dá)用戶的時(shí)間越晚，數(shù)據(jù)的價(jià)值越低。所以，每個(gè)傳感器節(jié)點(diǎn)必須確定采集到的數(shù)據(jù)塊中的次要數(shù)據(jù)（比如較低分辨率的鏈路或照片）何時(shí)通過聲學(xué)鏈路發(fā)送給陸地基站，以及該數(shù)據(jù)塊中的哪些主干部分應(yīng)該優(yōu)先傳輸。

　　本文針對水下傳感器獲得的數(shù)據(jù)塊信息價(jià)值(VoI)提出多種調(diào)度算法，對聲學(xué)傳輸調(diào)度策略的復(fù)雜性問題進(jìn)行研究，并設(shè)計(jì)了不同傳感器調(diào)度策略以確定何時(shí)通過聲學(xué)路由傳輸哪些數(shù)據(jù)。本文總體目標(biāo)是設(shè)計(jì)合適的調(diào)度策略使傳輸給陸地基站的數(shù)據(jù)信息價(jià)值最大。最后，基于真實(shí)場景的仿真研究表明了本文方案的有效性。

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í)間。直觀來講，數(shù)據(jù)塊中的信息是指該次之前的觀測數(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)起來，進(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)椋畔⒌木o迫性取決于觀察現(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ù)衰減模型來模擬時(shí)間價(jià)值衰減函數(shù)：

　　dt(t-t0)=exp(Ptd·(t-t0))(3)

　　其中，Ptd表示時(shí)間衰減參數(shù)。尤其地，Ptd=0表示信息對延時(shí)不敏感，Ptd>>0表示信息衰減的速度很快。

　　1.3 有條件信息價(jià)值

　　直觀來講，有條件信息價(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à)值相減，而是與它們在當(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)度算法

　　對所有傳感器節(jié)點(diǎn)持續(xù)進(jìn)行觀察，并在具體的時(shí)間點(diǎn)記錄觀察數(shù)據(jù)(D1，t1)，…，(Di，ti)。假設(shè)傳感器節(jié)點(diǎn)沒有內(nèi)存約束，可以存儲(chǔ)所有觀察數(shù)據(jù)直到AUV航行器到達(dá)。傳感器節(jié)點(diǎn)使用聲學(xué)解調(diào)器傳輸它們采集的數(shù)據(jù)塊主干數(shù)據(jù)。當(dāng)AUV航行器訪問傳感器節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)把從上次AUV航行器訪問迄今的所有數(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ù)雜性，然后給出問題的啟發(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)一通過帶寬B進(jìn)行數(shù)據(jù)傳輸。

　　文中需要解決的調(diào)度問題實(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)度問題是NP難題。

　　證明：假設(shè)問題不是NP難題。眾所周知，背包問題的優(yōu)化問題是NP難題[8]?？梢詫⒈嘲鼏栴}看成是所有主干數(shù)據(jù)價(jià)值為0且函數(shù)衰減參數(shù)也為0的特例（無時(shí)間衰減）。因此，可在多項(xiàng)式時(shí)間內(nèi)求解調(diào)度問題的算法也將可以求解背包問題，這于假設(shè)矛盾，命題得證。

　　上述問題的計(jì)算成本很高，所以在數(shù)據(jù)塊不斷生成的條件下對主干數(shù)據(jù)進(jìn)行傳輸調(diào)度也將導(dǎo)致較高計(jì)算成本。下文將定義3種可行的傳輸調(diào)度啟發(fā)式算法。

　　2.2 調(diào)度算法1：只利用AUV航行器(AUVO)

　　只通過AUV航行器不斷浮上水面來將數(shù)據(jù)傳輸給陸地基站，該種啟發(fā)式策略(AUVO)作為可以使用聲學(xué)調(diào)制解調(diào)器和多跳水下路由的其他策略的基準(zhǔn)策略。在AUVO中，用戶接收到的信息價(jià)值即是AUV接收到數(shù)據(jù)時(shí)的數(shù)據(jù)塊信息價(jià)值。研究發(fā)現(xiàn)，通過使用聲學(xué)路由在AUV航行器傳遞數(shù)據(jù)前成功傳輸數(shù)據(jù)塊的策略可以提高被采集數(shù)據(jù)的信息價(jià)值。AUVO在實(shí)踐中也具有顯著優(yōu)勢。例如，傳感器節(jié)點(diǎn)無需配備昂貴的聲學(xué)調(diào)制解調(diào)器（每個(gè)上千美元），因此成本更低；傳感器節(jié)點(diǎn)的電池壽命更長，因?yàn)槁晫W(xué)傳輸非常消耗能量；最后，節(jié)點(diǎn)的協(xié)議棧更為簡單，因?yàn)樵谕ㄐ艜r(shí)通過單跳光學(xué)鏈路下載數(shù)據(jù)，無需水下MAC和路由功能。

　　2.3 調(diào)度算法2：漸進(jìn)式數(shù)據(jù)摘要調(diào)度（UPD）

　　在該策略下，傳感器節(jié)點(diǎn)無法對數(shù)據(jù)塊的信息價(jià)值內(nèi)容進(jìn)行本地評估。然而，它既知道dt函數(shù)的形狀，又知道可使信息價(jià)值的降低速度低于摘要規(guī)模的數(shù)據(jù)摘要步進(jìn)量。由于節(jié)點(diǎn)只掌握了上述信息，所以節(jié)點(diǎn)的最優(yōu)選擇就是在任意給定時(shí)刻發(fā)送手頭最小的數(shù)據(jù)摘要，然后是更大一些（增加了步進(jìn)量）的數(shù)據(jù)摘要，依次類推，通過到達(dá)時(shí)間來破除關(guān)聯(lián)(tie)。此時(shí)的調(diào)度算法如下：

　　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ù)完成 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à)值。對于靜態(tài)數(shù)據(jù)塊集合，該策略實(shí)際上是個(gè)最優(yōu)策略。然而，對于不斷接收到新數(shù)據(jù)塊的節(jié)點(diǎn)來說，一個(gè)新的價(jià)值更高的數(shù)據(jù)摘要可能因?yàn)楦L的數(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ù)，需要在傳感器周圍滯留約13 min[10]。于是，AUV在一天內(nèi)可以按照固定次序訪問40個(gè)節(jié)點(diǎn)，然后回到船塢加載燃料、下載數(shù)據(jù)。

　　本文的模擬場景是，傳感器使用攝像機(jī)拍攝部署區(qū)域的視頻，以進(jìn)行入侵檢測。傳感器節(jié)點(diǎn)以720p的高分辨率來存儲(chǔ)監(jiān)測數(shù)據(jù)(1 280×720像素分辨率，29.97幀/s)。錄像被分割為1 min視頻大小的數(shù)據(jù)塊。假設(shè)視頻基于標(biāo)準(zhǔn)的H.264編解碼器進(jìn)行編碼。考慮4種類型的數(shù)據(jù)摘要，每種表示一種或數(shù)種從關(guān)鍵的視頻幀中提取出來的圖像，并用WEBP編解碼器進(jìn)行編碼。首先就能對從各個(gè)圖像中提取出來的信息量和這些信息對用戶的有用度做出主觀判斷，然后為這些數(shù)據(jù)分配摘要價(jià)值dd。表1列出了這些價(jià)值及其他參數(shù)的數(shù)值。

　　為了確定數(shù)據(jù)塊的價(jià)值，本文將其分為3種觀測類別C1、C2和C3，每種類別有不同的緊迫性和基本信息價(jià)值水平，如表2所示。觀測類別的分布不遵守均勻隨機(jī)分布：例如，入侵者很有可能在傳感器覆蓋的范圍內(nèi)滯留1 min以上。因此，使用圖2中給出的馬爾科夫鏈來模擬觀測數(shù)據(jù)分布。假設(shè)在大多數(shù)時(shí)間內(nèi)，系統(tǒng)的觀測事件均是非重要事件(C1)。事件的發(fā)生概率為PE。這些事件中有部分事件（比例為HEF）的優(yōu)先級較高。自我躍遷Plst和Phst確定事件的平均長度。

　　在本文實(shí)驗(yàn)中，改變信息價(jià)值最高的事件比例HEF，并且運(yùn)行3種啟發(fā)式算法AUVO、UPD和GAVI。對每種設(shè)置，使用不同的隨機(jī)種子生成10個(gè)場景然后取均值，實(shí)驗(yàn)結(jié)果見圖3。

　　圖3(a)給出了HEF取不同值時(shí)陸地基站接收到的總體信息價(jià)值情況。如預(yù)期，當(dāng)HEF上升時(shí)優(yōu)先級較高的事件的基本信息價(jià)值較高，所以各啟發(fā)式算法的信息價(jià)值量均有上升。沒有進(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ù)值是通過聲學(xué)路由傳輸?shù)男畔r(jià)值和AUV實(shí)現(xiàn)的有條件信息價(jià)值之和。請注意，AUV在兩種情況下傳輸?shù)模o條件）信息價(jià)值相同（即圖3(a)中AUVO的價(jià)值）。研究UPD的性能曲線，發(fā)現(xiàn)當(dāng)HEF較低時(shí)UPD和AUVO策略之所以比較接近，并不是因?yàn)橥ㄟ^聲學(xué)鏈路傳輸?shù)膬r(jià)值較低，而是因?yàn)锳UV航行器攜帶的無條件價(jià)值與有條件價(jià)值之間的落差完全掩蓋了這種增益。當(dāng)攜帶的大多數(shù)數(shù)據(jù)不夠緊急時(shí)更是如此。相反，GAVI維護(hù)了這種增益，根據(jù)信息價(jià)值情況智能化選擇聲學(xué)傳輸內(nèi)容，于是通過聲學(xué)路由傳輸高信息價(jià)值的數(shù)據(jù)的時(shí)間提前。

4 總結(jié)

　　本文研究了UWSN下的信息價(jià)值傳輸調(diào)度算法。具體來說，證明了當(dāng)節(jié)點(diǎn)可以通過多跳聲學(xué)路由傳輸數(shù)據(jù)并將數(shù)據(jù)傳輸給過往的AUV航行器時(shí)，制定合適的調(diào)度策略可以使傳感器節(jié)點(diǎn)通過聲學(xué)技術(shù)傳輸傳感數(shù)據(jù)的數(shù)據(jù)摘要，進(jìn)而實(shí)現(xiàn)傳遞給用戶的信息價(jià)值最大化。下一步將研究一個(gè)和多個(gè)AUV航行器的線路規(guī)劃問題，以實(shí)現(xiàn)信息價(jià)值最大化，同時(shí)全面評估不同方法的性能。

　　參考文獻(xiàn)

　　[1] 郭忠文，羅漢江，洪鋒，等.水下無線傳感器網(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].青島：中國海洋大學(xué)，2011.

　　[4] 劉玉梁，潘仲明.水下無線傳感器網(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] 陶新民，付丹丹，劉玉，等.雙尺度變異離散粒子群算法求解背包問題[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.