用于水声传感器网络自组织的询问式泛洪广播算法∗

肖东魏丽萍　陈庚　陈岩　马力

（中国科学院水声环境特性重点实验室　北京　100190）

用于水声传感器网络自组织的询问式泛洪广播算法∗

肖东†魏丽萍陈庚陈岩马力

（中国科学院水声环境特性重点实验室北京100190）

水声传感器网络（Underwater acoustic sensor networks，UASN）通常由随机散布的传感器节点组成。需要通过自组织算法将这些节点组成具有一定功能的网络。目前，已有较多成熟的用于陆地无线传感器网络（Wireless sensor networks，WSN）的自组织算法。但水声通信中存在的严重的传播损失、较高的背景噪声、有限的通信带宽、较长的传播时延、复杂的多途信道等，使得大多数适用于WSN的自组织算法难以适用于UASN。本文提出了一种改进的自组织算法，在简单泛洪广播算法中附加一段询问过程。通过OPNET仿真证明了在相同的条件下，相比于简单泛洪与概率泛洪广播算法，本算法可以在较短的时间内建立起有效路由，降低了水声网络在自组织阶段的能量消耗。

水声传感器网络，自组织算法，泛洪广播

1　引言

UASN用途广泛，例如：海洋环境及水文数据收集、水下灾害多发区域监视和分布式水下预警等。1993年，由美国（Office of naval research，ONR）资助的（Autonomous ocean sampling networks，AOSNs）项目最早提出了水声网络应用的概念［1］。二十年来，国际上比较著名水声网络研究计划有：美国的Seaweb海网计划、沿海大陆架观测计划（The front-resolving observational network with telemetry，FRONT）沿海大陆架观测计划，欧共体的（Marine science and technology program，MAST）计划等［1-3］。

组成水声网络的潜/浮标节点由船只或飞机随机布放在感兴趣的水域中，需要通过自组织算法才能构成具有一定功能的水声网络，可以说自组织算法是无线网络的基石。目前，用于WSN的自组织算法的大体思路有以下两种：（1）在各节点布放之后存在一个路由发现阶段，在该阶段每个节点按照一定规则形成自己的路由表，按照路由表发送数据包，并根据实际情况对路由表进行定期或者不定期的更新；（2）在各节点布放之后，每个节点不形成自己的路由表，只在有数据包需要发送的时候，根据用户需要、网络状态以及节点分布情况寻找路由进行发送。考虑到工程实现时各方面因素的限制，UASN尚不适宜组建大规模层次化网络，也暂时难以使用第2种思路进行网络自组织。

全网范围内的泛洪广播算法是在设计平面化自组织网络时常用的策略，但是直接泛洪广播容易造成数据重复广播，引发广播风暴，造成信道拥塞［4］。针对泛洪广播算法的改进算法也有很多，大致分为四类［5］：（1）简单或盲泛洪（Simple or blind flooding）；（2）概率或聊天式泛洪（Probabilistic or gossip flooding）［6］；（3）地域式泛洪（Area based flooding）［7］；（4）邻居知识式泛洪（Neighbor knowledge flooding）［8］。上述算法一般适用于移动性较强的无线传感器网络。其中，地域式泛洪通常需要每个节点可以较精确的获得自身的地理位置信息，邻居知识式泛洪一般需要本地拓扑结构及重复消息的统计信息［8］。而UASN的潜/浮标节点在布放后难以调整参数、几乎没有移动性，且潜标节点需要一定的辅助设施来获得自身较精确的地理位置。因此，将地域式泛洪或邻居知识式泛洪算法在UASN中工程实现，尚有难度。

本文将简单泛洪及概率泛洪两种算法移植到UASN中，经OPNET软件仿真发现：大多数情况下，部分节点难以在一定时间内形成完整的路由表，增加泛洪广播轮数对路由表形成的帮助有限。为改善上述情况，本文提出了一种询问式泛洪广播算法（下文简称为本算法），即在一轮泛洪广播之后增加了邻居询问及路由更新过程。以简单泛洪及概率泛洪算法为参考，在几种典型的拓扑结构下针对本算法进行了OPNET软件仿真。仿真中所有节点都在给定的时间内形成了完整的路由表，且节省了节点能量消耗。

2　算法设计

网络路由一般分为三种方式：先验式、反应式和混合式。水声传感器网络以水声通信作为物理层，资源极其有限。而反应式网络路由，即引言中的第2种思路，通常占用资源较多，不适用于水声传感器网络。随机布放的潜标节点虽然基本不会移动，但是也不可能存在先验性的路由表。所以，目前认为混合式路由比较适宜水声网络。即引言中的第1种思路，在潜标布放之后存在一个路由组织建立的阶段，在该阶段每一个节点建立自身路由表，并在之后的信息传输阶段对该路由表进行维护。本文提出的询问式泛洪广播算法适用于路由组织建立阶段。本算法在一轮简单泛洪广播之后增加了询问过程，并根据算法需要设计了相应的帧格式与路由表结构。

2.1自组织流程

本算法的自组织流程如图1所示。每个节点在初始化阶段随机地设置一个广播时间，在初始状态中等待该广播中断。在广播中断时发起一次泛洪广播。广播之后进入空闲状态，该状态下只通过询问邻居的方式对路由表进行更新。因此，采用本算法时整个网络只存在一轮泛洪广播。本算法认为水声通信信道具有互易性，在收到所有正确的数据帧时，都会根据帧信息更新路由表。在链路层协议中，可以采用随机退避重发的机制。多次重发失败后，认为到达目的节点的链路断开，清空路由表中对应项。将该数据帧留存到回收站，等待链路畅通后，再重新发送。

HXD3C型机车在济南机务段实际应用过程中发现EBV故障主要表现为:085故障、限制开关打开、单闸侧缓失效、列车管自动减压及制动手柄失效等现象。

图1　自组织算法流程图Fig.1 Flow chart of self-organization algorithm

其中，路由完整的判定准则为本节点可以通过网络路由访问所有其他节点。询问邻居时，本节点向一跳以内的所有邻居节点广播一个询问帧。每个询问帧可以询问一个其他节点的路由。接收到该询问帧的邻居节点在知情且空闲的情况下，发送一个回复帧给本节点。本节点收到回复帧之后，更新自身路由表。

2.2数据处理流程

图1的处理数据流程中，需要针对不同数据进行不同方式的处理，具体处理方式参见接收端流程图，见图2。接收端首先对数据帧进行校验，校验正确的情况下，按照图2进行数据处理。如果校验出错，则将该帧丢弃，不作任何处理。

图2　数据处理流程图Fig.2 Flow chart of data processing

2.3帧格式及其他

本算法所用的帧格式如图3所示。帧同步为水声通信物理层的时频同步头。帧信息包含了自组织算法所需要的所有信息。数据类型中应标明本帧为泛洪广播帧、路由询问帧还是路由回复帧。设置帧序号是为了区别同一节点先后发出的不同数据帧，以免错漏以及重复。

另外，每个节点需要维护一个自己的路由表，路由表包含三项信息：（1）目的节点是否能够访问；（2）到达该目的节点需要经过的下跳节点地址；（3）到达该目的节点需要经过的跳数。

图3　帧格式Fig.3 Frame format

3　软件仿真及结果分析

利用OPNET软件，对水声通信进行建模，并设计了半双工方式的实现方法。针对几种典型的拓扑结构，利用本算法进行软件仿真，并以简单泛洪广播算法作为参考，对仿真结果进行了分析。

3.1水声通信建模

OPNET中，将无线链路分为14个管道模型阶段进行建模。需要在节点模型中设定发射机与接收机的中心频率、带宽、调制方式、传输速率、纠错编码。对于无线链路，OPNET中默认方式是全双工，而目前大多数水声通信只能采用半双工方式［9-10］。

3.1.1管道模型阶段

仿真中，以实验室现有水声Modem的参数作为参考，将水声通信参数设置为：BPSK调制、半双工方式、中心频率6 kHz、带宽4 kHz、通信速率1 kbps、有效距离约5 km。具体到水声通信中，还需要注意的管道模型阶段有如下几点。

（1）第6阶段传播时延中，水下声波传播速度为1500 m/s，与OPNET中默认电磁波传播速度不同，需要修改。

（2）第8阶段接收功率中，需要根据水声传播衰减模型重新编写代码计算接收功率。本算法的仿真中采用了经典的Marsh-Schulkin模型［11］。

（3）实际水声通信中，一旦多个接收信号之间发生碰撞，这些接收信号都无法正确接收。因此在第9阶段的噪声串扰中，应放大信号间噪声串扰的影响。

（4）第10阶段背景噪声中，应计算海洋背景噪声级，仿真中采用经典的经验公式［12］将其分为四类进行计算。

（5）通过调整发射功率等参数，使得第11阶段信噪比中，在没有碰撞时的误码率在10-3左右，而发生碰撞时误码率在10-1量级，比较符合水声通信的情况。

3.1.2半双工设计

前已叙及，OPNET中使用的无线链路均为全双工通信方式，不论同一节点的发射机与接收机是否设置为相同中心频率以及带宽。因此，需要自行设定半双工通信方式。

OPNET仿真中设计的节点模型如图4所示。图中Source为数据来源，可以视为传感器。Router为自组网算法模块。Transmitter为发射换能器。Receiver为接收水听器。实线表示数据帧流向。虚线为统计中断线，一根为接收信号上升沿触发中断，标志接收信号起始，另一根为接收信号下降沿触发中断，标志接收信号结束。当发射换能器处于发射状态时，忽略接收信号的上升沿及下降沿触发中断，并丢弃所有接收到的数据帧。反之，设置水听器接收状态标志，将待发射信号延迟到下降沿触发中断之后再发送。

图4　节点模型Fig.4 Node model

需要补充的是：在无误码的情况下，数据帧成功接收时的流中断（由Receiver指向Router的数据帧流向线产生）与接收信号下降沿中断是同时产生的，取其一即可。但在因为误码而丢弃数据帧的情况下，不会产生流中断，但还是会产生下降沿中断。因此必须使用两条统计中断线来设置和清空接收水听器的接收状态标志位。

3.2仿真结果分析

对几种拓扑结构分别进行了仿真，拓扑结构图依次如图5所示。以简单泛洪广播算法及概率泛洪广播算法作为参考，考察了几种拓扑结构下本算法的网络自组织时间及能量消耗情况。对于概率泛洪算法，若其泛洪概率设置接近于1，则与简单泛洪差别不大；反之，泛洪概率设置接近于0时，相当于水声通信链路可靠性极低，网络自组织难以正常进行。因此，将其泛洪概率设置为0.5，即当一个节点接收到来自其他节点的新的泛洪广播数据时，50%的情况下会将该数据继续泛洪广播下去。另外，仿真中网络自组织完毕的标志为建立起有效的水声网络，即所有节点都可以通过网络路由访问到其他任何节点，暂且不论是否为最佳路由路径。因为不同的衡量标准下会产生不同的最佳路由标准。

图5　仿真所采用的拓扑结构Fig.5 Topologies in the simulation

仿真结果如表1所示。表中4种拓扑结构依次与图5中的4幅子图一一对应。图5（a）星型拓扑结构以一个节点作为中心节点，其他节点分布在其周围，且通信范围内仅存在中心节点；图5（b）环型拓扑结构，每一个节点的通信范围内都只存在两个其他节点；图5（c）蜂窝式拓扑结构可以实现对布放海域的最佳覆盖；图5（d）分布式拓扑结构是随机布放的一个示例。

仿真中假设所有节点布放完毕后再开始自组织。设定网络自组织的时间界限为1800 s，即1800 s以后放弃自组织。表中广播次数与询问次数的计算方法为每当有一个节点发起泛洪广播或者询问时，便计算一次。

由表1可见，几种拓扑结构下，简单泛洪及概率泛洪广播算法均未能够在1800 s内建立起有效网络。而本算法最长的自组织时间未超过1000 s。

首节点建立时刻、次节点建立时刻分别是指整个网络中有一个节点或两个节点建立起自身完整路由表的时刻。几种拓扑结构下，本算法与简单泛洪算法的首个节点的完成时刻相同，且均在300 s之内。不难推断，这两种算法中，首个节点均是在第一轮泛洪广播阶段建立起自身路由表的。而对于概率泛洪算法，由于其泛洪广播存在一定的概率性，首节点建立时刻稍晚于另外两种算法。

表1　仿真结果比较表Table 1 Simulation results comparison

从次节点建立时刻分析可见，简单泛洪算法的网络自组织效率较低，同时结合其完成情况来看，简单泛洪算法在后续的多轮泛洪广播中能够建立起完整路由的节点数量也极少。说明简单泛洪算法仅在一轮泛洪广播内比较有效，多轮泛洪广播对建立有效路由的帮助不大。而概率泛洪算法可以在一定程度上避免冲突，网络自组织效率稍高于简单泛洪算法。但是，与本算法相比，仍略逊一筹。

与陆地无线传感器节点不同的是：分布式水声网络节点的能量主要消耗在换能器发射声信号上，接收信号与信号处理的能量消耗相对较小甚至可以忽略。所以信号发射次数基本上就可以反映水声网络整体的能量消耗情况。以图5（a）中5节点星型拓扑结构为例，参考实验室现有水声Modem的参数，其中信号发射电功率10 W，接收及待机电功率0.05 W，对水声网络单个节点的平均能量消耗进行了仿真。仿真结果如图6所示。

图6　三种算法的能量消耗比较Fig.6 Comparison of used energy

图6中，横轴为时间，纵轴为单位时间内消耗电能量的焦耳数。点线为本算法的能量消耗，虚线和实线则分别对应概率泛洪算法和简单泛洪算法的能量消耗。通过比较容易发现，相比于简单泛洪和概率泛洪，本算法有效降低了网络自组织过程中的能量消耗。

4　结论

本文提出了一种适用于小规模水声传感器自组织网络的询问式泛洪广播算法。本算法在一轮简单泛洪广播算法之后增加了针对路由表空缺项询问邻居的流程。通过OPNET仿真证明了本算法可以在相对较短的时间内，建立起有效路由。且相比于简单泛洪广播算法，降低了水声网络的在自组织阶段的能量消耗。

［1］吴松伟.水声自组网节能路由协议研究［D］.哈尔滨：哈尔滨工程大学硕士学位论文，2010.

［2］邓婕.浅海水声自组网MAC协议的设计与实现［D］.厦门：厦门大学硕士学位论文，2009.

［3］李立.多水下自治机器人水声自组网的研究［D］.青岛：中国海洋大学硕士学位论文，2006.

［4］施韦，李善平，杨朝晖.移动自组织网络中一种基于多点中继策略的优化泛洪广播算法［J］.计算机研究与发展，2007，44（6）：924-931. SHI Wei，LI Shanping，YANG Zhaohui.An optimized floodingalgorithmbasedonmultipointrelayingfor mobile ad hoc networks［J］.Journal of Computer Research and Development，2007，44（6）：924-931.

［5］REINA D G，TORAL S L，JONHSON P，et al.Hybrid flooding scheme for mobile ad hoc networks［J］.IEEE communication letters，2013，17（3）：592-595.

［6］HAAS Z J，HALPERN J Y，LI L.Gossip-based ad hoc routing［J］.IEEE/ACM Trans.Networking.2006，14（3）：479-491.

［7］PARK S，LEE E，PAKR H，et al.Mobile geocasting to support mobile sink groups in wireless sensor networks［L］. IEEE Commun.Lett.，2010，14（10）：939-941.

［8］PENGW，LUX.Onthereductionofbroadcast redundancy in mobile ad hoc networks［C］.First Annual Workshop on Mobile and Ad hoc Networking and Computing，2000：129-130.

［9］冯菲，高翔，李霞.水声通信网MAC层协议仿真与分析［J］.声学与电子工程，2007，（1）：26-30. FENG Fei，GAO Xiang，LI Xia.Simulation and analysis of MAC protocol in underwater acoustic communication networks［J］.Acoustics and electronics engineering，2007，（1）：26-30.

［10］林碧兰，程恩，袁飞.基于OPNET的水声通信网MAC层协议的研究［J］.电子设计工程，2010，2（18）：1-3. LIN Bilan，CHENG En，YUAN Fei.Research of the MAC protocol for underwater acoustic communication networks based on OPNET［J］.Electronic Design Engneering，2010，2（18）：1-3.

［11］SCHULKIN M，MARSH H W.Absorption of sound in sea-water［J］.Journal of the Acoustical Society of America，1977，62（3）：558-564.

［12］COATES R F W.Underwater acoustic systems［M］. London：Macmillan Education LTD，1990.

Inquiring flooding broadcast algorithm for underwater acoustic sensor self-organization networks∗

XIAO Dong†WEI LipingCHEN GengCHEN YanMA Li
（Key Laboratory of Underwater Acoustic Environment，Institute of Acoustics，Chinese Academy of Sciences，Beijing 100190，China）

Usually,underwater acoustic sensor networks（UASN）is constructed by randomly deployed sensor nodes.In order to construct network of certain functions with these nodes,self-organization algorithm is needed.There are many self-organization algorithms for wireless sensor networks（WSN）onshore.But in underwater acoustic communication,the phenomena,such as：severe attenuation,high background noise, limited bandwidth,long time delay,complicated multi-path,etc.,most self-organized algorithms for WSN are hard to apply to UASN.An improved self-organization algorithm is proposed,which appends an inquiry process to flooding self-organization algorithm.It is proved by OPNET simulation that under the same conditions the network could be successfully established by the improved self-organization algorithm in a shorter time compared with simple flooding and probabilistic flooding algorithms,and the energy consumed in organization period is decreased.

Underwater acoustic sensor networks,Self-organization algorithm,Flooding broadcast

TN929.3

A

1000-310X（2015）01-0058-07

10.11684/j.issn.1000-310X.2015.01.009

2014-02-12收稿；2014-04-19定稿

∗国家自然科学基金项目（61302109）

肖东（1984-），男，安徽蚌埠人，博士研究生，研究方向：信号与信息处理。

E-mail：xiaodong@mail.ioa.ac.cn