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.