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

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

1 UWSN的信息價值

　　1.1 相關(guān)定義

　　假設(shè)某一傳感器節(jié)點(diǎn)記錄的數(shù)據(jù)收集于尺寸為|D|的數(shù)據(jù)塊D內(nèi)。tr(D)表示數(shù)據(jù)塊的創(chuàng)建時間。直觀來講，數(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ù)據(jù)為初始數(shù)據(jù)塊本身。

　　用V(D，t)表示陸地基站(客戶)在時間t時接收到的數(shù)據(jù)塊D的信息價值(VoI)。將信息價值與客戶采取的行動的價值V(a)關(guān)聯(lián)起來，進(jìn)而得到信息價值的實(shí)際定義。

　　定義1：信息價值V(D，t)表示客戶在知道了D這一必備信息后根據(jù)客戶策略采取的所有行動ai的價值之和：

　　定義2：有條件信息價值V(D，t|(D1，t1)…(Dk，tk))表示在之前時間ti接收到數(shù)據(jù)塊Di后，在時間t時接收到數(shù)據(jù)塊D的價值。

　　1.2 信息價值的形式

　　本文希望找到時間t時主干數(shù)據(jù)dig(D，b)的信息價值的閉型表達(dá)式。該價值將會低于初始價值V(D，tr)，一方面是因為信息的緊迫性使得信息價值隨著時間遞減，另一方面是因為信息的可概括性（描述數(shù)據(jù)被主干數(shù)據(jù)替代后信息價值如何減弱）。下文始終假設(shè)信息的緊迫性和可概括性互相獨(dú)立。這是因為，信息的緊迫性取決于觀察現(xiàn)象的含義（被觀察到的真實(shí)事件），而數(shù)據(jù)塊的可概括性主要取決于數(shù)據(jù)結(jié)構(gòu)。根據(jù)這一假設(shè)，可以將信息價值表述為如下形式：

　　其中，dd表示主干數(shù)據(jù)價值衰減函數(shù)，dt表示時間價值衰減函數(shù)。不失一般性，本文將dd定義為主干數(shù)據(jù)尺寸和初始數(shù)據(jù)塊尺寸之比，而將tr定義為數(shù)據(jù)采集的時間。

　　本文認(rèn)為數(shù)據(jù)塊的信息價值內(nèi)容由初始價值、主干數(shù)據(jù)價值衰減函數(shù)和時間價值衰減函數(shù)三元組構(gòu)成。使用一種指數(shù)衰減模型來模擬時間價值衰減函數(shù)：

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

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

　　1.3 有條件信息價值

　　直觀來講，有條件信息價值表示假設(shè)之前已經(jīng)接收到小規(guī)模主干數(shù)據(jù)后，新主干數(shù)據(jù)提供的新信息。如果在同一時刻接收到所有主干數(shù)據(jù)，則結(jié)果就是實(shí)現(xiàn)的兩個價值之差。然而，因為小規(guī)模主干數(shù)據(jù)的接收時間較早，不是與它們的到達(dá)時間價值相減，而是與它們在當(dāng)前時間的價值相減。有條件信息價值表示為：

　　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)行觀察，并在具體的時間點(diǎn)記錄觀察數(shù)據(jù)(D1，t1)，…，(Di，ti)。假設(shè)傳感器節(jié)點(diǎn)沒有內(nèi)存約束，可以存儲所有觀察數(shù)據(jù)直到AUV航行器到達(dá)。傳感器節(jié)點(diǎn)使用聲學(xué)解調(diào)器傳輸它們采集的數(shù)據(jù)塊主干數(shù)據(jù)。當(dāng)AUV航行器訪問傳感器節(jié)點(diǎn)時，節(jié)點(diǎn)把從上次AUV航行器訪問迄今的所有數(shù)據(jù)塊傳輸給AUV航行器（光學(xué)傳輸）。每當(dāng)完成一次傳輸時，節(jié)點(diǎn)必須調(diào)度一個新的主干數(shù)據(jù)用于傳輸。確定傳輸哪個主干數(shù)據(jù)及傳輸時間，決定了陸地基站接收到的信息價值。設(shè)計調(diào)度算法的總體目標(biāo)是使傳輸數(shù)據(jù)的總體信息價值最大化。本節(jié)首先研究利用聲學(xué)鏈路進(jìn)行主干數(shù)據(jù)傳輸調(diào)度的計算復(fù)雜性，然后給出問題的啟發(fā)式求解方法。

　　2.1 調(diào)度復(fù)雜度

　　假設(shè)有一個由數(shù)據(jù)塊、時間和信息價值內(nèi)容組成的靜態(tài)集合{(D1，t1，P1)，…，(Dn，tn，Pn)}及一個時間段[ts，td]。在td之后不會記錄任何新的主干數(shù)據(jù)，在ts之前也不會傳輸任何數(shù)據(jù)塊或主干數(shù)據(jù)。假設(shè)節(jié)點(diǎn)統(tǒng)一通過帶寬B進(jìn)行數(shù)據(jù)傳輸。

　　文中需要解決的調(diào)度問題實(shí)際上就是確定一種調(diào)度策略，即一個有序元組序列S={(ji，bi)}，使聲學(xué)鏈路上進(jìn)行的第i次傳輸?shù)葍r于在下述時間傳輸數(shù)據(jù)dig(D，bi)：

　　實(shí)現(xiàn)傳輸?shù)目傮w信息價值最大化的公式如下：

　　其中，i表示在先前調(diào)度策略S中傳輸?shù)闹鞲蓴?shù)據(jù)D。

　　屬性：調(diào)度問題是NP難題。

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

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

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

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

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

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

　　該策略假設(shè)節(jié)點(diǎn)可以確定被感知的數(shù)據(jù)塊的價值情況。利用這一信息，該策略可貪婪地實(shí)現(xiàn)傳輸數(shù)據(jù)的平均信息價值最大化。依次調(diào)度數(shù)據(jù)傳輸，于是下次傳輸將是單位時間的信息價值量最大的傳輸。這里的信息價值是考慮了之前相同數(shù)據(jù)塊傳輸?shù)挠袟l件信息價值。對于靜態(tài)數(shù)據(jù)塊集合，該策略實(shí)際上是個最優(yōu)策略。然而，對于不斷接收到新數(shù)據(jù)塊的節(jié)點(diǎn)來說，一個新的價值更高的數(shù)據(jù)摘要可能因為更長的數(shù)據(jù)塊當(dāng)前正在傳輸而需等待一段時間。該算法如下：

　　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 列表中的每個數(shù)據(jù)摘要d do

　　估計V:=V(d，t)；

　　估計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í)驗

　　假設(shè)網(wǎng)絡(luò)在面積為6×7 km2的海床上部署40個傳感器節(jié)點(diǎn)，節(jié)點(diǎn)間距1 500 m。每個節(jié)點(diǎn)配備一個聲學(xué)解調(diào)器。節(jié)點(diǎn)和陸地基站間的平均傳輸率為10 kb/s。AUV航行器為Odyssey-IV系列航行器，航行速度為1.8 m/s[2]。于是，AUV航行器需要13 min左右從一個節(jié)點(diǎn)到達(dá)另一個節(jié)點(diǎn)。當(dāng)AUV與傳感器節(jié)點(diǎn)相距不到100 m（清晰的水下通信）時，光學(xué)傳輸?shù)乃俾士蛇_(dá)10 Mb/s[9]。航行器如果要下載傳感器在一天內(nèi)采集的1.1 GB數(shù)據(jù)，需要在傳感器周圍滯留約13 min[10]。于是，AUV在一天內(nèi)可以按照固定次序訪問40個節(jié)點(diǎn)，然后回到船塢加載燃料、下載數(shù)據(jù)。

　　本文的模擬場景是，傳感器使用攝像機(jī)拍攝部署區(qū)域的視頻，以進(jìn)行入侵檢測。傳感器節(jié)點(diǎn)以720p的高分辨率來存儲監(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)行編碼。首先就能對從各個圖像中提取出來的信息量和這些信息對用戶的有用度做出主觀判斷，然后為這些數(shù)據(jù)分配摘要價值dd。表1列出了這些價值及其他參數(shù)的數(shù)值。

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

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

　　圖3(a)給出了HEF取不同值時陸地基站接收到的總體信息價值情況。如預(yù)期，當(dāng)HEF上升時優(yōu)先級較高的事件的基本信息價值較高，所以各啟發(fā)式算法的信息價值量均有上升。沒有進(jìn)行聲學(xué)傳輸?shù)腁UVO策略的信息價值最低，而GAVI策略利用了各數(shù)據(jù)摘要的本地信息價值，所以總體信息價值量最高。

　　本文根據(jù)數(shù)據(jù)到達(dá)陸地基站的方式研究了信息價值的構(gòu)成。圖3(b)和3(c)給出了UPD和GAVI實(shí)現(xiàn)的信息價值的構(gòu)成?？傮w信息價值曲線與圖3(a)相同。該數(shù)值是通過聲學(xué)路由傳輸?shù)男畔r值和AUV實(shí)現(xiàn)的有條件信息價值之和。請注意，AUV在兩種情況下傳輸?shù)模o條件）信息價值相同（即圖3(a)中AUVO的價值）。研究UPD的性能曲線，發(fā)現(xiàn)當(dāng)HEF較低時UPD和AUVO策略之所以比較接近，并不是因為通過聲學(xué)鏈路傳輸?shù)膬r值較低，而是因為AUV航行器攜帶的無條件價值與有條件價值之間的落差完全掩蓋了這種增益。當(dāng)攜帶的大多數(shù)數(shù)據(jù)不夠緊急時更是如此。相反，GAVI維護(hù)了這種增益，根據(jù)信息價值情況智能化選擇聲學(xué)傳輸內(nèi)容，于是通過聲學(xué)路由傳輸高信息價值的數(shù)據(jù)的時間提前。

4 總結(jié)

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

　　參考文獻(xiàn)

　　[1] 郭忠文，羅漢江，洪鋒，等.水下無線傳感器網(wǎng)絡(luò)的研究進(jìn)展[J].計算機(jī)研究與發(fā)展，2010，47(3)：377-389.

　　[2] 劉亞，劉功亮，康文靜.壓縮感知和LEACH結(jié)合的水下傳感器網(wǎng)絡(luò)信息采集方案[J].傳感技術(shù)學(xué)報，2013，26(3)：388-395.

　　[3] 洪璐.水下傳感器網(wǎng)絡(luò)高效數(shù)據(jù)傳輸協(xié)議研究[D].青島：中國海洋大學(xué)，2011.

　　[4] 劉玉梁，潘仲明.水下無線傳感器網(wǎng)絡(luò)能量路由協(xié)議的仿真研究[J].傳感技術(shù)學(xué)報，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é)報，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.