水声传感器网络分簇路由协议研究*
2012-11-24刘广钟
刘广钟，耿 伟
(上海海事大学 信息工程学院，上海201306)
水声传感器网络 (Underwater Acoustic Sensor Networks)是水声通信技术与无线传感器网络结合所产生的一个新的研究领域，经常应用于对固定海域的长期监测。这种网络一旦部署完毕，就需要在水下长期工作，而且，在此期间一般不会更换节点电池，因此延长网络生命期成为水声传感器网络的一个热点问题。在路由协议中，合理地选择路由对提高节点的能量效率、延长网络生命期十分重要[1]。LEACH协议分簇概念被引入之后，使得网络在节能以及网络寿命方面得到了很大提高，然而LEACH协议在水声传感器网络中的应用也有其自身不可忽略的局限性[2]。本文在LEACH算法的基础上介绍了一种改进的路由算法PBCP(Position-based Clustering Protocol)，该算法在簇首选举过程中充分考虑节点的能量因素，避免剩余能量较低的节点成为簇首节点。
1 LEACH协议及性能分析
1.1 LEACH算法描述
LEACH协议的全称是“低功耗自适应集群分层协议”(Low Energy Adaptive Clustering Hierarchy)，它采用动态分簇技术，使网络中的所有节点轮换充当簇首，以均衡网络中的能量消耗，延长整个网络的生命周期。在LEACH算法中，节点自组织成不同的簇，每个簇只有一个簇首。所有非簇首节点将自己的数据发给所属簇的簇首节点，为减少冗余数据的传输，簇首节点在数据融合后将数据发送给远方的Sink节点[3]。这样，每个非簇首节点都只需要知道自己所属簇的簇首信息即可，簇首也只需要维持很小的路由表，为了避免簇首能量消耗过快，每个节点须轮流担任簇首。
因此LEACH算法的实现分成若干轮，每一轮又可分成簇形成阶段和簇传输阶段，而簇传输阶段远远长于簇形成阶段。在簇形成阶段，每一个还没有担任过簇首的节点分别生成0～1之间的随机数，如果生成的随机数小于给定的阈值T(n)，则选择为簇首。T(n)的计算方法如下：
其中，p是簇首在所有节点中所占的百分比，r是选举轮数，G代表最近l/p轮中还没有当选过簇首的节点集合。
一旦节点被选定为簇首后，就向外发送簇首广播信息。非簇首节点根据收到的簇首广播信息的信号强弱决定要加入哪个簇，并向将要加入簇的簇首发送入簇请求。簇首在收到请求后将该节点加入自己的路由表并为每个节点设定一个TDMA定时消息，并且通知该簇中所有节点。此后的簇传输阶段，簇内节点按照该TDMA时间表与簇首进行通信，簇首节点接收簇内其他节点发送的数据，并将这些数据进行融合，然后发送给Sink节点。每隔一定时问，整个网络重新进入簇形成阶段开始新一轮的簇首选举过程。
1.2 LEACH算法的不足
LEACH协议采用层次结构，与平面路由相比简化了路径的选择及路由信息的存储，同时自适应随机选取簇首节点，利于实现全网负载的均衡。但是LEACH协议存在下列3个方面的问题，制约着网络能量的均衡消耗。
（1）节点担任簇首是严格的等概率选择，能量较低的节点一旦成为簇首很容易耗尽能量而死亡；
（2）每一轮通信结束后都要重新执行簇首选择和簇内、簇间路由的建立，导致了大量的能量消耗；
（3）簇首节点以单跳形式向基站传送数据，不仅会导致距离基站较远节点的能量消耗过大，也不利于网络的大规模扩展。
2 改进的算法PBCP
2.1 水声传感器节点能量模型
[4]给出了水声传感器节点数据通信的能量模型。设P0为数据包能被接收端正常接收的最低功率水平，x为数据包的传输距离(单跳距离)，则发送端发送数据包的最低功率可表示为：
式中，k为能量扩展系数，此处取 k=1.5；a=10a(f)/10，a与频率有关，由吸收系数a(f)获得，据Thorp表达式得：
则发送l bit的数据包，传输距离为x时发射端能耗为：
接收端接收这个数据包的能耗为：
式中，Pr为取决于设备的常数。
由上述能量公式可知，传感器节点的接收功率为一个常数，而发送功率随着传输距离x的增大呈指数级增长，因此缩短节点间的一跳传输距离成为节约节点能耗、延长网络生存时间的关键。
2.2 链路层协议
2.2.1 链路层协议的选择
与陆地传感器网络不同，水声传感器网络具有传输时延大、可用频带有限、严重的时变多途影响等。因此选取合理有效的链路层协议显得至关重要。链路层协议的基本任务是为传感器节点分配有限的水声信道资源，避免冲突。
由于水声信道为共享介质，节点发送数据的过程中可能会与其他节点发送的数据产生碰撞，造成发送包被丢弃，需重传发送的数据，导致碰撞节点发送这些数据消耗更多额外的能量，同时节点会接收并处理不必要的数据，然后再将其丢弃，造成节点的无线接收模块和处理器模块消耗更多的能量。因此需要考虑采用信道复用技术来合理分配水声信道。常用的信道复用技术包括频分多址FDMA、时分多址TDMA和码分多址CDMA[5]。由于水声信道的通信带宽非常有限，通常只有几千赫量级，基本无法使用频分多址技术实现多用户通信；而时分多址要求有时间保护间隔，且对时间同步的要求非常高，所以不适合大范围的水声通信；码分多址是实现水下多用户通信的可行技术选择[6]。
码分多址具有系统容量高、功耗低、抗干扰性好、抗多径衰落、保密安全性高、扩展性好等优点[7]。码分多址系统为每个用户分配了各自特定的地址码，利用地址码序列的正交性和准正交性来区分不同用户，在同频、同时的条件下，各接收机根据不同信号码型之间的差异分离出需要的信号[8]。
基于以上因素，本文考虑采用基于时分多址和码分多址的混合信道复用技术，即Sink节点采用一个彼此共知的CDMA扩频码（以下简称公共信道）与所有节点之间通信，每个簇内采用唯一的CDMA扩频码进行通信，避免簇间的信道冲突。簇内节点与簇首之间的通信采用时分复用技术，簇内节点只在规定的时隙向簇首节点发送数据。簇首与Sink节点之间进行多跳传输时每个簇首节点都将要传输的数据通过下一跳节点的跳频码字发送。
2.2.2 扩频地址码的分配
由于码分多址要求每条信道所采用的扩频地址码唯一，故考虑在簇首选出后由Sink节点对扩频地址码进行统一分配。簇首节点在收到分配给本簇的扩频码后将自身当选簇首的消息连同自身位置信息和该扩频码通过公共信道进行广播，为了避免多个簇首节点在同一时刻广播自己的消息造成信道冲突，本文考虑采用MACA协议中的RTS/CTS握手机制[9]：每个节点在当选簇首后通过公共信道向Sink节点发送一个RTS请求，Sink节点在收到所有的请求后为每个簇首节点分配一个唯一的CDMA扩频码，并按照请求的顺序依次给相应簇首发送携带其扩频码的CTS回应，簇首节点在收到CTS后，使用公共信道向全网广播自己当选簇首的消息，Sink节点在收到这一广播后继续给下一个簇首节点发送CTS回应,直到所有的簇首节点都将自己的消息广播出去。
2.3 网络模型假设
(1)水声传感器网络是同构网络，Sink节点没有能量限制；
(2)本文讨论的水声无线传感器网络为二维静态网络，不考虑节点的移动性；
(3)各节点的初始能量相等，各节点都有功率调节装置，可以根据距离的远近调整发射功率；
(4)传感器节点可以通过外部设施或是其他的定位机制获得其地理位置信息；
(5)每个传感器节点都有一个唯一的ID作为其在网络中的标识；
(6)网络规模较小，每个传感器节点的通信范围都可以覆盖整个网络。
2.4 改进算法的描述
2.4.1 簇首节点的选择
在每一轮的信息传递中，所有节点都把自身的当前能量值随采集到的数据信息发送给簇首，簇首在进行数据融合后连同自己的剩余能量信息发送给Sink节点，Sink节点在每轮通信结束后便掌握了所有节点的剩余能量信息。这样Sink节点便可以计算出当前网络中节点的平均能量Eavg并在发出开始下一轮簇首选举的命令中携带这一参数。所有节点在收到簇首选举命令后将自身能量E与Eavg进行比较，若E>Eavg，则参与簇首选举，反之，放弃选举簇首。簇首的选举依据式(6)：
每个节点生成一个0～1之间的随机数，如果生成的随机数小于T(n)，则选择为簇首。其中G为剩余能量E>Eavg的节点的集合。
2.4.2 簇内、簇间路由的建立
簇首节点选出后，所有当选簇首的节点如前文所述依次向全网广播自己当选簇首的消息，消息中包含自身的位置信息和所采用的CDMA扩频码。非簇首节点根据收到的簇首广播信息的信号强弱决定要加入哪个簇，采用该簇首的扩频码向其发送入簇请求并结合簇首位置信息和自身位置计算与簇首间的距离以确定向簇首发送数据时的发送功率。簇首在收到请求后将该节点加入自己的路由表并为每个节点设定一个TDMA定时消息，并且通知该簇中所有节点。
每一个簇首节点在收到其他簇首节点广播的消息后，根据其位置信息找到自己的前向簇首节点。判断方法如下：
(1)簇首节点先计算出与Sink节点间的距离：
(2)计算其他簇首节点与Sink节点间的距离：
(3)选 择 满 足 D(sink，this)>D(sink，clusteri)的 节 点 并对这些节点分别计算：
(4)若没有其他簇首节点满足 D(sink，this)>D(sink，clusteri)，则Sink节点为当前节点的下一跳。反之，从D(this，clusteri)中选出最小值 Dmin(this，cluster)，若 Dmin(this，cluster)
式(7)～式(9)中，s_x、s_y分别为 Sink节点的横纵坐标，t_x、t_y分别为当前簇首节点的横纵坐标，c_x、c_y为其他簇首节点i的横纵坐标。
2.4.3 完成一轮通信及开始下一轮通信
簇内、簇间路由建立完成后，Sink节点向全网发送传输开始指令开始一轮的数据传输阶段。所有簇内节点即按照自己的时隙在规定时间将收集到的数据连同自己的剩余能量值发送给簇首节点，簇首节点进行数据融合后将数据发送给自己的前向节点，直至所有数据都发送到Sink节点，一轮通信结束。开始下一轮通信。整个流程如图1所示。
图1 完成一轮通信后的处理流程
由于所选出的簇首节点能量均高于节点的平均能量，这样便可以保证整个网络的结构在一定时期内相对稳定。在出现了能量过低的簇首节点而执行簇内簇首重选时，只更改了本簇内的网络结构和上一跳簇首节点的路由表，分簇结构的主体结构并没有改变，避免了每轮重选簇首造成的大量能耗和长时延。
3 算法的仿真分析
3.1 仿真参数
为了验证PBCP算法的性能,在MATLAB环境中对PBCP和LEACH协议进行了仿真比较。网络规模为一个Sink节点和 100个sensor节点，分布在20 km×20 km的区域内。仿真参数如表1所示。
表1 仿真参数设置
3.2 仿真结果
图2显示了在第一轮簇首选举过后，整个网络的簇内、簇间路由（Sink节点位于仿真区域中心）。从中可以看出，每个普通节点都加入了距离自己最近的簇首节点所在的簇，簇首节点之间按上文所述的最小代价建立起以Sink节点为目的地的多跳连接。
从图3中可以看出，PBCP协议的死亡节点达到一半时，LEACH协议的节点数已经接近全部死亡。与应用LEACH协议相比网络生存期延长了约45%，并且大大推迟了第一个节点死亡的时间，仿真结果表明，应用PBCP协议能够有效节约节点能量，平衡网络负载，延长网络生存时间。
延长网络生命期成为水声传感器网络的一个热点问题。在路由协议中，合理地选择路由，对提高节点的能量效率，延长网络生命期十分重要。本文在LEACH算法的基础上，介绍了一种改进的路由算法PBCP，该算法在簇首选举过程中充分考虑节点的能量因素，避免剩余能量较低的节点成为簇首节点。下一步的研究包括：在簇首节点的选举中综合考虑能量位置等因素；保证簇首节点在地理上均匀分布；验证该协议在三维环境中的能耗性能；优化执行簇内簇首重选、簇结构重新建立的阈值参数等。
参考文献
[1]魏昕，赵力，李霞，等.水声通信网综述[J].电路与系统学报，2009，14(6)：98-106.
[2]张光旭.水声传感器网络可靠路由协议的研究[D].中国海洋大学硕士学位论文.青岛：中国海洋大学，2008.
[3]邢达波.水声传感器网络路由算法仿真研究[D].哈尔滨工程大学硕士学位论文.哈尔滨：哈尔滨工程大学，2009.
[4]SOZER E M，STOJANOVIC M，PROAKIS J G.Underwater acoustic networks[J].IEEE Journal of Oceanic Engineering，2000，25(1)：72-83.
[5]张林波，刘彤，刘国枝.水声通信网路由协议比较研究[J].哈尔滨理工大学学报，2004，9(5)：39-42.
[6]AKYILDIZ，POMPILI D，MELODIA T.Underwater acoustic sensor networks：Research challenges[J].Elsevier's Journal of Ad Hoc Networks，2005，3(3)：257-279.
[7]STOJANOVIC M.On the relationship between capacity and distance in an underwater acoustic communication channel[C].ACM WUWNet.Los Angeles：[s.n.]，2006：41-47.
[8]BANEOEE S，MISRA A.Minimum energy paths for reliable communication in multi-hop wireless networks[C].Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc).Lausanne：ACM，2002.
[9]LINDSEY S，RAGHAVENDRA C，SIVALINGAM K.Data gathering in sensor networks using the energy delay metric[C].In 15th IPDPS Workshop on Issues in Wireless Networks and Mobile Computing，2001.
