无线纳米传感网中基于概率的洪泛算法*

夏建川，张秀娟，王斯锋

（曲阜师范大学 信息科学与工程学院，山东 日照 276826）

0 引 言

无线传感器网络在军事和民用领域都具有重要的应用前景[1]。纳米技术允许纳米器件以纳米尺度收集，创建，计算，处理和传输数据。因此，采用纳米技术的无线纳米传感网能为健康监测、智慧城市、军事、农业和工业等众多应用提供新的解决方案。纳米节点具有能量有限、节点资源受限、分布性和多跳通信等特点。

基于电磁的纳米传感器是适合建立无线纳米传感网的器件。它使用基于石墨烯的天线，拥有纳米收发器，能够在0.1～10 THz波段传输和接收电磁波[2]。这种通信能力使得纳米传感器能够以同步、监督和合作的方式工作，实现共同的任务。当纳米传感器互联时，构成无线纳米传感网，可以使用广播和通信协议来控制它们。资源有限的纳米传感器之间可以用洪泛协议传播数据，但由于过多的数据包重传会浪费带宽，加大消耗能量。因此减少冗余传输是需要解决的主要问题之一。

本文第2节列出相关工作；第3节给出能减少冗余传输的详细算法；第4节是仿真结果及性能分析，并指出下一步工作方向。

1 相关工作

纳米传感器非常小，至多几百纳米，存储能力也有限。因此，纳米传感器没有存储路由表的存储能力，也没有查找路由表的处理能力。限于纳米传感器的存储、处理、能量的有限性，传统的路由协议不适于无线纳米传感网，简单的路由算法洪泛是合适的。洪泛算法中，每个节点将自己收到的数据包，广播给除了源节点之外的其它（传输范围内的）所有节点。它可以应用于无线纳米传感网，但直接的洪泛算法会引起广播风暴问题，导致大量数据包重传，丢失，造成冲突，增大消耗。许多学者通过分析或者仿真研究了广播风暴问题的危害[3]。文献[4]中针对纳米传感器沿着人体血液方向的环境中均匀移动情形，基于能量提出了贪心能量感知和最优能量感知两个数据包转发算法。贪心能量感知转发算法，每次选择当前具有最高能量的邻居节点进行转发，最终的能量消耗并不是最优的；而最优能量感知算法，从全局出发，每次选择能够最大化网络能量的节点进行转发，此算法需要全局信息。文献[5]中基于层次分簇架构提出了一个集中式路由框架。

综上所述，无线传感网中现有的非洪泛机制的数据包转发方案没有综合考虑纳米网中纳米特性、分布性特性等。

2 算法

鉴于以上的分析和研究，在本文中我们提出了基于概率的洪泛算法PBF（Probabilistic Based Flooding），用于无线纳米传感网的广播问题。PBF算法是一个分布式算法，每个节点独立运行算法。每个节点发送数据包d有三种情形。情形一，若节点监测的环境发生改变，自己产生数据包d需要发送出去，此时广播的概率为1。然后存储数据包d的ID号，对应flag标志置为true，目的是标记此节点已经广播过此数据包，下次再收到时降低概率发送。情形二，若节点收到数据包d并且对应flag标志为false,说明第一次收到数据包d，则以较高概率p1（属于[0.6,1]）将此数据包广播出去，若发送成功，对应flag标志置为true。情形三，若节点收到数据包d并且对应flag标志为true，说明以前此节点成功广播过此消息，则以较低概率p2（属于[0,0.6]）将此数据包广播出去。纳米节点的存储能力有限，已发送数据包ID和对应flag标志的存储按照最近最久未使用的算法进行淘汰。这里0.6的选取，只是使得p1为较高概率，p2为较低概率，并不影响算法的本质。

下面给出基于概率的洪泛算法PBF：

算法. PBF

对于每个节点，

1： IF 节点u生成数据包d

2： 以概率1广播，存储d的ID，对应flag标志置为true

3： ENDIF

4： IF 节点u收到数据包d并且对应flag标志为false

5： 以概率p1（属于[0.6,1]）发送，以概率1-p1不发送

6： IF 节点u发送数据包

7：d对应flag标志置为true

8： ENDIF

9： ENDIF

10：IF 节点u收到数据包d并且对应flag标志为true

11：以概率p2（属于[0,0.6]）发送，以概率1-p2不发送

12：ENDIF

3 性能评估

本文采用Nano-Sim进行算法的仿真。NS3是一个开源的网络仿真器，被广泛采用。Nano-Sim是运行于NS3之上的模块，可用于基于电磁的无线纳米传感网仿真。Nano-Sim是开源的、模块化的、可扩展的。它的物理接口采用TS-OOK调制方案、简单的MAC协议、一种基于洪泛技术的路由模块以及用于生成和处理消息的单元。纳米传感器节点随机分布在长方体区域。它们以20 cm/s的速度按选定方向随机移动。纳米接口部署于长方体中心，仿真期间位置固定不变。纳米节点收集自己周围环境信息，然后发送数据包给周围节点。数据包从一个节点广播到其它节点，直到纳米接口。脉冲能量、脉冲持续时间和脉冲间隔时间等物理层参数根据Nano-Sim的原始工作设定[6]。为了考察PBF算法在无线纳米传感网中的性能，将它与一般的洪泛算法进行比较。每组仿真取30次运行结果的平均值。

为了考察PBF算法在无线纳米传感网中的性能，我们主要关注以下三个指标：数据包传输率PDR（Packet Delivery Ratio）、延迟和能量消耗。数据包传输率PDR是实际接收的数据包数量与需发送的数据包数量比率。延迟是数据包从源节点到目标节点传输所花费的时间。数据包若需要大量路由和重传，会产生额外的能量消耗。接收的数据包数量和发送（包括转发）的数据包数量的比率与成功接收每个数据包的所消耗能量是成正比的，而网络中传输和接收数据包的总数量与此比率成正比。因此，能量消耗与网络中传输和接收数据包的总数量正相关。众所周知，能量消耗多，网络的生存期就短。

图1-图3考察节点个数的不同（反映密度）对三个指标的影响，传输范围取值为10 mm。图1的垂直线表示平均延迟。为了获得平均延迟，将所有传送成功数据包延迟的总和除以传送的数据包总数。结果表明，无论稠密网络还是稀疏网络中，洪泛算法和PBF算法性能接近，平均延迟大约75 ns。从图2中观察相同条件下两个算法的数据包传输率，发现稀疏网络中（节点个数从100～200）PBF算法此值低于100%，其余情况两个算法的数据包传输率都为100%。稀疏网络中PBF算法数据包传输率低，是因为数据包到达某节点，但因为按照一定概率转发，碰巧没有转发出去，稀疏网络中源节点和目标节点的通路本来就少，可能就没有通路了，这样此数据包就没有到达目的节点。

图1 传感器数目与平均延迟

图3给出了仿真时间内网络中所有节点传输和接收的数据包数量和，如果此值高，网络中节点的能量消耗大。从图中可以看到，PBF算法的发送和接收数据包总数要比洪泛算法低得多，也就是说使用此方案，有助于减少冗余广播，可以大大减少无线纳米传感网中数据包传输和接收次数，从而节省能量，延长网络使用寿命。我们的仿真沿用Nano-Sim的原始工作设定，没有考虑节点之间相互的干扰。洪泛算法引起的广播风暴问题，会造成大量重传。因此，若考虑实际运行中相互间的干扰，洪泛算法会造成数据包的丢失，传输的延迟，特别是在稠密网络中。若考虑干扰，稠密网络时，洪泛算法在图1中平均延迟可能增加，在图2中数据包传输率可能到不了100%。

图2 传感器数目与数据包传输率

图3 传感器数目与发送和接收数据包总数

图4 传输范围与发送和平均延迟

图5 传输范围与数据包传输率

图6 传输范围与发送和接收数据包总数

图4-图6中，固定取节点个数为400，考察传输范围对网络行为的影响。图4表明无论使用PBF算法还是洪泛算法，平均延迟的趋势基本一致。传输范围取值小，平均延迟小，原因是许多纳米节点不连通，导致许多数据包无法到达目标节点，所以平均延迟小。当传输范围为6 ns时，传送成功的数据包多了，但传输范围还不够大，从源节点到目标节点所需要的跳数多，所以平均延迟最高。随着传输范围变大，从源节点到目标节点所需要的跳数减少，平均延迟又开始降低了。图5中可见，两个算法仿真时平均数据包传输率PDR变化规律很类似，当传输范围为6 mm时，PDR达到或者接近100%。从图6中可知，无论传输范围为何值，PBF算法都能大大降低发送和接收数据包总数，也就是，大大减少了重复广播。

4 结 语

本文设计了PBF算法，通过引入概率试图减少数据包的重复转发。仿真结果表明，PBF算法和传统的洪泛算法平均延迟和数据传输率性能接近，而网络中传输和接收数据包的总数量大大降低。也就是说，PBF算法能大大降低传统的洪泛算法中数据包重复广播的次数，因此能减少能量消耗，提高网络生存期。下一步，我们会在Nano-Sim仿真中引入干扰模型，预计PBF算法在稠密网络中平均延迟和数据传输率还会好于传统洪泛算法，也会根据仿真情况进一步优化PBF算法。