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