文獻標識碼： A
文章編號： 0258-7998(2015)02-0127-04
0 引言
水下傳感器網絡(UWSNs)[1]由通過聲音鏈路進行通信的大量水上和水下傳感器組成。在該網絡中，傳感器節點的主要通信模式是利用聲音調制解調器向岸上的數據采集基站發送數據[2-4]。這種模式中報文只要生成便能發送，因此數據傳輸的延時較低。然而，這種通信模式的BER較高，且通信帶寬不到10 kb/s。為此，傳感器節點只能通過聲學鏈路發送被采集數據的數據摘要。另一種通信方法就是使用自主式水下航行器(AUV)[5]。AUV航行器訪問節點，通過高速短距離光學通信下載數據。最后，AUV航行器周期性地浮出水面，通過無線通信把數據傳輸給陸地基站來下載采集到的數據。這種場景的示意圖見圖1。
實踐證明[6-7]，傳感器節點采集到的信息的規模、價值和優先級有很大區別。人們很難預測何時何地將會發生重大事件，哪些節點能夠檢測到這些事件。而傳感信息的原始價值會隨著時間的推移不斷下降，因此應該將數據盡快傳輸給陸地基站和最終用戶。數據到達用戶的時間越晚，數據的價值越低。所以，每個傳感器節點必須確定采集到的數據塊中的次要數據（比如較低分辨率的鏈路或照片）何時通過聲學鏈路發送給陸地基站，以及該數據塊中的哪些主干部分應該優先傳輸。
本文針對水下傳感器獲得的數據塊信息價值(VoI)提出多種調度算法，對聲學傳輸調度策略的復雜性問題進行研究，并設計了不同傳感器調度策略以確定何時通過聲學路由傳輸哪些數據。本文總體目標是設計合適的調度策略使傳輸給陸地基站的數據信息價值最大。最后，基于真實場景的仿真研究表明了本文方案的有效性。
1 UWSN的信息價值
1.1 相關定義
假設某一傳感器節點記錄的數據收集于尺寸為|D|的數據塊D內。tr(D)表示數據塊的創建時間。直觀來講，數據塊中的信息是指該次之前的觀測數據。∧表示所有可能的數據塊組成的集合。
尺寸為b的主干數據dig(D，b)是數據塊D中的部分數據。當b>|D|時，假設主干數據為初始數據塊本身。
用V(D，t)表示陸地基站(客戶)在時間t時接收到的數據塊D的信息價值(VoI)。將信息價值與客戶采取的行動的價值V(a)關聯起來，進而得到信息價值的實際定義。
定義1：信息價值V(D，t)表示客戶在知道了D這一必備信息后根據客戶策略采取的所有行動ai的價值之和：
定義2：有條件信息價值V(D，t|(D1，t1)…(Dk，tk))表示在之前時間ti接收到數據塊Di后，在時間t時接收到數據塊D的價值。
1.2 信息價值的形式
本文希望找到時間t時主干數據dig(D，b)的信息價值的閉型表達式。該價值將會低于初始價值V(D，tr)，一方面是因為信息的緊迫性使得信息價值隨著時間遞減，另一方面是因為信息的可概括性（描述數據被主干數據替代后信息價值如何減弱）。下文始終假設信息的緊迫性和可概括性互相獨立。這是因為，信息的緊迫性取決于觀察現象的含義（被觀察到的真實事件），而數據塊的可概括性主要取決于數據結構。根據這一假設，可以將信息價值表述為如下形式：
其中，dd表示主干數據價值衰減函數，dt表示時間價值衰減函數。不失一般性，本文將dd定義為主干數據尺寸和初始數據塊尺寸之比，而將tr定義為數據采集的時間。
本文認為數據塊的信息價值內容由初始價值、主干數據價值衰減函數和時間價值衰減函數三元組構成。使用一種指數衰減模型來模擬時間價值衰減函數：
dt(t-t0)=exp(Ptd·(t-t0))(3)
其中，Ptd表示時間衰減參數。尤其地，Ptd=0表示信息對延時不敏感，Ptd>>0表示信息衰減的速度很快。
1.3 有條件信息價值
直觀來講，有條件信息價值表示假設之前已經接收到小規模主干數據后，新主干數據提供的新信息。如果在同一時刻接收到所有主干數據，則結果就是實現的兩個價值之差。然而，因為小規模主干數據的接收時間較早，不是與它們的到達時間價值相減，而是與它們在當前時間的價值相減。有條件信息價值表示為：
V(dig(D，b2)，t2|(dig(D，b1)，t1))
=V(dig(D，b2)，t2)-V(dig(D，b1)，t2)(4)
2 傳輸調度算法
對所有傳感器節點持續進行觀察，并在具體的時間點記錄觀察數據(D1，t1)，…，(Di，ti)。假設傳感器節點沒有內存約束，可以存儲所有觀察數據直到AUV航行器到達。傳感器節點使用聲學解調器傳輸它們采集的數據塊主干數據。當AUV航行器訪問傳感器節點時，節點把從上次AUV航行器訪問迄今的所有數據塊傳輸給AUV航行器（光學傳輸）。每當完成一次傳輸時，節點必須調度一個新的主干數據用于傳輸。確定傳輸哪個主干數據及傳輸時間，決定了陸地基站接收到的信息價值。設計調度算法的總體目標是使傳輸數據的總體信息價值最大化。本節首先研究利用聲學鏈路進行主干數據傳輸調度的計算復雜性，然后給出問題的啟發式求解方法。
2.1 調度復雜度
假設有一個由數據塊、時間和信息價值內容組成的靜態集合{(D1，t1，P1)，…，(Dn，tn，Pn)}及一個時間段[ts，td]。在td之后不會記錄任何新的主干數據，在ts之前也不會傳輸任何數據塊或主干數據。假設節點統一通過帶寬B進行數據傳輸。
文中需要解決的調度問題實際上就是確定一種調度策略，即一個有序元組序列S={(ji，bi)}，使聲學鏈路上進行的第i次傳輸等價于在下述時間傳輸數據dig(D，bi)：
實現傳輸的總體信息價值最大化的公式如下：
其中，i表示在先前調度策略S中傳輸的主干數據D。
屬性：調度問題是NP難題。
證明：假設問題不是NP難題。眾所周知，背包問題的優化問題是NP難題[8]。可以將背包問題看成是所有主干數據價值為0且函數衰減參數也為0的特例（無時間衰減）。因此，可在多項式時間內求解調度問題的算法也將可以求解背包問題，這于假設矛盾，命題得證。
上述問題的計算成本很高，所以在數據塊不斷生成的條件下對主干數據進行傳輸調度也將導致較高計算成本。下文將定義3種可行的傳輸調度啟發式算法。
2.2 調度算法1：只利用AUV航行器(AUVO)
只通過AUV航行器不斷浮上水面來將數據傳輸給陸地基站，該種啟發式策略(AUVO)作為可以使用聲學調制解調器和多跳水下路由的其他策略的基準策略。在AUVO中，用戶接收到的信息價值即是AUV接收到數據時的數據塊信息價值。研究發現，通過使用聲學路由在AUV航行器傳遞數據前成功傳輸數據塊的策略可以提高被采集數據的信息價值。AUVO在實踐中也具有顯著優勢。例如，傳感器節點無需配備昂貴的聲學調制解調器（每個上千美元），因此成本更低；傳感器節點的電池壽命更長，因為聲學傳輸非常消耗能量；最后，節點的協議棧更為簡單，因為在通信時通過單跳光學鏈路下載數據，無需水下MAC和路由功能。
2.3 調度算法2：漸進式數據摘要調度（UPD）
在該策略下，傳感器節點無法對數據塊的信息價值內容進行本地評估。然而，它既知道dt函數的形狀，又知道可使信息價值的降低速度低于摘要規模的數據摘要步進量。由于節點只掌握了上述信息，所以節點的最優選擇就是在任意給定時刻發送手頭最小的數據摘要，然后是更大一些（增加了步進量）的數據摘要，依次類推，通過到達時間來破除關聯(tie)。此時的調度算法如下：
list:={}；
When AUV到達 do
將列表中所有完整的數據塊發送給AUV；
list:={}；
End
When 采集了數據塊D do
對所有b創建數據摘要dig(D，b)；
list:=list∪digests∪D
End
When 當前傳輸任務完成 do
list:=按照尺寸排序的列表；
current-transmission=list[0]；
list:=list[1:end]；
end
2.4 啟發式算法3：基于貪婪的平均信息價值(GAVI)調度
該策略假設節點可以確定被感知的數據塊的價值情況。利用這一信息，該策略可貪婪地實現傳輸數據的平均信息價值最大化。依次調度數據傳輸，于是下次傳輸將是單位時間的信息價值量最大的傳輸。這里的信息價值是考慮了之前相同數據塊傳輸的有條件信息價值。對于靜態數據塊集合，該策略實際上是個最優策略。然而，對于不斷接收到新數據塊的節點來說，一個新的價值更高的數據摘要可能因為更長的數據塊當前正在傳輸而需等待一段時間。該算法如下：
list:={}；
When AUV到達 do
將列表中所有完整的數據塊發送給AUV；
list:={}；
End
When 采集了數據塊D do
為所有b創建數據摘要dig(D，b)；
list:=list∪digests∪D；
End
When 當前傳輸任務結束 do
t=current time；
For 列表中的每個數據摘要d do
估計V:=V(d，t)；
估計ttrans(d):=size(d)/帶寬；
Vavg(d，t):=V/ttrans(d)；
End
list:=根據Vavg(d，t)排序的列表；
current-transmission=list[0]；
list:=list[1:end]；
End
3 仿真實驗
假設網絡在面積為6×7 km2的海床上部署40個傳感器節點，節點間距1 500 m。每個節點配備一個聲學解調器。節點和陸地基站間的平均傳輸率為10 kb/s。AUV航行器為Odyssey-IV系列航行器，航行速度為1.8 m/s[2]。于是，AUV航行器需要13 min左右從一個節點到達另一個節點。當AUV與傳感器節點相距不到100 m（清晰的水下通信）時，光學傳輸的速率可達10 Mb/s[9]。航行器如果要下載傳感器在一天內采集的1.1 GB數據，需要在傳感器周圍滯留約13 min[10]。于是，AUV在一天內可以按照固定次序訪問40個節點，然后回到船塢加載燃料、下載數據。
本文的模擬場景是，傳感器使用攝像機拍攝部署區域的視頻，以進行入侵檢測。傳感器節點以720p的高分辨率來存儲監測數據(1 280×720像素分辨率，29.97幀/s)。錄像被分割為1 min視頻大小的數據塊。假設視頻基于標準的H.264編解碼器進行編碼。考慮4種類型的數據摘要，每種表示一種或數種從關鍵的視頻幀中提取出來的圖像，并用WEBP編解碼器進行編碼。首先就能對從各個圖像中提取出來的信息量和這些信息對用戶的有用度做出主觀判斷，然后為這些數據分配摘要價值dd。表1列出了這些價值及其他參數的數值。
為了確定數據塊的價值，本文將其分為3種觀測類別C1、C2和C3，每種類別有不同的緊迫性和基本信息價值水平，如表2所示。觀測類別的分布不遵守均勻隨機分布：例如，入侵者很有可能在傳感器覆蓋的范圍內滯留1 min以上。因此，使用圖2中給出的馬爾科夫鏈來模擬觀測數據分布。假設在大多數時間內，系統的觀測事件均是非重要事件(C1)。事件的發生概率為PE。這些事件中有部分事件（比例為HEF）的優先級較高。自我躍遷Plst和Phst確定事件的平均長度。
在本文實驗中，改變信息價值最高的事件比例HEF，并且運行3種啟發式算法AUVO、UPD和GAVI。對每種設置，使用不同的隨機種子生成10個場景然后取均值，實驗結果見圖3。
圖3(a)給出了HEF取不同值時陸地基站接收到的總體信息價值情況。如預期，當HEF上升時優先級較高的事件的基本信息價值較高，所以各啟發式算法的信息價值量均有上升。沒有進行聲學傳輸的AUVO策略的信息價值最低，而GAVI策略利用了各數據摘要的本地信息價值，所以總體信息價值量最高。
本文根據數據到達陸地基站的方式研究了信息價值的構成。圖3(b)和3(c)給出了UPD和GAVI實現的信息價值的構成。總體信息價值曲線與圖3(a)相同。該數值是通過聲學路由傳輸的信息價值和AUV實現的有條件信息價值之和。請注意，AUV在兩種情況下傳輸的（無條件）信息價值相同（即圖3(a)中AUVO的價值）。研究UPD的性能曲線，發現當HEF較低時UPD和AUVO策略之所以比較接近，并不是因為通過聲學鏈路傳輸的價值較低，而是因為AUV航行器攜帶的無條件價值與有條件價值之間的落差完全掩蓋了這種增益。當攜帶的大多數數據不夠緊急時更是如此。相反，GAVI維護了這種增益，根據信息價值情況智能化選擇聲學傳輸內容，于是通過聲學路由傳輸高信息價值的數據的時間提前。
4 總結
本文研究了UWSN下的信息價值傳輸調度算法。具體來說，證明了當節點可以通過多跳聲學路由傳輸數據并將數據傳輸給過往的AUV航行器時，制定合適的調度策略可以使傳感器節點通過聲學技術傳輸傳感數據的數據摘要，進而實現傳遞給用戶的信息價值最大化。下一步將研究一個和多個AUV航行器的線路規劃問題，以實現信息價值最大化，同時全面評估不同方法的性能。
參考文獻
[1] 郭忠文，羅漢江，洪鋒，等.水下無線傳感器網絡的研究進展[J].計算機研究與發展，2010，47(3)：377-389.
[2] 劉亞，劉功亮，康文靜.壓縮感知和LEACH結合的水下傳感器網絡信息采集方案[J].傳感技術學報，2013，26(3)：388-395.
[3] 洪璐.水下傳感器網絡高效數據傳輸協議研究[D].青島：中國海洋大學，2011.
[4] 劉玉梁，潘仲明.水下無線傳感器網絡能量路由協議的仿真研究[J].傳感技術學報，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].系統仿真學報，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.