1、第 卷 第 期 年 月传 感 技 术 学 报 .项目来源：国家自然科学基金资助项目（）；青海省自然科学创新团队基金资助项目（）收稿日期：修改日期：，（，；，；，）：，（），：；：基于状态着色的水声网络 协议田晓静，杜秀娟，王丽娟，李 冲，韩多亮（青海师范大学计算机学院，青海省物联网重点实验室，青海 西宁；藏语智能信息处理及应用国家重点实验室，青海 西宁；高原科学与可持续发展研究院，青海 西宁）摘 要：水声网络中的 协议主要采用 机制，然而 控制包不仅限制了并发传输的可能性，进而降低了信道利用率和吞吐量，而且造成信道资源分配不公平。为了提高吞吐量、信道利用率和公平性，提出了一种基于状态着色的水声
2、网络（，）协议。在 协议中，每个节点根据自身一跳邻居表构建本地分层图，通过侦听数据帧或 帧获知邻居节点状态来为本地分层图中的节点着色，并根据本地分层着色图调度包的发送，减少数据帧的碰撞与重传。协议在避免冲突的前提下实现了并行传输。同时，给出基于公平性的退避方案以提高 协议的公平性。仿真结果表明，协议与 协议和 协议相比在端到端延迟、吞吐量和平均能耗等方面有明显的优势。关键词：水声网络；协议；本地分层着色图；信道利用率；中图分类号：文献标识码：文章编号：（）近年来，水声网络（，）在海洋学数据收集、环境监测、战术监视和资源发现等研究领域都有广阔的应用前景。电波在 中不适用，因此，使用声波进行通信。
3、声波在水下环境中比电波效果更好，但也受以下几方面的制约：声波在水下的传播速度只有 左右，比无线电通信中电波 的传播速度低 个数量级，水声信道具有高延迟的特点；水声信道受多径效应、噪声等因素的影响，使得水声信道误码率很高；水声信道中声音信号的可用带宽很窄。此外，还存在节点移动和更换电池困难的问题。因此设计一种适用于 的 协议将面临极大的挑战。随着 的关注度日益增大，越来越多适用于 的 协议被国内外学者相继提出。协议一般分为基于竞争的 协议和基于无竞争的 协议。基于无竞争的 协议包括频分多址（，第 期田晓静，杜秀娟等：基于状态着色的水声网络 协议）、时分多址（，）和码分多址（，）。将频带分成若干个
4、子频带，然而水下信道带宽很窄，会造成很低的吞吐量，因此 不适用于。引入伪随机码，使得每个节点可以在同一时间使用同一频带进行通信，提高了信道利用率，然而，难以解决远近效应的问题，因此并不适用于。允许将时间信道分为离散的时隙，但在 中时钟同步难以实现，在水下并不适用。基于竞争的 协议分为随机访问的 协议与基于握手的 协议。夏威夷大学提出的 协议，每个节点可以随时发送数据包，简单易行，但是极易产生冲突；文献提出的 协议通过增加 控制包的长度，来避免冲突，但是过长的 控制包持续占用信道造成能量极大的浪费并且降低了信道利用率；文献提出的 协议引入时隙技术，只有在一个时隙的开始才能发送报文，因此短的控制包
5、也可以避免冲突，但是时钟同步在 中是一个难以解决的难题，较长的时隙划分对于有限的水下带宽造成了极大的浪费，每次数据传输之前都需要经过一系列的握手，且同一时间内只有一组数据进行传输，节点之间的握手不仅增大了能量消耗，同时也延长了数据传输的平均延时；文献提出的 是一种基于预约的 协议，不需要 握手机制避免冲突，然而引入了、等控制包和复杂的调度算法来避免冲突，若在移动的 中，传播延时估算误差会很大，因此只适用于静态网络或者移动性不大的网络中。本文提出一种新型的基于状态着色的水声网络 协议，与基于竞争的 协议相比，该协议不需要 握手机制避免冲突产生，通信全程只有数据帧和确认帧（，），没有使用除 以外的
6、任何控制包避免冲突，减少控制包可以减少能耗，提高信道利用率。我们通过节点一跳邻居表及其节点状态构建每一个节点的本地分层着色图，每个节点根据本地分层着色图实现尽可能多的并发无冲突传输，同时解决了隐藏终端和暴露终端的问题。为了提高协议的公平性，提出基于公平性的退避方案，给不容易抢占信道的节点较小的退避时间。当节点数据传输结束或一次抢占信道成功后传输的数据帧数达到最大值，节点开启退避计时器，退避时间结束后重新抢占信道。因此，协议在能耗、信道利用率和公平性等方面有极大的改进。协议为了更好地阐述 协议的机制，将第 节中描述 协议所使用的参数解释说明，如表 所示。表 协议中的符号参数符号含义节点 节点 的
7、本地分层图中的节点集节点 的本地分层图中的节点 与邻居节点共享边集节点 的本地分层着色图 包的传输延时 包的传输延时最大传播延时成功通信次数请求通信次数接收节点与发送节点的距离 协议的设计 构建本地分层着色图 本地分层拓扑图在网络初始化阶段，节点向网络中定期广播 消息（消息包含发送节点的、层级和位置等信息），传感器节点通过接收的 消息获取一跳邻居表和层级信息。根据传感器节点到 的跳数，为 中的每个节点指定一个层级。将拓扑图中节点附带层级后，得到分层拓扑图，如图 所示。此外，节点还根据收到 消息中邻居节点的信息，构建本地（一跳）邻居表，如表 所示。图 分层拓扑图表 节点 的邻居信息表节点层级层级
8、老化时间状态颜色位置，在 协议中，根据每个节点的本地一跳邻居表，为每个节点构建本地分层图。具体过程如传 感 技 术 学 报第 卷下：如图 所示，根据节点 的一跳邻居表（表）为节点 构建本地分层图，其中节点 的本地分层图中节点集为：，即：，；如果两个节点是一跳邻居那么两个节点共享同一条边，则（，），（，），（，），（，）。由于每个节点只会和本层或者上下层的节点成为一跳邻居，因此 节点和最底层的节点的本地分层拓扑图中层级数 为（），其余节点的本地分层拓扑图中层级数 都为（）。节点 的本地分层图可表示为，。图 节点 的本地分层图图 节点 与节点 通信 基于节点状态构建本地分层着色图 协议的通信过程如
9、图 所示，节点 是发送节点，节点 是接收节点，节点、节点 分别为节点 与节点 的一跳邻居节点，节点 通过尝试发送第一个试探数据帧抢占信道，第一个试探数据帧里有标识告诉节点 本次信道占用期间传输数据帧数。当节点 收到第一个试探数据帧时，向节点 回复 帧，表示传输无冲突。节点 收到来自节点 的 帧后，开始传输包链中剩余的数据帧，当节点 收到最后一个试探数据帧，回复一个 帧。节点 根据收到的 帧判断是否重传部分数据帧。协议中，帧对第一帧数据帧进行确认是为了判断是否成功抢占信道，帧对包链中的其余数据帧进行确认是为了判断是否需要重发丢失或出错的数据帧。在半双工通信的，需要一种机制来避免发送节点即将进行的
10、数据传输干扰其邻居节点正在接收其他节点的数据帧。为了解决这种干扰，协议通过侦听信道中的数据帧或 帧判断邻居节点状态，根据邻居节点状态为本地分层图中的节点着色，所着颜色分为以下 种颜色。绿色表示该邻居节点状态未知或处于发送避免状态，发送节点可以尝试给该邻居节点发送第一帧试探数据帧。在网络初始化完成后数据传输开始前，节点将邻居表中邻居节点的状态初始化为未知状态；为了保证节点使用信道的公平性，当节点数据传输结束或一次抢占信道成功后传输的数据帧数达到最大值，按照协议规则节点要进入发送避免状态。黄色表示邻居节点处于发送状态，若给正处于发送状态的邻居节点传输数据，则会在该邻居节点处产生收发冲突。当发送节点
11、发送包链中的非最后一帧时，发送节点的邻居节点也侦听到来自发送节点的 （表示本节点侦听到了 帧，但该帧的目的节点不是本节点），此时发送节点的邻居节点认为发送节点处于发送状态。红色表示邻居节点正在接收来自其他节点的数据，此时若当前节点给该邻居节点发送数据会在该邻居节点处产生收收冲突。当接收节点发送回应第一帧试探数据帧的 帧，并进入接收状态。此时接收节点的邻居也会听到 帧（表示本节点侦听到了 帧，但该帧的目的节点不是本节点），此时接收节点的邻居节点认为接收节点处于接收状态。图 节点 的分层着色图网络初始化完成后，在开始传输数据之前，节点将邻居表中邻居节点的状态初始化为未知状态。以节点 为例，网络初始
12、化后节点 的本地分层图中所有的节点的颜色都为绿色（图（）中灰色节点）。若节点 向其他邻居节点（除节点 以外的邻居节点）发送数据帧，节点 尝试发送第一个数据帧后，节点侦听到来自节点 的，将本地分层图中的节点 的颜色由绿色变为黄色（图（）中淡灰色节点）。若节点 接收到一个来自其他邻居节点（除节点 以外的邻居节点）的数据帧后，会回复一个 帧；节点 会听到来自节点 的 帧，将本地分层图中的节点 的颜色由绿色变为红色（图（）中深灰色节点）。节点 通过不断地侦听信道中的数据帧和 帧来确定邻居节点的状态，进而实时地给节第 期田晓静，杜秀娟等：基于状态着色的水声网络 协议 点 的本地分层图 着色，最后得到节点
13、 的本地分层着色图，。数据传输若节点 向节点 发送数据，要满足以下两个条件：节点 没有红色的邻居节点；节点 的颜色为绿色。图 数据帧传输满足这两个条件后，节点 与 的通信过程如图 所示：假设以包链的形式传输数据，一次数据传输最多发送 个数据帧。首先节点 向节点 尝试发送第一个试探数据帧，并要求节点 对该帧执行确认，节点 的邻居节点也会听到，此时节点 的邻居节点认为节点 处于发送状态并将本地分层着色图中节点 的颜色变为黄色；节点 收到，给节点 回复 帧，节点 的邻居节点听到 帧，此时节点 的邻居节点认为节点 处于接收状态并将本地分层着色图中节点 的颜色变为红色；节点 收到 帧后，依次向节点 传输
14、包链中剩余的 个数据帧，直至发送最后一个数据帧，并要求节点 对该 个帧执行确认。节点 收到 后，向节点 回复 帧，帧会告诉节点 传输的 个数据帧是否成功传输。若传输成功，节点 的邻居节点听到 帧认为节点 处于发送避免状态，将本地分层着色图中节点 的颜色变为绿色；若传输失败，节点 需要立即重传出错的数据帧，节点 的邻居节点的本地分层着色图中节点 的颜色不变直到听到新的 帧并且所有数据帧完全成功传输，节点 颜色变为绿色。节点 的邻居节点（节点）在侦听到节点 传输的最后一个数据帧后等待，若没有听到节点 重传，节点 的邻居节点认为节点 已经处于发送避免状态并将本地分层着色图中节点 的颜色变为绿色。帧发
15、生丢包存在以下两种情况（具体示意图如图 所示）：节点 发送的包链中的第一个数据帧后，等待，没有接收到回应第一个数据帧的 帧，则节点 将重新传输第一个试探数据帧，直到接收到对应的 帧，或者重传的次数超过了预定义的次数；节点 发送包链中的最后一个数据帧 后，等待，仍然没有收到来自节点 的 帧，节点 将立刻重新传输最后一个数据帧，然后等待接收 帧。基于公平性的退避方案公平性是指信道资源可以公平地被节点获取，较早发送请求的节点应该优先传输数据。但是由于 长传播延时的特性，是否能优先传输数据不仅取决于节点发送请求的时间，还取决于节点的位置。时空不确定性使得距离接收节点较近的节点会迅速抢占信道，而其他距离
16、接收节点较远的节点难以获得信道资源，导致节点在获取信道资源上的不公平现象。因此，提出基于公平性的退避方案，改善信道分配资源不公平的现象。发送节点通过计算自己的优先级函数来评估自己接入信道的可能性。优先级函数对尚未接入信道的发送节点并不会产生影响。优先级函数是基于发送节点与接收节点的通信次数和发送节点的请求数据传输的次数。通信次数越大时，优先级函数值越小，发送节点接入信道的可能性越小；请求数据传输的次数越大时，优先级函数的值越大，发送节点接入信道的可能性越大。发送节点的优先级函数 的计算公式如式（）所示：图 函数图像（）（）式中：权重系数，为发送节点与接收节点的通信次数，为发送节点请求数据传输的次数。权重系数 和 可以平衡通信次数和请求次数的影响。根据上述公式，当 增大，优先级函数值变小；增大，优先级函数值变大。通信次数越少，请求数据传输次数越多，优先级函数值越大，节点接入信道的可能性越大。函数 （）和函数 的图像如图 所示。传 感 技 术 学 报第 卷当节点数据传输结束或一次抢占信道成功后传输的数据帧数达到最大值，都会开启一个退避计时器。发送节点的优先级函数值越大，越早结束退避计时器。
