这里写自定义目录标题
- Lines beginning with `#' are comments
目 录
第一章 无线传感器网络概述 6
概述 6
1.1 NS-2 6
1.2 OPNET 6
1.3 SensorSim 6
1.4 EmStar 7
1.5 GloMoSim 7
1.6 TOSSIM 7
1.7 PowerTOSSIM 7
第二章 Omnet＋＋简介 8
概述 8
2.1 OMNeT++框架 8
2.1.1 OMNeT++组成 8
2.1.2 OMNeT++结构 9
2.2 OMNeT++的安装 10
2.3 OMNeT++语法 11
2.3.1 NED语言 11
2.3.1.1 NED总概述 11
2.3.1.2 Ned描述的组件 11
2.3.1.3函数 13
2.3.2 简单模块 14
2.3.2.1 OMNET＋＋中离散事件 14
2.3.2.2 包传输模型 14
2.3.2.3 定义简单模块 15
2.3.2.4 简单模块中的主要成员函数 16
2.3.3 消息 17
2.3.3.1 cMessage类 17
2.3.3.2 消息定义 17
2.3.3.3 消息的收发 17
2.3.4 模块参数、门及连接的访问 18
2.3.4.1消息参数的访问 18
2.3.4.2门和连接的访问 19
2.3.4.3门的传输状态 20
2.3.3.4连接的状态 20
2.4 仿真过程 21
2.5 配置文件omnetpp.ini 22
2.6 结果分析工具 22
2.6.1 矢量描绘工具Plove 22
2.6.2 标量工具Scalar 22
2.7、结束语 23
第三章 物理层仿真（信道） 24
3.1 UWB的基础知识 24
3.1.1 UWB信号的应用背景 24
3.1.2 UWB信号的定义 24
3.1.3 UWB的脉冲生成方式(高斯脉冲,非高斯脉冲) 25
3.1.4 UWB的调制方式 25
3.1.5 用功率控制多址接入方法来进行链路的建立控制 27
3.2 用OMNeT++对UWB进行仿真 28
3.2.1 算法仿真的概述 28
3.2.2 算法的具体流程 30
3.2.3 算法的主要代码 31
3.2.4 仿真结果分析 43
3.2.5 应用前景 43
参考文献 44
第四章 MAC层仿真 44
概述 44
4.1 无线传感器网络MAC层特性及分类 45
4.1.1 无线信道特性 45
4.1.2 MAC 设计特性分析 45
4.1.3 无线传感器网络典型MAC协议的分类 45
4.2 基于随机竞争的MAC协议 46
4.2.1 S-MAC协议[12] 46
4.2.2 T-MAC协议 47
4.2.3 AC-MAC协议 48
4.3 基于时分复用的MAC协议 48
4.3.1 D-MAC协议 48
4.3.2 TRAMA协议 49
4.3.3 AI-LMAC协议 49
4.4 其他类型的MAC协议 49
4.4.1 SMACS/EAR协议 49
4.4.2 基于CDMA技术的MAC协议 50
4.4.3 DCC-MAC 50
4.5 基于OMNeT++的MAC层协议仿真 51
4.5.1 S-MAC协议的仿真 51
4.5.2 S-MAC协议流程图 52
4.5.3 S-MAC协议的分析 53
4.6 小结 63
参考文献 63
第五章 网络层仿真 64
概述 64
5.1 无线传感器网络路由协议研究 65
5.1.1 无线传感器网络协议分类 65
5.1.2 无线传感器网络中平面路由 66
5.1.3 无线传感器网络中层次化路由 67
5.1.4 经典算法的OMNET仿真 69
5.2 无线传感器网络路由协议研究的发展趋势 76
5.3 无线传感器网络层路由协议与OMNET++仿真 77
5.3.1 无线传感器网络层路由与OMNET++仿真的基本概念[19] 77
5.3.1.1 传感器网络的体系结构 77
5.3.1.1.1 传感节点的物理结构 77
5.3.1.1.2 传感器网络的体系结构与网络模型 78
5.3.2 传感器网络层路由协议的基本概念 79
5.3.2.1 网络通信模式[28] 79
5.3.2.1.1 单播： 79
5.3.2.1.2 广播： 79
5.3.2.1.3 组播： 79
5.3.2.2 传感器网络层设计[29] 80
5.3.3 OMNET++仿真软件的基本概念 81
5.4 无线传感器网络路由协议介绍 81
5.4.1 泛洪法(Flooding)[32] 82
5.4.2 定向扩散(Directed Diffusion：DD)[33] 82
5.4.3 LEACH( Energy Adaptive Clustering Hierarchy)[34] 83
5.5. OMNET++仿真实例 84
5.5.1 泛洪法 84
5.5.2 gossiping协议 88
5.6 本章总结 90
参考文献 90
第六章 应用层仿真 92
6.1 无线传感器网络节点定位 92
6.1.1 节点定位的基本概念 92
6.1.1.1 节点定位的定义 92
6.1.1.2 节点定位的重要性 93
6.1.2 节点定位的研究 93
6.1.2.1 测距方法 93
6.1.2.2 节点定位原理 94
6.1.2.3 节点定位算法分类 94
6.1.2.3.1 锚节点分类 94
6.1.2.3.2 计算方式分类 95
6.1.2.3.3 测距分类 95
6.1.2.3.4 节点移动性分类 96
6.1.2.4 节点定位性能评价[37] 96
6.1.3基于OMNET++的DV—Hop定位算法仿真 97
6.1.3.1 DV—Hop定位算法的基本思想 97
6.1.3.2 DV—Hop定位算法仿真 98
6.2 网络管理 105
6.2.1概叙 105
6.2.1.1 wsn网络管理的定义及范畴 106
6.2.1.2 wsn网络管理系统的分类 106
6.2.1.3 wsn网络管理系统的设计标准 107
6.2.2 wsn网络管理系统 108
6.2.2.1 能量管理系统 108
6.2.2.1.1 SenOs[5] 108
6.2.2.2 拓扑控制系统 109
6.2.2.2.1 TopDisc 算法 109
6.2.2.3 可调试、可配置、可编程系统 110
6.2.2.2.1 sympathy 系统[42] 111
6.2.2.2.2 Agilla系统[7] 111
6.2.3典型网络管理算法的Omnet 模拟 112
6.2.3.1 基于Wsn的一个简单拓扑查找算法算法模拟 112
6.2.4 结论 116
6.3 基于路由层安全协议的OMNeT++仿真 116
6.3.1 基础知识介绍 116
6.3.1.1无线传感器网络安全性的重要性和必要性 116
6.3.1.2 无线传感器网络的安全目标 116
6.3.1.3无线传感器网络中的路由协议概述 117
6.3.1.4无线传感器网络路由协议的攻击方法 117
6.3.1.5无线传感器网络中经典路由协议安全性分析 119
6.3.1.6 安全路由技术分析 121
6.3.1.6.1 密钥管理技术[20, 23, 24, 25] 121
6.3.1.6.2 安全路由协议 121
6.3.2 在OMNeT++ 中的仿真 122
6.3.3 总结 128
参考文献 129
第七章 实例（无线传感器网络移动节点定位仿真） 133
概述 133
7.1 移动定位算法介绍 134
7.1.1 室内移动节点定位算法 134
7.1.1.1 Active Badge系统 134
7.1.1.2 RADAR系统 134
7.1.1.3 Cricket系统 134
7.1.2 室外移动节点定位算法 135
7.1.2.1 基于静态定位的移动定位算法 135
7.1.2.2 纯移动定位算法 135
7.2 移动定位算法的OMNeT++仿真 136
7.2.1 MCL（Monte Carlo Localization）定位算法简介 136
7.2.2 MCL（Monte Carlo Localization）的OMNeT++仿真 138
7.2.2.1 建立网络拓扑 138
7.2.2.2 编码阶段 141
7.3.总结和发展趋势 145
参考文献 145
第一章 无线传感器网络概述
概述
集成了传感器、微机电系统和网络三大技术而形成的传感器网络是一种全新的信息获取和处理技术，具有广阔的应用前景。主要表现在军事、环境、医疗、家庭等商业领域，特别在空间探索和灾难拯救等特殊的领域有其得天独厚的技术优势。为评价传感器网络协议算法的性能，仅通过实验是无法实现的，特别是包含大量节点的大规模无线传感器网络，更是很难通过实验来实现(实际上，上百个节点的实验己经比较难以管理与实现)。
为了实现无线传感器网络的仿真，研究人员设计开发了许多的仿真平台(或在现有平台建立无线传感器网络模型)，包括NS-2, OPNET, SensorSim, EmStar, OMNet++, G1oMoSim, TOSSIM, PowerTOSSIM等。
1.1 NS-2
NS-2 (Network Simulator-2)是著名的用于网络研究的离散事件仿真工具，里面包括了大量的用于在有线或无线、本地连接或通过卫星连接进行TCP协议、路由算法、多播协议仿真的网络协议、调度器和工具。NS-2主要致力于OSI模型的仿真，包括物理层的行为。NS-2可以对仿真进行详细的跟踪并用仿真工具“网络动画播放器”C Network Animator (NAM)进行回放。NS-2是开放源码的自由软件，可以免费下载。有一些研究小组对NS-2进行了扩展，使它能支持无线传感器网络的仿真，包括传感器模型、电池模型、小型的协议栈、混合仿真的支持和场景工具等。由于NS-2对数据包级进行非常详细的仿真，接近于运行时的数据包数量，使得其无法进行大规模网络的仿真。
1.2 OPNET
OPNET建模工具是商业化的通信网络仿真平台。OPNET采用网络、节点和过程三层模型实现对网络行为的仿真。其无线模型是采用基于流水线的体系结构来确定节点间的连接和传播，用户可指定频率、带宽、功率和包括天线增益模式和地形模型在内的其它特征。OPNET提供了很多的模型，包括TCP/IP, 802.1 1 , 3G等。并已有一些研究人员在OPNET上实现对TinyOS的NesC程序的仿真。 但要实现无线传感器网络的仿真，还需要添加能量模型，而OPNET本身似乎更注重于网络QoS的性能评价。
1.3 SensorSim
SensorSim是建立在NS-2的一个采用DSR的802.11网络模型上的。SensorSim是用于WINS平台的，需要用SensorWare Tel脚本进行设计。SensorSim在仿真时跟踪了节点的能量使用情况，其能量模型来自WINS节点，使得其无法用于Mote平台的仿真。另外，SensorSim已经停止开发和支持，也无法下载到程序代码。
1.4 EmStar
EmStar提供了在仿真和基于iPAQ的运行Liunx的节点之间灵活切换的环境，用户可以选择在一个主机上运行多个虚拟节点进行仿真，也可以在一个主机上运行多个与真实的节点进行桥接的虚拟节点。EmSta:可以将无线传感器网络部署在一个友好的基于Linux的环境中，并进行跟踪和调试程序。EmTOS是用于在EmStar中进行TinyOS程序仿真的工具。 EmStar虽然不是一个真正意义上的无线传感器网络仿真工具，但却是一个很有用的用于对传感器网络的应用程序进行测试的环境。
1.5 GloMoSim
GloMoSim (Global Mobile Information Systems Simulation Library )是一个可扩展的用于无线和有线网络的仿真系统，根据OSI进行分层的建模设计。应用层、传输层、网络层、数据链路层、数据包接收模型、无线电模型和无线电波传播模型等不同的层次之间采用标准的APIs进行仿真。GIoMoSim采用Parsec进行设计开发，提供了对并行离散时间仿真的支持。G1oMoSim目前仅支持纯无线网络的协议仿真，可用于仿真传感器网络中的物理信道特征和数据链路协议的时延等特性。
1.6 TOSSIM
TOSSIM (TinyOS mote simulator)是用于对采用TinyOS的Motes进行bit级的仿真的工具。TOSSIM将TinyOS环境下的NesC代码直接编译为可在PC环境下运行的可执行文件，提供了不用将程序下载的真实的Mote节点上就可以对程序进行测试的一个平台。TOSSIM还提供了用于显示仿真情况的用户界面TinyViz.。TOSSIM的缺点是没有提供能量模型，无法对能耗有效性进行评价。
1.7 PowerTOSSIM
PowerTOSSIM是对TOSSIM的扩展，采用实测的MICA2节点的能耗模型对节点的各种操作所消耗的能量进行跟踪，从而实现无线传感器网络的能耗性能评价。PowerTOSSIM的缺点是，所有节点的程序代码必须是相同的，而且无法实现网络级的抽象算法的仿真。
第二章 Omnet＋＋简介
概述
目前，存在的网络通用协议十分有限。Ethernet普遍用于有线局域网，IEEE 802.11主要用于无线局域网，而TCP则为不可靠的媒质提供可靠的传输。然而，对于传感器网络来说，它没有这种权威的协议或算法，将来也未必能有，因为传感器网络通常是基于特定应用的。另外，无线传感器网络的设计需要同时考虑能量效率、容错率、同步、服务质量、调度方法、系统拓扑等的影响。因此，ns-2等网络模拟器对于无线传感器网络的仿真是有局限的。本书将介绍另一种新的网络模拟器OMNeT++ ( Objective Modular Network Testbed in C++)，并运用它进行无线传感器网络协议算法的仿真。
OMNeT++是Objective Modular Network TestBed in C++的英文缩写，它是开源的基于组件的模块化的开放网络仿真平台，是近年来在科学和工业领域里逐渐流行的一种优秀的网络仿真平台。OMNeT++作为离散事件仿真器，具备强大完善的图形界面接口和可嵌入式仿真内核，同NS2，OPNET和JavaSim等仿真平台相比，OMNeT++可运行于多个操作系统平台，可以简便定义网络拓扑结构，具备编程，调试和跟踪支持等功能。OMNeT++主要用于通信网络和分布式系统的仿真，目前最高版本为OMNeT3.3p1。
2.1 OMNeT++框架
2.1.1 OMNeT++组成
OMNeT++主要由六个部分组成：仿真内核库（simulation kernel library,简称Sim），网络描述语言的编译器（network description compiler, nedc），图形化的网络编辑器（graphical network description editor,GNED），仿真程序的图形化用户接口－Tkenv，仿真程序的命令行用户接口－Cmdenv，图形化的输出工具－Plove和Scalar。 Sim是仿真内核和类库，用户编写的仿真程序要同Sim连接，Sim在OMNeT++中占据最为核心重要的地位。下面详细介绍的另外两重要组成部分。
(1)．网络描述（NED）语言
NED是模块化的网络描述语言。网络描述包括大量的对组件的描述，如通道，简单和复合模块的类型。这些组件描述可用于各种不同的网络描述中。NED语言用来定义模型中的网络拓扑结构，较为简单的网络拓扑可以使用GNED，但复杂网络的拓扑描述还应该用NED源文件方式书写。
(2)．用户接口
OMNeT++的用户接口用于实现仿真程序的人机交互，OMNeT++允许模型内部机制对用户可视化，也允许用户启动和终止仿真，并更改模型内部的变量。OMNeT++中的图形化接口是一个用户工具，可方便用户了解模型内部的运行机制。
用户接口和仿真内核的交互是通过一个已定义的接口实现的。无需改变仿真内核，就可以实现不同类型的用户接口。同样无需更改模型文件，仿真模型可在不同接口下运行。用户以在强大图形化用户接口下测试和调试仿真程序，并最后可在简单快速的用户接口中运行，而且该接口支持批处理。
目前OMNeT++支持两种用户接口，即Tkenv和Cmdenv。对仿真进行的测试和调试可以在Tkenv接口下进行，Tkenv是一个简便易用的图形窗口化的用户接口，Tkenv支持跟踪，调试和执行仿真的功能。它在执行仿真过程中的任意时刻都能够提供详细的状态信息。Tkenv的主要特征有：各模块的文本输出有其独立的窗口，仿真过程中可以在Tkenv窗口中看到自传消息，支持仿真动画，标记断点，具有检查窗口，可以检查和改变模型中的变量，执行过程中仿真结果的图形化显示并且结果可以用柱状图和时间序列图显示，仿真可重新进行，快照文件用于显示模型的详细信息。
Cmdenv接口用于实际的仿真实验，因为Cmdenv支持批处理。Cmdenv是一个简便的小型命令行接口，执行速度快。它可以在所有操作系统平台上运行。Cmdenv可以一次批处理配置文件中所有的仿真。
2.1.2 OMNeT++结构
(1) OMNeT++具有模块化的结构，图1是OMNeT++仿真的高层体系结构。
图1的箭头表示两组件之间的交互，图中共有5个箭头，表示了组件间的5种关系。
(1)执行模型和Sim：仿真内核管理将来的事件，当有事件发生时，仿真内核就调用执行模型中的模块。执行模型的模块存储在Sim的main对象中。执行模型依次调用仿真内核的函数并使用Sim库中的类。
(2)Sim和模型组件库：当仿真开始运行创建了仿真模型的时候，仿真内核就实例化简单模块和其它的组件。当创建动态模块时，仿真内核也要引用组件库。实现在模型组件库中注册和查寻组件也是Sim的功能。
(3)执行模型和Envir：ev对象作为Envir的一部分，是面向执行模型的用户接口。仿真模型使用ev对象来记录调试信息。
(4)Sim和Envir：由Envir决定创建何种模型，Envir包含主要的仿真循环，并调用仿真内核以实现必须的功能。Envir捕捉并处理执行过程中发生在仿真内核和或类库中的错误和异常。
(5)Envir和Tkenv，Cmdenv：Envir定义了表示用户接口的TOmnetApp基类，Tkenv和Cmdenv都是TOmnetApp的派生类。main()函数是Envir的一部分，为仿真决定选用合适的用户接口类，创建用户接口类的实例并执行。Sim和模型对ev对象的调用通过实例化TOmnetApp类进行。Envir通过TOmnetApp和其它类的方法实现Tkenv和Cmdenv的框架和基本功能。
2.2 OMNeT++的安装
OMNeT++的安装环境:
a) Linux
b) 其他一些类似Unix的系统
c) Win32 平台 (NT4.0, Window 2000,XP)
本书主要讨论在windows平台下的仿真。
2.2在windows环境下，安装前需要安装好Visual C++ 7.0或具有 Service Pack 6支持的Visual Studio 6.0；
安装步骤
(1)从官方网站：www.omnetpp下载omnetpp-3.3-win32.exe安装包，开始安装
(2)在安装过程中，注意vc＋＋版本的选择。它有vc8.0、vc.7.0、vc6.0等选项，一般选择vc6.0 release。另外还有gswin32c路径的选择，ghostscript 主要用于打开或打印ps或pdf图形格式的文件。
(3)安装完毕后，应该先进行环境变量的设置。即：在vc6.0的bin目录下，找到VCVARS32.BAT文件，然后进入cmd下，运行即可
2.3 OMNeT++语法
OMNET++是面向对象的离散事件模拟工具,为基于进程式和事件驱动两种方式的仿真提供了支持。 OMNET++采用混合式的建模方式,同时使用了OMNET++特有的ned(Network Discription,网络描述)语言和C++进行建模。OMNET++的主要模型拓扑描述语言NED,采用它可以完成一个网络模型的描述。 网络描述包括下列组件:输入申明、信道定义、网络定义、简单模块和复合模块定义。使用NED描述网络，产生NED文件，该文件不能直接被C++编译器使用，需要首先采用OMNET++提供的编译工具NEDC将.NED文件编译成.cpp文件。最后,使用C++编译器将这些文件与用户和自己设计的简单模块程序连接成可执行程序。
2.3.1 NED语言
2.3.1.1 NED总概述
NED语言用来刻画定义模型的拓扑结构，方便对一个网络的模型化描述，这意味着一个网络的描述可以包括一组元件的描述（通道，简单/复杂模型），这些组件的描述可以在其他网络描述中得以重用。包含网络描述的文件带有.Ned的后缀，.Ned文件动态地载入到模拟程序，或者用Ned编译器或C++代码链接到模拟器执行。NED文件可以使用任何文本编辑器或GNED图形编辑器来编写。
2.3.1.2 Ned描述的组件
一个NED描述包括以下的组件（按任意次序排列）
(1)输入指示：用于引进其它网络描述文件，引进一个网络描述后，可以使用它所包含的模块通道等组件，当一个文件被引进，只有声明信息是可用的，并且引进一个D文件并不会使该NED文件被编译，当父文件被NED编译时，例如，你可以编译所有并连接所有的网络描述文件你可以用文件名（用NED扩展名也可），同样可以在文件包括一条路径或者用NED编译器的
如：import “ethernet”; // imports ethernet.ned
(2)信道定义：说明一个链接类型的特征，在信道申明中包含三个属性，它们都是可选项的：delay（每仿真秒的传输延时），error（比特错误率），datarate（信道带宽）。且三者出现的先后顺序没有限制。
如： channel LeasedLine
delay 0.0018 // sec
error 1e-8
datarate 128000 // bit/sec
endchannel
(3)简单模块和复合模块定义：
简单模块：它是复合模块的基本构建成分，它通过申明它的参数和门来定义。语法如下：
simple SimpleModuleName
parameters:
//…
gates:
//…
endsimple
复合模块：它由一个或多个子模块组成。不管是简单模块还是复合模块都可以用做子模块。它们也都能有门和参数，在简单模块能够使用的任何地方复合模块都能使用。相对于简单模块，它还有两个部分：子模块和链接。语法如下：
module CompoundModule
parameters:
//…
gates:
//…
submodules:
//…
connections:
//…
endmodule
其中任意部分（参数，门，子模块，链接）都是可选项。
(4) 网络定义：模块声明只定义了模块类型，要确实地获得一个仿真器能运行的模块，需要书写网络定义，网络定义将前面定义的模块类型声明为一个仿真模块实例，尽管可以将一个模块作为自包含的简单模块并实例为一个网络，你可能更想使用复合模块类型。在NED文件中可以有几个网络定义仿真程序，使用NED文件可运行其中任何一个，你可以在配置文件时选择最想使用的那个，网络定义的语法如下：
network wirelessLAN: WirelessLAN
parameters:
numUsers=10,
httpTraffic=true,
ftpTraffic=true,
distanceFromHub=truncnormal(100,60);
endnetwork
wirelessLAN是前面定义好的复合模块的名称，它应该包含关于wirelessHost，wirelessHub等类型进一步的复合模块的定义。自然地，只有模块类型可以使用在网络定义中，与子模块定义一样，不需要对它所有的指针赋值。
图2：OMNeT＋＋中的简单模块和复合模块
2.3.1.3函数
在NED表达式中，可以使用以下数学函数：
(1)C语言中<math.h>库函数：exp( ),log( ),cos( ),floor( ),ceil( )等等。
(2)产生随机变量的函数：uniform, exponential, normal等等。
表达式可以包含不同类型的随机变量，指针类型（除了const）返回不同的值，每次被计算。如果声明为const类型，指针值只在仿真开始的时候计算一次，以后的访问返回相同的值，随机变量程序用随机数字生成其中的一个，缺省为genertor0。
函数描述如下表：
(3)用户自定义函数：
要使用用户自定义的函数，需C++代码带有0，1，2，3，4个参数（double型），返回double型的值，函数要在C++文件中用Define_Function（）macro注册。例如：
例：
#include <omnetpp.h>
double average(double a, double b)
{
return (a+b)/2;
}
Define_Function(average, 2);
2表示average()函数有2个参数。这样定义之后，average()函数就能用于NED文件了。
module Compound
parameter: a,b;
submodules:
proc: Processor
parameters: av = average(a,b);
endmodule
如果参数类型不是double，可以进行类型转换。另外，简单模块类型名（#include 包含）要利用Define在OMNeT++中注册，允许类名与NED定义的简单模块名不相同。
2.3.2 简单模块
2.3.2.1 OMNET＋＋中离散事件
一个离散事件系统是指一个系统的状态改变是离散的，在两个连续的事件之间没有任何事件发生。简单地说，事件规定了系统状态的改变，状态的修改仅在事件发生时进行。离散事件系统可以使用离散事件模拟进行仿真。例如，计算机网络通常被看作是离散事件系统。部分事件包括：
包传输的开始
包传输的结束
重传等待时间到达
事件发生的时间通常被称做事件时间戳，在OMNET中叫做到达时间。模拟时间或虚拟时间是指模拟程序运行了多长时间，相对地，真实时间或cpu时间是指多少cpu时间被消耗。
OMNET＋＋使用消息来描述事件。每一事件都通过一个cMessage类或它的一个子类来表示；不存在单独的事件类。消息从一个模块发送到另一模块——这意味着“事件将发生”的地方就是消息的目的模块，事件发生的模拟时间就是消息到达时间。像“等待满期”事件通过模块给自己发送一个消息而实现。
OMNET++中的模拟时间被存储在C＋＋类型的simtime_t中，是双精度类型。
2.3.2.2 包传输模型
(1) 延迟，比特误差率，数据速率
可以被三个指针赋值的连接便利了通信网络建模，对其他的模型来说也非常有用。
• propagation delay (sec)
• bit error rate (errors/bit)
• data rate (bits/sec)
所有的这些指针都是可选的，你可以为每一个连接指定链接指针，也可以定义链接类型，并在整个模型中使用。传播延迟是消息通过通道到达目的地的时间段，传播延迟以秒为单位计算。比特误差率对消息的传输有影响，比特误差率就是一个比特被错误传输的机率。
一条有N比特的消息，没有错误的比特长度：
Pnobiterror = (1 − ber)length
消息有一个错误标志。
数据速率的单位bits/second。
消息的发送时间与传输的第一个比特和接收的最后一个比特相关。（图3）
图3 消息传输
上面的模型不能模拟所有的协议。在Token Ring 和 FDDI协议中，站发送重复的比特直到整个帧到达。如果一条消息沿途经过一系列的链接与模块。模块的行为好像每一个模块都在等待消息的最后一个比特到达，然后开始发送。因为上述的影响是不期望的，你更希望数据通过只有一个链接的路由来传播。
2.3.2.3 定义简单模块
(1) 直接或间接定义一个CSimpleModule的子类；
(2) 以define_Module() 或define_Module_Like()宏注册之；
a) 作用：声明一个simple module 类型并且建立与相应NED文件的关联。前者用于类名与NED定义的SimpleModule名相同，后者用于不同，可以为一个NED描述的SimpleModule提供不同的实现。
b) 每个SimpleModule都必须手动添加该宏，CompondMoudule由OMNeT自动添加。
(3) 实现模块类：
例子：
#include <omnetpp.h>
// module class declaration:
class SlidingWindow : public cSimpleModule
{
Module_Class_Members(SlidingWindow,cSimpleModule,8192)
//构造函数
virtual void activity();
};
// module type registration:
Define_Module( SlidingWindow );
// implementation of the module class:
void SlidingWindow::activity()
{
int windowSize = par(“windowSize”);
…
}
相关的NED文件
// file: swp.ned
simple SlidingWindow
parameters:
windowSize: numeric const;
gates:
in: fromNet, fromUser;
out: toNet, toUser;
endsimple
(4) 建立构造函数：
使用宏Module_Class_Members(classname, baseclass, stacksize);
如果你使用activity()，这个模块以协同模式执行， 需要划分出一个独立的栈空间。若栈空间为0使用handleMessage()。
需要变量参与初始化，需要自己重写构造函数。
2.3.2.4 简单模块中的主要成员函数
(1) activity()
它使得你可以象编写一个进程、线程一样编写一个简单模块。等待消息、延缓执行时间等等。拥有这个函数的简单模块们作为一系列协同程序协同执行，又称之为协同多任务。手动设置模块栈空间，一般为16k，如果模块存在递归或本地变量占空间较大的话，可以设置为更大的栈空间。
(2)handleMessage()
a)为每个message / event调用handleMessage()。
b)你需要在initialize()函数中初始化变量，一些基于协同的函数如wait()、receive()等均不能调用。
c)SimpleModule的stacksize一定要设置为0。
在事件处理中被调用，对每一个简单模块，用户需重定义该函数。在其中可以使用一些消息相关函数send（）（发送消息）、scheduleAt（）（自发消息）、cancelEvent（）（删除scheduleAt（）的消息）。
(3)Initialize()
在初始化消息放入FES(Future Event Set)后，在执行前被调用，初始化成员变量。复合模块的初始化先于其子模块。
(4)Finish()
循环结束(FES没有模拟事件时)后正常中止时被调用，模块的调用顺序刚好与initialize()相反。
2.3.3 消息
2.3.3.1 cMessage类
cMessage是OMNET＋＋的一个中心类。CMessage和子类的对象可以模拟一些东西：事件；消息；包；帧；蜂窝；网络中的位或信号传输；系统中的实体传输等等。一个cMessage对象有许多属性如下：
a) 名字是string(const char *)类型，在模拟程序中自由使用。消息的名字出现在Tkenv（如:动画中）的许多地方，因此选择一个描述性的名字非常必要。这个属性继承于cObject。
b) 消息类型被假定为携带一些消息类型信息。0或正值可以被自由使用。负值被OMNET仿真库保留起来以供使用。
c) 长度被用于计算当消息经过一个赋值了数据速率的链接时的传输延时。
d) 位错误标记被仿真内核以1−(1−ber)length的概率设置为真，当消息被发送经过一个赋值了位错误率（ber）的链接的时候。
e) 优先权被仿真内核用来在具有相同到达时间值的消息队列（FES）中定制消息。时间戳不被仿真内核使用。
2.3.3.2 消息定义
假设你需要一些消息对象来携带源和目的地址，还有跳数。你可以写一个mypacket.msg文件如下：
message MyPacket
{
fields:
int srcAddress;
int destAddress;
int hops = 32;
};
消息子集编译器的任务是生成C＋＋类，像允许Tkenv检查这些数据结构的“reflection”类一样，你可以从你的模型中使用。
如果你使用消息子集编译器来处理mypacket.msg,将创建以下文件：mypacket_m.h和mypacket_m。mypacket_m.h包含Mypacket C＋＋类的申明，field（域）中支持以下数据类型：
(1) 原始类型：bool, char, short, int, long, unsigned short, unsigned int, unsigned
long, double, string，一个动态定位string，以contst char *呈现。
(2) 结构，类（根于或不根于cObject），消息句法中或外部C＋＋代码中被申明。
2.3.3.3 消息的收发
OMNeT中，模拟就是一系列简单模块间通过message进行通信。
(1)普通发送：
send(cMessage *msg, const char *gateName, int index=0);
send(cMessage *msg, int gateId);
isBusy(); transmissionFinishes()；
(2)广播和重传：
不能使用send()发送同一个message多次。
Why：消息就是一个具体的对象，它不能在同一时间出现在不同的地点。一旦被源端送出，该消息就不再属于源端，到达目的端后，目的端就有对该消息的一切控制权如转发、删除、接收。
(3)延迟发送：
a)Wait();send(msg,”outgate”);
b)sendDelayed(cMessage *msg, double delay, const char *gate_name, int index);
c)sendDelayed(cMessage *msg, double delay, int gate_id);
d)送出时间是当前的模拟时间＋延迟时间；
E.g：sendDelayed(msg, 0.005, “outGate”);
(4)自传消息：
例如消息超时重传、job结束等等，这些源自于模块内部的事件，要由模块自身产生发给自己的消息来触发。
a)使用scheduleAt()发送自传消息；
scheduleAt(absoluteTime, msg);
scheduleAt(simtime()+delta, msg);
b)和普通消息一样接收；
c)isSelfMessage()：判定是否自传消息；
例：实现timer
cMessage *timeoutEvent = new cMessage(“timeout”);
scheduleAt(simTime()+10.0, timeoutEvent);
//…
cMessage *msg = receive();
if (msg == timeoutEvent)
{
// timeout expired
}
else
{
// other message has arrived, timer can be cancelled now:
delete cancelEvent(timeoutEvent);//从FES中删除
}
2.3.4 模块参数、门及连接的访问
2.3.4.1消息参数的访问
调用cModule 的par()成员函数可以访问模块指针：
cPar& delayPar = par(“delay”);
cPar类是一个存储值的对象，它支持数据类型，指针值可以这样读：
int numTasks = par(“numTasks”);
double processingDelay = par(“processingDelay”);
如果指针上一个随机变量或者指针值可以改变，最好存储指针的索引，在需要时重新读取指针的值。
cPar& waitTime = par(“waitTime”);
for(;?
{
//…
wait( (simtime_t)waitTime );
}
如果NED source 或者ini 文件对wait_time指针赋予了一个随机值，上面的代码导致不同的延时。指针值可以在程序中改变。如果指针通过索引引用，其他模块也可以看到它的变化。指针可以作为模块间通信的方法。
par(“waitTime”) = 0.12;
Or:
cPar& waitTime = par(“waitTime”);
waitTime = 0.12;
2.3.4.2门和连接的访问
（1）简单模块门
门实现模块的连接。OMNET++支持单向的简单线路，因此有输入门输出门，消息从输出门发出，在输入门接收。门用标识符识别，以字母开头，支持门向量，一个门向量包含一组简单的门。门声明在gates关键字后，一个空括号[ ]表示门向量，向量元素个数从0开始。例：
当简单模块被用作复合模块类型的组件时，门向量的大小被给定，因此模块的每个实例都可以有不同大小的门向量。例：
simple NetworkInterface
parameters: //…
gates:
in: fromPort, fromHigherLayer;
out: toPort, toHigherLayer;
endsimple
simple RoutingUnit
parameters: //…
gates:
in: output[];
out: input[];
endsimple
(2) 连接
①一个连接：
·包含属性（延迟，比特出错率，数据速度）或使用命名的通道（频道）；
·可能出现在一个for循环中（生成多重连接）；
·可能是有条件限制的；
②通道
如果不指定通道，连接就没有传输时延，传播时延与比特出错率，例如：
node1.outGate --> node2.inGate;
在这种情况下NED源必须包含有通道的定义，可以直接指定通道指针。
node1.outGate --> error 1e-9 delay 0.001 --> node2.inGate;
③循环连接
如果使用门向量与子模块，就可以在一种场合中使用多个连接，多连接用for循环创建。
for i=0…4 do
node1.outGate[i] --> node2[i].inGate
endfor;
上面循环连接在图4中刻画。
图4 循环连接
2.3.4.3门的传输状态
isBusy()成员函数返回门当前是否正在传输。
transmissionFinishes()返回传输结束的时间。例如：
cMessage *packet = new cMessage(“DATA”);
packet->setByteLength(1024); // 1K
if (gate(“TxGate”)->isBusy()) // if gate is busy, wait until it
{ // becomes free
wait( gate(“TxGate”)->transmissionFinishes() - simTime());
}
send( packet, “TxGate”);
如果简单模块的输出门并没有与连接直接相连，那就需要检查路由中的第二个门是否繁忙。
if (gate(“mygate”)->toGate()->isBusy())
如果数据率在仿真中改变，改变只影响后来发生的消息。
2.3.3.4连接的状态
isConnected()成员函数返回门是否连接。如果是输出门，则由toGate()成员函数返回连接的门。如果是输入门，成员函数为fromGate()。
cGate *gate = gate(“somegate”);
if (gate->isConnected())
{
cGate *othergate = (gate->type()==’O’) ?gate->toGate() : gate->fromGate();
ev << "gate is connected to: " << othergate->fullPath() << endl;
}
else
{
ev << “gate not connected” << endl;
}
要明确输出门最终与哪个模块相连，你可以按照下面的路径进行：
cGate *gate = gate(“out”);
while (gate->toGate()!=NULL)
{
gate = gate->toGate();
}
cModule *destmod = gate->ownerModule();
sourceGate() and destination-Gate()成员函数也可以方便地完成这项工作。
2.4 仿真过程
仿真执行文件是一个独立的程序，因此它可以运行在其他没有OMNET++或现存模型文件的机器上。当程序被启动，它就开始读配置文件（omnetpp.ini）。这个文件包含一些设置——控制仿真程序怎样执行，模型参数值等等。配置文件也能够规定一些仿真运行；最简单的情况下，它们一个接一个地被仿真程序执行。
仿真输出被写进数据文件中：vector矢量文件，scalar标量文件，和用户输出文件。OMNET提供了一个名为Plove的GUI工具来观察和绘制vector输出文件的内容。不期望人们单独地使用OMNET＋＋对结果文件进行处理：输出文件是一种能被读进像Matlab或Octave的数学包格式的文本文件，或被输入像OpenOffice Calc，Gnumeric 或MS Excel的电子数据表。所有这些外部程序为统计分析和清晰可见提供了丰富的功能性。
仿真编译过程如下：
nedtool *.ned ————————将ned文件编译成_n文件。
opp_msgc .msg————————将.msg文件编译成_m.h和_m文件。
opp_nmakemake -f -e cc（cpp）——对目录下的所有cc（cpp）文件进行编译，cc或cpp决定于你目录下的文件。若都有，必须都进行编译。之后生成Makefile.vc文件。
nmake -f Makefile.vc——————生成可执行文件
2.5 配置文件omnetpp.ini
该文件使得模拟程序得知将要仿真的网络，并通过该配置文件传递一些参数。
可分为以下几部分：
【General】——包含适应于所有模拟运行的常规设置和所有用户界面。
【Run 1】,【Run 2】，….——包含每一运行设置。这些部分可能包含任意在其他部分中被承认的实体。
【Cmdenv】——包含Cmdenv专门设置。
【Tkenv】——包含Tkenv专门设置。
【parameters】——包含在NED文件中没有赋值的模块参数值。
【OutVectors】——输出矢量的配置记录。你可以通过矢量名称和模拟时间来指定过滤。
2.6 结果分析工具
2.6.1 矢量描绘工具Plove
Plove特征：
Plove是描绘OMNET++输出矢量的一个便利的工具。每个矢量的线性跟轴边界，缩放比例，标题和标注一样被设置为最频繁的绘图选项。你可以点击一下将图保存到文件中去。在windows中，可以将图片复制到矢量格式的剪切板中，然后粘贴到其他的应用程序中。绘图之前先对结果进行过滤是可能的。过滤能够平均化，切断极限值,通过计算柱状形可进行密度估计等等。启动时，Plove自动读你有效目录下的.ploverc文件。这个文件包含了一般的应用设置，包括你创建的滤波器。
Plove使用：
首先，在左边方框中加载一个输出矢量(.vev)文件。可以通过点击中间的向右箭头将左方框内的矢量复制到右方框中。PLOT按钮将开始绘制右方框内所选
矢量。在windows下是这样选定的：shift+左键拖选定一个区域，ctrl+左击选定/取消选定个别项。要调整图形风格，改变矢量的标题或增加一个滤波器，点击
Options……按钮。这也适应于一些选定的矢量。左方框作为你正在运行的矢量存储器。你可以加载许多矢量文件，删除你不想处理的矢量文件，对它们重命名等等。这些改变不会影响矢量文件或磁盘。(Plove从不会自身修改输出矢量文件)在右方框内，如果你想要过滤矢量，你可以复制它们也可以保存最初的矢量文件。如果你为一个矢量设置了正确的选项，但是暂时还不想它留在右方框内，你可以把它送回左方框内存储起来。
2.6.2 标量工具Scalar
输出矢量捕获了仿真运行的瞬时行为。但是，为了比较多样的参数设置下的模型行为，输出标量更有用。
输出标量格式，使用recordScalar()函数调用来记录标量结果，通常来自模块的finish()方法，代码如下：
void EtherMAC::finish()
{
double t = simTime();
if (t==0) return;
recordScalar(“simulated time”, t);
………………………….
}
相对应的输出标量文件(默认,omnetpp.sca)大致如下：
run 1 “lan”
scalar “lan.hostA.mac” “simulated time” 120.249243
scalar ……………
………………
run 2 “lan”
scalar “lan.hostA.mac” “simulated time” 235.678665
[…]
每次调用recordScalar()在文件中都产生一”scalar”行。另外，一些仿真运行可以将它们的结果记录到一个单个的文件中----进行比较，创建x-y绘图，等等。
2.7、结束语
本章详细介绍了OMNeT++这个优秀的网络仿真平台，它主要用于离散事件的模拟。OMNeT++相对其它网络模拟器来说，使用是较为简单，但其使用方法仍然有其特殊性和复杂性。本章详细介绍了如何使用OMNeT++，对其体系结构，编程语法以及建模过程都作了详细介绍与深入剖析。
OMNeT++作为传感器网络的仿真平台具有显著的优势，具体包括：
OMNeT++支持用户组件库，实现了模块类型的灵活重用。
OMNeT++的面向对象特性，允许仿真内核提供基类的灵活扩展。
OMNeT++提供了图形化的网络编辑器和网络、数据流查看工具。
OMNeT++提供仿真类库和用户界面，支持输入/输出、仿真数据的图形化显示、随机数生成器、消息结构等。通过用户界面，可以跟踪调试仿真过程。
仿真环境采用C++语言开发，并采用自定义的配置文件omnetpp.ini进行配置定义。
OMNeT++在仿真802.11的MAC和Directed Diffusion协议时，比其他的网络仿真工具要快。
第三章 物理层仿真（信道）
3.1 UWB的基础知识
3.1.1 UWB信号的应用背景
传统的无线电技术都是基于载波的。但是将信号调制到载波上面，需要在发送端进行调制，接收端又要进行解调。这就增加了硬件的复杂度。而且发射载波需要较大的功耗。这对移动终端的移动性能造成了极大的影响。在这些背景之下，美国联邦通信委员会（FCC）定义民用的UWB技术。UWB技术是一种与传统技术有很大不同的无线通信技术，其特点是低功耗、高带宽、低复杂度。超宽带技术解决了困扰传统无线技术多年的有关传播方面的重大难题，它具有对信道衰落不敏感、发射信号功率谱密度低、安全性高、系统复杂度低，能提供数厘米的定位精度等优点。UWB尤其适用于室内等密集多径场所的高速无线接入和军事通信应用中
3.1.2 UWB信号的定义
信号带宽大于500MHz，或信号带宽与中心频率之比大于25％为超宽带；信号带宽与中心频率之比在1％～25％之间为宽带，小于1％为窄带，可见UWB的带宽明显大于目前所有通信技术的带宽。见下图：
信号的相对带宽定义如下
如果相对带宽 大于0.20～0.25，我们就认为它是一个超宽带信号。
超宽带的传输方式一般是无载波的。传统的"窄带"和"宽带"都是采用无线电频率（RF）载波来传送信号，载波的频率和功率在一定范围内变化，从而利用载波的状态变化来传输信息。相反的，超宽带以基带传输。实现方式是发送脉冲无线电（IR）信号传送声音和图像数据，每秒可发送多至10亿个代表0和1的脉冲信号。这些脉冲信号的时域极窄（0.1至1.5纳秒），频域极宽（数Hz到数GHz，可超过10GHz），其中的低频部分可以实现穿墙通信。信号的发射功率都十分低，仅仅相当于一些背景噪音，不会对其他窄带信号产生任何干扰。由于UWB系统发射功率谱密度非常低，因而被截获概率很小，被检测概率也很低，与窄带系统相比，有较好的电磁兼容和频谱利用率。此外，传统的无线通信在通信时需要连续发出载波（电波），要消耗不少电能。而UWB是发出脉冲电：直接按照0或1发送出去。由于只在需要时发送出脉冲电波，因而大大减少了耗电量（仅为传统无线技术的1/100）。UWB信号的功率谱密度极低，发射系统比现有的传统无线电技术功耗低得多；数据传输速率极高；非常可贵的对其他无线系统的低干扰特性；很强的抗多径干扰能力；比构造扩频系统简单，成本低。
IEEE802.11a Bluetooth UWB
传输速率 54Mbps 小于1Mbps 可高达500Mbps
通信距离 10m-100m 10m 小于10m
发射功率 1瓦以上 1毫瓦-100毫瓦 1毫瓦以下
应用范围 无线局域网 计算机等家庭和办公室设备互连 近距离多媒体
表1 ：各种无线技术的参数比较
3.1.3 UWB的脉冲生成方式(高斯脉冲,非高斯脉冲)
传统的UWB信号是用高斯脉冲来产生。一个高斯脉冲的时域波形如下：
也可以用它的导数来产生波形，一般用上式的一阶或者二阶三阶导数来产生超宽带脉冲（参看文献[10],[11]）。
3.1.4 UWB的调制方式
A ：直接序列扩频UWB （DS－UWB）
B ：跳时超宽带 （TH－UWB）
C ：多频带超宽带
在文献[1]中采取了TH-PPM的调制方式。有关的这种调制的知识可以参考该文献。这里采用TH-PAM调制，也就是跳时码+二进制反极性调制。因为二进制反极性码具有比PPM码更好的性质。在相同的误码率要求下，二进制反极性信号的发射功率只是二进制正交PPM调制的一半。文献[10]，[11]).因此可以采用TH+PAM的调制方式。
这种调制方式如图所示：
在这种调制中，时间被分为一个个帧，每个帧的时间为，每个帧由个时隙构成，在这里=7。每个时隙时间为。因此=。一个信息比特用个脉冲表示，在这里=4。一个用户在一个帧内只发送一个脉冲。因此用户A的一个信息比特要在上图的四个帧发送完后才完全接收。
在上图可以看到，用户A 的TH码是{0 1 5 3}，因此，用户A在第一个帧的0时隙检测，为了区分信息比特，在这里采用了二进制反极性PAM调制。这里第一个帧内检测到的脉冲为-1。同理，接收机在第二个帧的第1时隙，第三个帧的第5时隙，第四个帧的第3时隙分辨检测，得到的信号分别为+1，+1， -1。至此，A用户的一个信息比特所代表的脉冲全部检测完成，为{-1 +1 +1 -1}
根据超宽带信号的信号特点，假设系统中有N个用户，那么链路i的信噪比的公式如下所示（文献[1]）：
1.1
其中，
N是活动链路的个数.
为一个个帧的时间
为第i链路的比特信息速率
是从发送节点j到接收节点i的链路增益.
是第i链路的接收节点的背景噪声的功率谱密度.
是UWB脉冲的形成因子
一个比特用个脉冲来表示，一个帧的时间为，这样一个比特完全发送完毕用的时间为= 这样,比特速率为：
= 1.2
平均功率. 1.3
其中，为第i条链路在一帧内发送的功率，为第i链路的一个脉冲的能量。因此，为了改变i链路的功率，可以通过改变脉冲的能量，或者改变来实现.其中的改变又可以分为改变或者来实现。
3.1.5 用功率控制多址接入方法来进行链路的建立控制
在建立链路时候的多址接入方式采用了一种改进的的基于MEI 的分布式功率控制信道接入算法。本文考虑的网络拓扑是ad-hoc形式的网络，.各条链路之间不需要同步，仅仅需要接收点和发送点之间的同步即可。对于发射功率的上界，由于UWB工作的频段都是未经授权的频段，如果UWB的发射功率不经控制的话，很有可能对别的系统造成干扰。所以我们必须考虑发射功率的上界。在这里采用FCC的规定。
为了方便描述功率控制接入算法，这里首先引入”最大能忍受干扰”(MEI)的概念。 ”最大能忍受干扰” 也就是一个链路为了保持正常的通信QoS而能忍受的最大的额外的干扰。.假如链路i 的目标最小信噪比为，根据超宽带信噪比公式1.1，得下面的计算MEI的公式：
1.4
每个链路，定时检测自己周围的干扰情况，以及自己的,等信息，通过上式就可以算出自己的。
当一条新的链路要建立的时候，假设此时系统中已经有N个活动的链路,每个链路都已经算出自己的，并且定时将这些信息通过广播信道发送出去。
当一条新的链路(假设是第N+1条链路)要建立时，它首先监听出所有的链路的，.假设第N+1条链路的信噪比和速率要求分别为：和,由：
1.5
可以算得为了保证以速率发送,最小的功率要求为
1.6
但是,前面已经知道，系统中已经存在N条活动的链路，这些链路的优先级是比新链路高的，于是,第N+1条链路建立的时候,必须保证已经存在的链路的正常通信。于是第N+1条链路首先计算出
并且考虑到FCC的功率掩蔽，得出外界对N+1链路的功率上界限制为：
对比 与
如果，则可以成功建立新链路。
否则无法建立新链路，进入等待状态。经过一个随机的实验后再进行接入尝试。这样如果经过一个time out以后还无法建立，则N+1链路会将该问题交给高层处理,或者降低速率的要求。
当=时，显然链路N+1以发送。
当<，最佳的发送功率是。为了计算出，文献[1]中设计了一种平衡的MEI算法。但是该算法过于复杂。为了简单性，我们采取了一种折中的办法，取.经仿真，这种方法也可以得到很好的效果。
3.2 用OMNeT++对UWB进行仿真
3.2.1 算法仿真的概述
OMNeT＋＋是一个强大的网络仿真器件，关于它的使用说明，请参看安装目录doc/下面usman手册。在这里我们介绍一下如何用它来进行物理层的UWB功率控制算法的仿真。在进行功率控制算法的设计的时候，必须考虑UWB的信号模型，干扰模型，多径传播模型，自由空间传播模型等等。仿真的结果如下图所示：
图 1 仿真的网络拓扑图
这个程序主要包括两个部分，第一个部分是自定义的一个message类powerMsg，用来携带功率控制的信息，如功率大小，链路增益，信噪比，节点的状态信息（空闲或者忙碌）等等。第二个部分就是实现具体算法的详细代码。仿真的输出如下图所示：
图2 仿真的输出：
3.2.2 算法的具体流程
发送节点：
1.初始化一个链路建立请求，并发送请求信息给RX节点。
2.计算本节点在不干扰现存的其它链路的情况下，能运用的最大发送功率Pmax。
3.如果收到RX节点的应答最小功率要求Pmin，则进入4，否则等待。
4.进行比较，如果Pmin≤Pmax，则说明这条链路可以成功建立，转入5，否则链路无法建立，经过一个随机的时间后，返回1的初始化步骤。
5.计算最优功率Popt，并发送给链路成功建立的状态信息给RX节点。
6.开始发送数据。
接收节点：
1.检查自己的接收缓冲，如果收到TX的初始化链路请求信息，则转入2，否则返回1。
2.计算出自己为了维持所需的信噪比，需要的最小功率Pmin。并发送给TX。
3.如果收到TX的成功建立链路的信息，则进入4。否则返回1。
4.开始接收数据。
这个算法的流程图如下图所示：
图3 算法的流程图
3.2.3 算法的主要代码
基于活动链路保护的UWB功率控制算法的主要步骤在上面的流程图中已经详细给出，下面将给出这个算法的主要代码。
正如前面所述，这个程序主要包括两个部分，第一个部分是自定义的一个message类powerMsg，第二个部分就是实现具体算法的详细代码。下面的是这个两个部分的主要代码。
第一部分：
自定义的一个powerMsg类，用来携带功率控制的信息，如功率大小，链路增益，信噪比，节点的状态信息（空闲或者忙碌）等等。
message powerMsg
{
fields:
double txPower;
double rxWantMinpower;
double MEI;
int sourceNodeIndex;
int destintNodeIndex; // 如果为 -1说明是广播的.
int x; //记录发送节点的x,y位置
int y;
bool wantCommWithYou=false;
bool linkSucessToCreat=false; //如果成功建立一个link则为true
}
这个msg文件通过编译后，会生成另外两个文件：powerMsg_m.h和powerMsg_m。
第二：建立一个物理层的模块。
物理层的模块主要处理与信道有关的东西，比如功率控制的信道接入方式，维持链路的增益，计算比特误码率等等。
#include <omnetpp.h>
#include “powerMsg_m.h”
class Physic :public cSimpleModule
{
private:
double initxPower;
double commonPower; //发起链接请求的时候的通用的功率
double deviceMaxpower;
double myMEI;
double mySIR;
double myLinkGain;
double requireRate;
double totoalInterferenc;
double backnoise;
double shapingFactor;
double tagetSIR;
double Tf;
int posX, posY;
int targetNodeIndex;
int sourceNodeIndex;
bool isBusy;
cArray txpmsgArray;
cArray rxpmsgArray;
public:
double getDistance(powerMsg * pmsg);
double getGain(powerMsg *pmsg);
double getInterference();
double getSIR();
double getmyMEI(double tSIR);
void sendmyMEI();
void sendIniPmsg(int targetNodeIndex);
double maxPower();
double minPower();
double resetPower();
virtual void initialize();
virtual void handleMessage(cMessage * msg);
virtual void finish();
};
#include “Physic.h”
Define_Module(Physic);
void Physic::initialize()
{
//从父模块(就是node节点模块那里获取x,y的位置)
posX=(int)parentModule()->par(“x”);
posY=(int)parentModule()->par(“y”);
txpmsgArray.setName(“txpmsgList”);
rxpmsgArray.setName(“rxpmsgList”);
isBusy=false;
myLinkGain=0.0;
initxPower=0.0;
//发起链接请求的时候的通用的功率
commonPower=1.0;
deviceMaxpower=2.0;
requireRate=1.4e6;
backnoise=4.0e-18;
shapingFactor=1.99e-3;
tagetSIR=10.0;
Tf=1.0e-7;
ev<<"the node’s Physic layer… is initializing…the node is "<<parentModule()->index()<<endl;
ev<<“send a msg to MAC”<<endl;
//发一个Msg到MAC层
cMessage *toMacmsg=new cMessage(“toMAC”);
send(toMacmsg,“toMAC”);
//一条新的链路的初始化请求
if(((parentModule()->index())%2)==0)
{
ev<<“the node “<< parentModule()->index()<<” is initializing… and want to send a selfMsg…”<<endl;
simtime_t waittime=(simtime_t)uniform(0.10,3.0);
cMessage *smsg=new cMessage(“selfMsg”);
scheduleAt(simTime()+waittime,smsg);
ev<<“self msg had send…”<<endl;
isBusy=true;
}
}
//处理cMessage的主要代码
void Physic:: handleMessage(cMessage * msg)
{
if (msg->isSelfMessage())
{
//处理selfMsg；
delete msg;
int a=genk_intrand(0,11);
while((a%2)==0)
{
a=genk_intrand(0,11);
}
bool aIsBusy=false;
for (int i=0;i<rxpmsgArray.items();i++)
{
powerMsg *pmsgs=(powerMsg *)rxpmsgArray[i];
if(pmsgs->getSourceNodeIndex()==a)
{
aIsBusy=true;
ev<<" the node a is now receiving ,choose a new one "<<endl;
break;
}
}
if(aIsBusy)
{
ev<<"the node "<< parentModule()->index()<<" is initializing.... and want to send a selfMsg..."<<endl;
ev<<"but the destination node is busy...choosing aother one ....."<<endl;
cMessage *smsg=new cMessage("selfMsg");
scheduleAt(simTime(),smsg);
ev<<"self msg had send..."<<endl;
isBusy=true;
}
else
{
ev<<"I am the node "<<parentModule()->index()<<" the self msg had arrived...."<<endl;
ev<<" and i want to comunicate with the node "<<a<<" and send a msg to him...... "<<endl;
sendIniPmsg(a);
isBusy=true;
}
}
else if (strcmp(msg->name(),"txpowerMsg")==0)
{
powerMsg *pmsg=(powerMsg *)msg;
ev<<" a txpowerMsg is arriving from the node "<<pmsg->getSourceNodeIndex()<<endl;
ev<<"convert to pMsg.....I am the node "<<parentModule()->index()<<endl;
if ((pmsg->getWantCommWithYou())&&((pmsg->getDestintNodeIndex())==(parentModule()->index())))
{
if (!isBusy) {
if(pmsg->getLinkSucessToCreat()) //此时已经成功建立了连接
{
ev<<"I am the node "<<parentModule()->index()<<" an the link is sucess to creat.."<<endl;
powerMsg *minpmsg=new powerMsg("rxpowerMsg");
minpmsg->setSourceNodeIndex(parentModule()->index());
minpmsg->setDestintNodeIndex(-1); //广播MEI了
minpmsg->setWantCommWithYou(false);
myLinkGain=getGain(pmsg);
initxPower=pmsg->getTxPower();
myMEI=getmyMEI(tagetSIR);
minpmsg->setMEI(myMEI);
minpmsg->setLinkSucessToCreat(true);
minpmsg->setX(posX);
minpmsg->setY(posY);
isBusy=true;
for(int i=0;i<11;i++)
{
powerMsg *copypmsg= (powerMsg *)minpmsg->dup();
send(copypmsg,"toOutside",i);
}
bubble("I have broadcasted my MEI...");
ev<<"I am the node .."<<parentModule()->index()<<"I have broadcasted my MEI..."<<endl;
if(isBusy)
{
//在这个link的生命内 不停的广播自己的MEI myMEI=getmyMEI(tagetSIR);
ev<<" In my life I am Broadcasting........my MEI is :"<<myMEI<<endl;
powerMsg *minpmsg=new powerMsg("rxpowerMsg");
minpmsg->setSourceNodeIndex(parentModule()->index());
minpmsg->setDestintNodeIndex(-1); //说明要广播MEI了
minpmsg->setWantCommWithYou(false);
minpmsg->setMEI(myMEI);
minpmsg->setLinkSucessToCreat(true);
minpmsg->setX(posX);
minpmsg->setY(posY);
for(int i=0;i<11;i++)
{
powerMsg *copypmsg= (powerMsg *)minpmsg->dup();
send(copypmsg,"toOutside",i);
}
}
}
else
{
myLinkGain=getGain(pmsg);
double minipower=minPower();
ev<<"I am the node "<<parentModule()->index()<<" computing the min power is OK!!"<<endl;
ev<<"the min power is .."<<minipower<<endl;
powerMsg *minpmsg=new powerMsg("rxpowerMsg");
minpmsg->setSourceNodeIndex(parentModule()->index());
minpmsg->setRxWantMinpower(minipower);
minpmsg->setDestintNodeIndex(pmsg->getSourceNodeIndex());
minpmsg->setWantCommWithYou(true);
minpmsg->setX(posX);
minpmsg->setY(posY);
for(int i=0;i<10;i++)
{
powerMsg *copypmsg= (powerMsg *)minpmsg->dup();
send(copypmsg,"toOutside",i);
}
send(minpmsg,"toOutside",10); // 是广播
}
}
}
else if( ((pmsg->getDestintNodeIndex())!=(parentModule()->index()))&&(pmsg->getLinkSucessToCreat()))
{
bool haveOldmsg;
haveOldmsg=false;
for (int i=0;i<txpmsgArray.items();i++)
{
powerMsg *pmsgs=(powerMsg *)txpmsgArray[i]; if(pmsgs->getSourceNodeIndex()==pmsg->getSourceNodeIndex())
{
haveOldmsg=true;
delete txpmsgArray.remove(i);
int index =txpmsgArray.add(pmsg);
break;
}
}
if(!haveOldmsg)
int indexs=txpmsgArray.add(pmsg);
}
}
else
{
delete pmsg;
ev<<"I am the node "<<parentModule()->index()<<“I receive a msg which is usefulless …deleting it”<<endl;
}
}
else if (strcmp(msg->name(),"rxpowerMsg")==0)
{
powerMsg *pmsg=(powerMsg *)msg;
ev<<"convert to pMsg....."<<endl;
if ((pmsg->getWantCommWithYou())&&((pmsg->getDestintNodeIndex())==(parentModule()->index())))
{
//是rx应答的信息,里面有它需要的最小的power.
double rxminpower=pmsg->getRxWantMinpower();
ev<<"my min power is :"<<rxminpower<<endl;
double txmaxpower=maxPower();
if (rxminpower>txmaxpower)
{
isBusy=false;
while(!isBusy)
{
ev<<"the node "<< parentModule()->index()<<" re transmiting is
want to send a selfMsg…"<<endl;
simtime_t waittime=(simtime_t)uniform(0.10,3.0);
cMessage *smsg=new cMessage(“selfMsg”);
scheduleAt(simTime()+waittime,smsg);
ev<<“self msg had send…”<<endl;
}
}
else
{
initxPower=(txmaxpower+rxminpower)/2;
isBusy=true;
powerMsg *txpmsg=new powerMsg("txpowerMsg");
ev<<"I am the node "<<parentModule()->index()<<"sucees to contruct a new link ..."<<endl;
ev<<"the link is :"<<parentModule()->index()<<"--->>"<<pmsg->getSourceNodeIndex()<<endl;
txpmsg->setTxPower(initxPower);
txpmsg->setSourceNodeIndex(parentModule()->index());
txpmsg->setDestintNodeIndex(pmsg->getSourceNodeIndex());
txpmsg->setX(posX);
txpmsg->setY(posY);
txpmsg->setWantCommWithYou(true);
txpmsg->setLinkSucessToCreat(true);
for(int i=0;i<10;i++)
{
powerMsg *copypmsg= (powerMsg *)txpmsg->dup();
send(copypmsg,"toOutside",i);
}
send(txpmsg,"toOutside",10);
bubble("I have broadcasted my ini power...");
while(isBusy)
{
powerMsg *txpmsg=new powerMsg("txpowerMsg");
txpmsg->setTxPower(initxPower);
txpmsg->setSourceNodeIndex(parentModule()->index());
txpmsg->setDestintNodeIndex(pmsg->getSourceNodeIndex());
txpmsg->setX(posX);
txpmsg->setY(posY);
txpmsg->setWantCommWithYou(true);
txpmsg->setLinkSucessToCreat(true);
for(int i=0;i<10;i++)
{
powerMsg *copypmsg= (powerMsg *)txpmsg->dup();
send(copypmsg,"toOutside",i);
}
send(txpmsg,"toOutside",10);
}
}
}
else if((pmsg->getDestintNodeIndex()==-1)&&(pmsg->getLinkSucessToCreat()))
{
bool haveOldmsg;
haveOldmsg=false;
for (int i=0;i<rxpmsgArray.items();i++)
{
powerMsg *pmsgs=(powerMsg *)rxpmsgArray[i];
if(pmsgs->getSourceNodeIndex()==pmsg->getSourceNodeIndex())
//删除旧的,加入新的msg
{
haveOldmsg=true;
delete rxpmsgArray.remove(i);
int index =rxpmsgArray.add(pmsg);
ev<<" there is an old one in the rxArray....delete it and add the new one"<<endl;
//ev<<"the old one is from....node ..."<<pmsgs->getSourceNodeIndex();
break;
}
}
if(!haveOldmsg)
int index=rxpmsgArray.add(pmsg);
}
else
{
ev<<"I am the node "<<parentModule()->index()<<"I receive a msg which is usefulless ....deleting it"<<endl;
delete pmsg;
}
}
else
{
//处理数据msg，交给上层；
send(msg,“toMAC”);
}
}
//发送初始化请求的Msg
void Physic::sendIniPmsg(int targetindex)
{
powerMsg *pmsg=new powerMsg(“txpowerMsg”);
pmsg->setTxPower(commonPower);
pmsg->setX(posX);
pmsg->setY(posY);
pmsg->setWantCommWithYou(true);
pmsg->setSourceNodeIndex( parentModule()->index() );
pmsg->setDestintNodeIndex(targetindex);
for(int i=0;i<10;i++)
{
powerMsg *copypmsg= (powerMsg *)pmsg->dup();
send(copypmsg,“toOutside”,i);
ev<<“broakcasting the initial msg to other node from the gate toOuside[”<<i<<"]"<<endl;
}
send(pmsg,“toOutside”,10);
}
//计算两个节点的距离
double Physic::getDistance(powerMsg * pmsg)
{
double distant=sqrt((posX-pmsg->getX())(posX-pmsg->getX())+(posY-pmsg->getY())(posY-pmsg->getY()));
return distant;
}
//计算两个节点的信噪比
double Physic::getGain(powerMsg pmsg)
{
double gain;
double dist=getDistance(pmsg);
if(dist<35)
{
gain=1;
}
gain=1225/(distdist);
return gain;
}
//一个接收节点计算它的总干扰
double Physic::getInterference()
{
double totleNiose=0.0;
for (int i=0;i<txpmsgArray.items();i++) {
powerMsg *pmsg=(powerMsg *)txpmsgArray[i];
if ((pmsg->getSourceNodeIndex() )!=(parentModule()->index()))
{
double gains=getGain(pmsg);
totleNiose+=(pmsg->getTxPower())*gains;
}
}
return totleNiose;
}
double Physic::getSIR()
{
double mylinkgain, sourcepower;
for (int i=0;i<txpmsgArray.items();i++)
{
powerMsg apmsg=(powerMsg )txpmsgArray[i];
if ((apmsg->getSourceNodeIndex() )==(parentModule()->index()))
{
mylinkgain=getGain(apmsg);
sourcepower=apmsg->getTxPower();
break;
}
}
//下面计算SIR
double interfere=getInterference();
double theSIR=(mylinkgainsourcepower)/(requireRate(backnoise+shapingFactorTfinterfere));
return theSIR;
}
//正在接收的节点计算它的MEI
double Physic::getmyMEI(double tSIR)
{
double interfere=getInterference();
double xixi=tSIRrequireRateshapingFactorTf;
double myMei=(initxPowermyLinkGain-tSIRrequireRatebacknoise-xixi*interfere)/(xixi);
return myMei;
}
//发送节点计算最大的发送功率
double Physic::maxPower()
{
double thetxPower;
double maxpower=1000.0;
for (int i=0;i<rxpmsgArray.items();i++)
{
powerMsg *pmsgs=(powerMsg *)rxpmsgArray[i];
double gain=getGain(pmsgs);
if (((pmsgs->getMEI())/gain)<maxpower)
maxpower=(pmsgs->getMEI())/gain;
}
if(maxpower>(deviceMaxpower))
maxpower= deviceMaxpower;
return maxpower;
}
//计算最小需要的功率
double Physic::minPower()
{
double intf=getInterference();
double minpowers=(tagetSIRrequireRate(shapingFactorintfTf+backnoise))/ myLinkGain;
return minpowers;
}
void Physic::finish()
{
ev<<“finish…”<<endl;
}
3.2.4 仿真结果分析
通过上面的仿真实验，我们可以看到，运用UWB作为物理层载体，各个链路之间的多用户干扰是很小的。因为UWB信号的功率非常低，而且随着距离的增大，它的功率也会衰减得很快。所以它非常适合于应用在多个用户的系统，以及多径复杂的环境下。上面的仿真的结果输出也说明，该功率控制算法运用在UWB上是非常有效的。
3.2.5 应用前景
超宽带UWB技术潜力还很大，主要是由于使用极短的脉冲通信，传输速率在理论上可以达到数Gbps的水平。目前UWB样品已经能够达到，3米范围内480Mbps传输速率、5米内80Mbps传输速率。未来预计在2007年以后，“超宽带UWB”设备甚至可以用来直接传输视频信号，这可以让众多的视频显示系统，摆脱线缆限制，届时整个电子产品业内面貌将会随之而产生巨大改变。另外人们对于健康越来越重视，更加青睐“低功耗、低辐射”类型的产品，“超宽带UWB技术”先天的低功耗特点，将会让其成为家庭、办公环境的首选。而且“超宽带UWB技术”由于脉冲发生的电路结构简单，可以用单一芯片实现全部功能，这样更容易在笔记本电脑、PDA等便携设备中集成，为未来个人无线传输打下基础，达到无线无处不在的境地。由于应用前景十分广阔，因此会有越来越多的研究者投入到UWB 领域。
参考文献
[1] Francesca Cuomo, Cristina Martello. Ultra Wide Band WLANS:A Self-Configuring Resource Control Scheme for Accessing UWB Hot-Spots with QoS Guarantees
[2] Michael I. Brownfield, Kaveh Mehrjoo, Almohonad S. Fayez, and Nathaniel J. Davis IV, Wireless Sensor Network Energy-Adaptive MAC Protocol
[3] Jeffrey P. Monks, Vaduvur Bharghavan, and Wen-mei W. Hwu, A Power Controlled Multiple Access Protocol for Wireless Packet Networks
[4] F. Cuomo, C. Martello, A. Baiocchi, and F. Capriotti, “Radio Resource Sharing for Ad Hoc Networking with UWB”, IEEE Journal on Selected Areas in Communications, Vol. 20, No. 9,pp. 1722–1732, December 2002.
[5] MARIA-GABRIELLA DI BENEDETTO, LUCA DE NARDIS, MATTHIAS JUNK and GUERINO GIANCOLA，（UWB）2: Uncoordinated, Wireless, Baseborn Medium Access for UWB Communication Network
[6] Jean-Yves Le Boudec, Ruben Merz, Božidar Radunovi ´c, Jörg Widmer ,DCC-MAC A Decentralized MAC Protocol for 802.15.4a-like UWB Mobile Ad-Hoc Networks Based on Dynamic Channel Coding
[7] Tomaso Erseghe, Nicola Laurenti, Pietro Nicoletti, and Andrea Sivier, An Algorithm for Radio Resource Management in UWB Ad Hoc Networks with Concurrent Guaranteed QoS and Best Effort Traffic
[8] Vipin Mehta, Magda El Zarki, An Ultra Wide Band (UWB) based Sensor Network for Civil Infrastructure Health Monitoring
[9] N.Boubaker , K.B.Letaidf, Performance Analysis of DS-UWB Multiple Access Under Imperfect Power Control
[10]Maria-Gabriella, Di Benedetto, Guerino Giancola 著, 葛利嘉等译. 超宽带无线电基础. 北京: 电子工业出版社, 2005.
[11] 葛利嘉,曾凡鑫，刘郁林，岳光荣.超宽带无线通信.北京：国防工业出版社，2005.8
第四章 MAC层仿真
概述
介质访问控制(medium access control)协议简称MAC 协议，处于无线传感器网络协议的底层部分，以解决无线传感器网络中节点以怎样的规则共享媒体才能保证满意的网络性能问题。对传感器网络的性能有较大影响，是保证无线传感器网络高效通信的关键网络协议之一，传感器网络的性能如吞吐量、公平度、延迟性能等完全取决于所采用的MAC协议。
蜂窝电话网络、Ad Hoc 是当前主流的无线网络技术，但它们各自的MAC 协议不适合无线传感器网络。GSM 和CDMA 中的介质访问控制主要关心如何满足用户的QoS 要求和节省带宽资源，功耗是第二位的；Ad Hoc 网络则考虑如何在节点具有高度移动性的环境中建立彼此间的链接，同时兼顾一定的QoS 要求，功耗也不是其首要关心的。而无线传感器网络的MAC 协议首要考虑的因素就是节省能量。这意味着传统网络的MAC 协议不适用于传感器网络，需要提出新的适用于传感器网络的MAC 协议。
4.1 无线传感器网络MAC层特性及分类
4.1.1 无线信道特性
在无线通信中,一个无线电干扰范围内,一个信道不能被两个或多个节点同时访问，其性能受众所周知的“隐藏终端”和“暴露终端”问题的严重影响。如图1（a）所示，假设A获得无线接口的接入权，并且在向指定的接收终端B传输数据。假设在B邻居范围内有第三个终端C也开始了一个传输过程，但由于距离远或被阻隔，它对A来说是隐蔽的。终端B在侦听信道时由于接收不到A的信号而认为信道是空闲的，它发射功率后就会在接收节点B处产生了冲突，这就是隐蔽终端问题。
暴露终端问题如图1（b）所示。假设终端A开始向B发送分组，并假设另一终端C也要发送分组。当C侦听信道时，它检测到有从B到A的传输信号，认为信道忙而推迟传输。但实际上，C发送的分组不会影响到B对A的正确接收，因为B和C在彼此的无线覆盖范围之外。
（a）隐藏终端问题 （b）暴露终端问题
图1 隐藏终端问题和暴露终端问题
4.1.2 MAC 设计特性分析
设计无线传感器MAC 协议,首先要考虑节点的电池能量效率。每个节点由电池供电,由于环境或是其他条件约束,节点的电池只能一次使用,在MAC 设计时着重考虑如何提高电池能量效率,成为无线传感器网络区别于其他网络MAC 设计的一个重要方面。其次要考虑无线传感器的可扩展性,网络的尺寸、节点的密度和网络拓扑由于节点的失效和新节点的加入可能随时会发生变化。当然还有一些传统网络的属性,如公平性、延迟、吞吐率和带宽利用率等,这些属性在传统的网络中是非常重要和需要着重考虑的,在无线传感器中成为次要考虑的内容。
无线传感器网络节点的能量效率主要由以下因素决定。第一个因素就是冲突,由于发生冲突不得不进行重传,从而增加了能量消耗又增加延迟。第二个因素是串音,就是节点收到不是发给他的分组,造成能量消耗。第三个是一个分组中控制部分的开销,如果传输分组的个数
多,且每个分组所携带的数据部分比较小,那么控制部分的开销就会很大。最后也是最主要的一个开销就是空闲侦听,多数情况下,无线传感器网络的应用负载是相对小的,无谓的侦听浪费了大量的能量,在节点不参与工作时,应该关掉节点的无线收发部分。以下的协议都是基于以上的一个或几个特性考虑的。
4.1.3 无线传感器网络典型MAC协议的分类
根据采用固定分配信道方式还是随机访问信道方式，可以将传感器网络的MAC协议分为三类：
（1）采用无线信道的随机竞争方式，节点在需要发送数据时随机使用无线信道，重点考虑尽量减少节点间的干扰；
（2）采用无线信道的时分复用方式，给每个传感器节点分配固定的无线信道使用时段，从而避免节点之间的相互干扰；
（3）其他MAC协议，如通过采用频分复用或者码分复用等方式，实现节点间无冲突的无线信道的分配。
下面按照上述传感器网络MAC协议分类，介绍几种无线传感器网络典型的MAC协议。
4.2 基于随机竞争的MAC协议
4.2.1 S-MAC协议[12]
S-MAC协议[1]是在802.11MAC协议基础上，针对传感器网络的节能需求而提出的传感器网络MAC协议。针对碰撞重传、串音、空闲侦听和控制消息等可能造成传感器网络消耗更多能量的主要因素，S-MAC协议采用以下机制：周期性侦听/睡眠的低占空比工作方式，控制节点尽可能处于睡眠状态来降低节点能量的消耗；邻居节点通过协商的一致性睡眠调度机制形成虚拟簇，减少节点的空闲侦听时间；通过流量自适应的侦听机制，减少消息在网络中的传输延迟；采用带内信令来减少重传和避免监听不必要的数据；通过消息分割和突发传递机制来减少控制消息的开销和消息的传递延迟。下面详细描述S-MAC协议的主要机制。
1、周期性侦听和睡眠
为了减少能量消耗，节点要尽量处于低功耗的睡眠状态。每个节点独立地调度它的工作状态，周期性地转入睡眠状态，在苏醒后侦听信道状态，判断是否需要发送或接收数据。为了便于相互通信，相邻节点之间应该尽量维持睡眠/侦听调度周期的同步。
每个节点用SYNC消息通告自己的调度信心，同时维护一个调度表，保存所有相邻节点的调度信息。当节点启动工作时，首先侦听一段固定长度的时间，如果在这段侦听时间内收到其他节点的调度信息，则将它的调度周期设置为与邻居节点相同，并在等待一段随机时间后广播它的调度信息，当节点收到多个邻居节点的不同调度信息时，可以选择第一个收到的调度信息，并记录收到的所有调度信息。如果节点在这段侦听时间内没有收到其他节点的调度信息，则产生自己的调度周期并广播。在节点产生和通告自己的调度后，如果收到邻居的不同调度，分两种情况：如果没有收到过与自己调度相同的其他邻居的通告，则采纳邻居的调度而丢弃自己生成的调度；如果节点已经收到过与自己调度相同的其他邻居的通告，在调度表中记录该调度信息，以便能够与非同步的相邻节点进行通信。
这样，具有相同调度的节点形成一个虚拟簇，边界节点记录两个或多个调度。在部署区域广阔的传感器网络中，能够形成众多不同的虚拟簇，可使得S-MAC具有良好的扩展性。为了适应新加入节点，每个节点都要定期广播自己的调度，使新节点可以与已经存在的相邻节点保持同步。如果一个节点同时收到两种不同的调度，那么这个节点可以选择先收到的调度，并记录另一个调度信息。
2．流量自适应侦听机制
传感器网络往往采用多跳通信，而节点的周期性睡眠会导致通信延迟的累加。在S-MAC协议中，采用了流量自适应侦听机制，减少通信延迟的累加效应。它的基本思想是在一次通信过程中，通信节点的邻居节点在通信结束后不立即进入睡眠状态，而是保持侦听一段时间。如果节点在这段时间内接到RTS分组，则可以立刻接收数据，无须等到下一次调度侦听周期，从而减少了数据分组的传输延迟。如果在这段时间内没有接到RTS分组，则转入睡眠状态直到下一次调度侦听周期。
3、串音避免
为了减少碰撞和避免串音，S-MAC协议采用与802.11MAC协议类似的虚礼和物理载波侦听机制，以及RTS/CTS的通告机制。两者的区别在于当邻居节点处于通信过程中时，S-MAC协议的节点进入睡眠状态。
每个节点在传输数据时，都要经历RTS/CTS/DATA/ACK的通信过程（广播包除外）。在传输的每个分组中，都有一个域值表示剩余通信过程需要持续的时间长度。源和目的节点的邻居节点在侦听期间侦听到分组时，记录这个时间长度值，同时进入睡眠状态。通信过程记录的剩余时间会随着时间不断减少。当剩余时间减至零时，若节点仍处于侦听周期，就会被唤醒；否则，节点处于睡眠状态直到下一个调度的侦听周期。每个节点在发送数据时，都要先进行载波侦听。只有虚礼或物理载波侦听表示无线信道空闲时，才可以竞争通信过程。
4、消息过程
因为传感器网络内部数据处理需要完整的消息，所以S-MAC协议利用RTS/CTS机制，一次预约发送整个长消息的时间；又因为传感器网络的无线信道误码率高，S-MAC协议将一个长消息分割成几个短消息在预约的时间内突发传送。为了能让邻居节点及时获取通信过程剩余时间，每个分组都带有剩余时间域。为了可靠传输以及通告邻居节点正在进行的通信过程，目的节点对每个短消息都要发送一个应答消息。如果发送节点没有收到应答消息，则立刻重传该短消息。
相对IEEE802.11MAC的消息传递机制，S-MAC的RTS/CTS控制消息和数据消息携带的时间是整个长消息传输的剩余时间。其他节点只要收到一个消息，就能够知道整个长消息的剩余时间，然后进入睡眠状态直至长消息发送完成。IEEE802.11MAC协议考虑网络的公平性，RTS/CTS只预约下一个发送短消息的时间，其他节点在每个短消息发送完成后都不须醒来进入侦听状态。只要发送方没有收到某个短消息的应答，连接就会断开，其他节点便可以开始竞争信道。
S-MAC协议的主要优点是：利用周期性的睡眠/侦听减少了空闲监听所造成的能量浪费；通过让相邻节点同步减少了控制消耗；利用RTS/CTS机制减少了数据冲突的几率。
S-MAC协议本身也存在着一些缺点：睡眠和侦听的周期是预定不变的，侦听周期的设定必须满足最高通信负载时的要求，所以当通信负载变化时，仍会导致空闲侦听，造成能量浪费；周期性的睡眠造成了延时的增加；相邻节点的同步增加了冲突的几率；采用自适应侦听会降低吞吐量同时也导致空闲侦听；没有考虑节点的运动，当网络中存在移动节点时，容易造成节点丢失。
4.2.2 T-MAC协议
T-MAC（Timeout MAC）协议[2]是在S-MAC 协议的基础上提出来的。S-MAC 协议通过采用周期性侦听/睡眠工作方式来减少空闲侦听，周期长度是固定不变的，节点的侦听活动时间也是固定的。而周期长度受限于延迟要求和缓存大小，活动时间主要依赖于消息速率。这样就存在一个问题：延迟要求和缓存大小是固定的，而消息速率通常是变化的。如果要保证可靠及时的消息传输，节点的活动时间必须适应最高通信负载。当负载动态较小时，节点处于空闲侦听的时间相对增加。针对这个问题，T-MAC 协议在保持周期长度不变的基础上，根据通信流量动态地调整活动时间，用突发方式发送消息，减少空闲侦听时间。T-MAC协议相对S-MAC 协议减少了处于活动状态的时间。
在T-MAC 协议中， 发送数据时仍采用RTS/CTS/DATA/ACK 的通信过程，节点周期性唤醒进行侦听，如果在一个指定时间TA 内没有发生下面任何一个激活事件，则活动结束：周期时间定时器溢出;在无线信道上收到数据;通过接收信号强度指示RSSI 感知存在无线通信;通过侦听RTS/CTS 分组，确认邻居的数据交换已经结束。
T-MAC 协议根据当前的网络通信情况，通过提前结束活动周期来减少空闲侦听，但带了早睡问题。为解决这个问题，提出了未来请求发送和满缓冲区优先两种方法。
4.2.3 AC-MAC协议
AC-MAC协议[3]是在MAC协议基础上做的另一种改进，但目的和T-MAC一样，都是为了应对实际传感器应用中的负载变化问题。不同的是AC-MAC采用了在S-MAC框架中引入自适应任务周期方案，在保持S-MAC能量有效利用性能的同时，提升了在传输负载大范围变化下延时和吞吐量方面的性能。具体来说，AC-MAC用在MAC层排队的信息包数量作为传输负载高低的指标，根据这个指标，在S-MAC的几个基本任务循环周期中安排了自适应数量的通信机会。AC-MAC协议中新任务周期的确认方法如下：
假设在MAC层中节点i的队列信息包为Ni，它可以通过方程Ri＝f（Ni）映射到对应的值Ri，其中函数f表达了应用中节点想要传输信息的渴望程度。新的任务周期为：
为了保持S-MAC基本的任务周期，R值是在每个基本任务周期的开始处通过RTS/CTS信息包宣布的。为了达到最优的延时和吞吐量，自然要采用最大的R值.
AC-MAC的优点是在保持了S-MC协议能量有效利用性能的同时，大幅度提高了S-MAC协议在延时和吞吐量方面的性能，并且适应了实际应用中传输负载的变化，但它在传输负载变化的情况下，不能像T-MAC那样进一步减少能量的消耗，而且固定的小竞争窗口将导致冲突发生的可能性增加。
4.3 基于时分复用的MAC协议
4.3.1 D-MAC协议
S-MAC 和T-MAC 协议采用周期性的活动/睡眠策略减少能量消耗，但是存在数据通信停顿问题，从而引起数据的传输延迟。而在无线传感器网络中，经常采用的通信模式是数据汇集树，针对这种结构，为了减少网络的能量消耗和数据的传输延迟，提出了DMAC协议[4]。其基本思想是，基于数据汇集树，让多跳路径上的所有节点的活动区间交错，让这些节点像链接反应一样相继醒来。
与S-MAC协议不同的是D-MAC协议中没有采用RTS/CTS机制。为了避免在同一深度的节点在传输周期中发生冲突，在每个竞争窗口之前加上了一个随机退让周期(BP)，在节点接收了一个信息包后，它将等待一段很短的周期(SP)然后再返回一个ACK信息包，所以接收周期和发送周期的长度为：µ = BP+CW+DATA+SP+ACK。
当一个节点有多个信息包需要发送时，D-MAC采用了slot-by-slot更新方案，将多数据标志附在MAC报头以增加节点和多跳路径上其他节点的任务周期。在此基础上，D-MAC协议还增设了数据预报方案，减少了睡眠延时。为了避免不同分支上的节点之间发生冲突，D-MAC协议提出了more-to-send方案。
在汇聚形式的通信中，D-MAC协议与S-MAC协议相比延时方面达到了非常好的效果。但它只局限于汇聚这种通信形式，而且如果数据的传输路径没有事先得知，数据汇集树将无法形成，此时该协议将不能适用。
4.3.2 TRAMA协议
流量自适应介质访问（TRAMA）协议[5]将时间划分为连续时隙，根据局部两跳内的邻居节点信息，采用分布选举机制确定每个时隙的无冲突发送者。同时，通过避免把时隙分配给无流量的节点，并让非发送和接收节点处于睡眠状态达到节省能量的目的。为了适应节点失败或节点增加等引起的网络拓扑结构变化，将时间划分为交替的随机访问周期和调度访问周期。随机访问周期和调度访问周期的时隙个数根据具体应用情况而定。随机访问周期主要用于网络维护。
TRAMA 协议根据两跳范围内的邻居节点信息，由节点独立确定自己发送消息的时隙，同时避免把时隙分配给没有信息发送的节点，由此提高了网络吞吐量，克服了基于TDMA 的MAC 协议扩展性差的不足。但是TRAMA 协议相对比较复杂，为了建立节点间一致的调度消息，计算和通信开销都比较大。
4.3.3 AI-LMAC协议
AI-LMAC(adaptive,information centric and lightweightMAC)是基于TDMA 技术的MAC 协议[6]，无需竞争介质，也不会产生碰撞冲突。AI-LMAC 协议的思想是：网络初始化由网关节点(如sink 节点) 发起，网关先广播一个控制帧到与它相邻一跳范围的邻节点，节点收到信息后，再广播自己的控制帧到它的一跳范围内的邻节点，这样逐步扩散至整个网络，初始化主要是完成时隙( time slot)分配，即网络中的节点选取一个时隙作为自己的发射时间)。在控制帧中有一个域来标识时隙(一个bit 位表示一个节点的时隙)，其它节点收到广播后就会选取尚未使用的时隙。时隙的长度不变，每个时隙包含控制信息(controlmessage，CM)和数据信息(data message，DM)两部分。其中CM 长度固定，DM长度可变化，但最大不能超出上限，为了节约能量，当没有数据发送或者数据发完而时隙没有完时，都及时关闭无线电发射装置。AI-LMAC 协议中每个节点都有一个固定分配的时隙来发送/接收信息，但当节点中的数据传输量较大时，可根据每个节点中的DDT (data distribution table) 中的信息来申请使用空闲的时隙，以减少网络的延时，提高节点的公平性。AI-LMAC 协议最显著特点是充分利用了循环机制，使每个传感器节点在自己时隙以外的其它时隙处于睡眠状态，使能量消耗最小，达到节能的目的。
4.4 其他类型的MAC协议
4.4.1 SMACS/EAR协议
SMACS/EAR（Self-organizing Medium Access Control/Eavesdrop And Register）协议[7]是一种结合时分复用和频分复用的基于固定信道分配的MAC协议。基主要思想是为每一对邻居节点分配一个特有频率进行数据传输，不同节点对时间的频率互不干扰，从而避免同时传输的数据之间产生碰撞。SMACS协议主要用于静止节点间链路的建立，而EAR协议则用于建立少量运动节点与静止节点之间的通信链路。SMACS/EAR 协议不要求所有节点之间进行时间同步，只需要两个通信节点间保持相对的帧同步。它不能完全避免碰撞，因为多个节点在协商过程中可能同时发出“邀请”消息或应答消息。于每个节点要支持多种通信频率，这对节点硬件提出了很高的要求，同时，由天每个节点需要建立的通信链路数无法事先预计，使得整个网络的利用率不高。
4.4.2 基于CDMA技术的MAC协议
CDMA 是一种使用编码技术实现信道共享的通信技术。CDMA 是利用相互正交的编码来实现频率、时间上的叠加。在无线传感器网络中要想实现CDMA技术就是要为众多的传感器节点分配相互正交的地址码，就能够避免碰撞冲突发生。文献[8]中介绍了一种使用CDMA 技术的MAC 协议。为了实现正交的地址编码，设计了一种伪随机码分配算法，使得每个传感器节点与其两跳范围内的所有节点的伪随机码都保持正交，从而实现了信道共享，确保了通讯过程中不会产生碰撞冲突。为了保持局部范围内的同步，同时也为了降低能量消耗，该协议要求每个节点使用两个独立的无线电装置，即：数据收/发射频和低功率唤醒射频。在不收/发数据时让大功率的收/发电路进入睡眠状态，低功率唤醒射频一直处于侦听状态，如果发现需要与其它节点需要向本节点发送数据，则打开数据收/发射频来接收数据；如果节点自身需要发送数据到邻居节点，则通过唤醒射频唤醒睡眠的接收节点，然后双方打开数据收/发射频传输数据。基于CDMA 技术的MAC 协议，不需要严格的时钟同步，只要求局部范围内的节点之间保持同步，网络的可扩展性较好。但CDMA 的编码解码过程较为复杂，是对传感器节点有限的计算能力的考验。
4.4.3 DCC-MAC
为了将超宽带技术与传感器网络结合起来，在DCC-MAC协议[9]中采用了一种类似传统CDMA和扩码的技术。在DCC-MAC[4]中，基于PPM-TH-UWB信号[10]，应用跳时码（TH）多路接入物理层，提出了一个联合物理和MAC层的体系结构，适用于低速、低功耗、定位、分布式的IEEE 802.15.4a[11]网络架构。在跳时超宽带物理层，采用比较大的脉冲重复周期（PRP），这样一方面可以降低辐射的能量，另一方面减少了时间上跳时码重复的可能。在信道访问方面，通过结合基于接收端和基于邀请的THS选择解决了UWB中不能用传统的载波侦听的问题。为了避免同时几个发送端向一个接收端发送数据，采用私有MAC（Private MAC）的方式进行通信，通过基于接收端的公共的跳时序列（public THS）竞争访问目的端，但是建立通信通过私有的属于源－目的对的私有序列（private THS）。假设一个节点S有数据发往节点D，同时没有其他的节点往D发数据。空闲的节点D用它的THS监听信道。当节点S需要与D通信，它用D的THS发送一个传输请求包（REQ）。为了能让其他的节点知道自己发送了一个请求，这个REQ采用最低的速率RN确保最大的能量。D用私有序列回答一个响应包（RESP）,速率也是RN.当S收到RESP，开始传输数据。传输完后，发送端和接收端用它们自己的THS发布一个空闲信号通知其他节点。整个过程如图2。DCC-MAC无需公共控制信道，一个节点能够监听多个THS，但是一次只能接收一个节点，而且，一个节点不能同时收发。
图2 DCC-MAC信道访问
4.5 基于OMNeT++的MAC层协议仿真
MAC Simulator是基于TU Delft大学并行和分布式系统研究小组的Consensus项目开发的一个MAC协议模拟器，这个模拟器基于OMNeT++开发，最新版本为version 0.2.2。在OMNeT++官方网站（http://www.omnetpp/article.php?story=200510251304406）有关于MAC Simulator的介绍和相关链接。在TU Delft大学Consensus项目网站上有相关论文和MAC Simulator模拟器的开源软件下载（http://www.consensus.tudelft.nl/software.html）。
开源的MAC Simulator支持Linux操作系统，但是不能直接在Windows操作系统下面运行，需要做适当修改，才能基于Windows平台下的OMNeT++编译和运行。
用MAC Simulator可以对S-MAC，T-MAC，TMACp，L-MAC，CSMA，CSMAACK等MAC协议进行仿真和分析，也可以在这些开源的MAC协议上面进行改进和扩展。下面我们主要结合S-MAC协议的实现进行分析。
4.5.1 S-MAC协议的仿真
在Windows操作系统中，以命令行模式进入MAC Simulator所在目录，依次运行以下命令nedtool *.ned，opp_msgc *.msg，opp_nmakemake –f –e cc，nmake –f Makefile.vc，最终生成可执行文件。运行可执行文件，选择S-MAC，配置监听时间和帧长后，运行效果如图3所示。
图3 S-MAC协议仿真
4.5.2 S-MAC协议流程图
S-MAC协议的周期性侦听和睡眠流程图如图4所示。
图4 S-MAC协议流程图
4.5.3 S-MAC协议的分析
S-MAC的实现主要继承于BasicMac类，而BasicMac主要继承于cSimpleModule。此外，S-MAC根据自己的算法，添加了一些与协议有关的函数。S-MAC类定义如下：
class SMac: public BasicMac
{
//构造，析构，模块
Module_Class_Members(SMac, BasicMac, 0);
protected:
unsigned int listen_time;
unsigned int sleep_time;
unsigned int frame_time;
ushort sched_table[10]; // 邻居调度表
int sched_count;
SchedStates sched_state;
ushort time_last_sched; // 节点自身上次调度的时间
ProtoState proto_state;
ProtoState proto_next_state;
int nav_state;
ushort nav_end_time;
int must_send_sync;
int resync_counter;
Packet * tx_msg;
int rts_contend_time;
int cts_to;
ushort cts_nav_end;
ushort cts_nav_rcv;
ushort cts_nav_t;
int ack_to;
int ack_serial;
int my_serial;
void setMySchedule(ushort time); // 产生自己的调度
void evalState(); // 检查状态
void startContending(int time); // 竞争，冲突避免
void sendSync(); // 发送同步消息
void sendRts();
void sendCts();
void sendData();
void sendAck();
void receiveSync(Packet * msg); // 接收同步消息
void receiveRts(Packet * msg);
void receiveCts(Packet * msg);
void receiveData(Packet * msg);
void receiveAck(Packet * msg);
void adoptSchedule(int offset); // 其他调度
void calcSchedState(); // 重新计算调度状态
void setIdle();
void protocolTimeout();
void navTimeout();
void schedTimeout();
void setProtocolTimeout(int t);
void setNavTimeout(int t);
void setSchedTimeout(int t);
void updateNav(ushort nav);
void txDone();
virtual void endForce();
int isSameSchedule(int time1, int time2);
virtual int mustUseCA(Packet * msg);
//virtual void incBackoff();
virtual void decBackoff();
virtual void init();
virtual void timeout(int which);
virtual void txPacket(Packet * msg);
virtual void rxFrame(Packet * msg);
virtual void transmitDone();
virtual void rxFailed();
virtual void rxStarted();
virtual int headerLength();
};
S-MAC协议的主要函数实现如下：
调度函数
void SMac::setMySchedule(ushort time)
{
// 在时间
状态检查函数
void SMac::evalState()
{
if (proto_state == PROTO_STATE_IDLE && !isReceiving())
{
// 空闲
if (nav_state == NAV_STATE_CLEAR && sched_state !=CHED_STATE_SLEEP)
{
// 侦听 / 活动状态
if (must_send_sync)
{
printf(PRINT_MAC, “preparing to send SYNC %s”,tx_msg?"(data
pending)":"");
// 开始竞争
proto_next_state = PROTO_STATE_SEND_SYNC;
startContending(SYNC_CONTEND_TIME);
return;
}
if (tx_msg && sched_state == SCHED_STATE_OWN)
{
if (mustUseCA(tx_msg)) //冲突避免
{
printf(PRINT_MAC, “preparing to send RTS”);
// 开始竞争
proto_next_state = PROTO_STATE_SEND_RTS;
startContending(rts_contend_time);
}
else
{
printf(PRINT_MAC, “preparing to send data”);
proto_next_state = PROTO_STATE_SEND_DATA;
startContending(RTS_CONTEND_TIME);
}
return;
}
// 只侦听
printf(PRINT_MAC, “idle listening”);
setRadioListen();
}
else
{
// 睡眠状态
printf(PRINT_MAC, “idle sleeping”);
if (getForce() != FORCE_NOSLEEP)
setRadioSleep();
}
}
}
竞争函数
void SMac::startContending(int time)
{
assert(proto_next_state >= 0);
assert(time >= 5);
if (nav_state == NAV_STATE_BUSY)
{
printf(PRINT_MAC, “contend: skipping because nav is busy”);
proto_next_state = PROTO_STATE_INVALID;
setIdle();
}
else
{
proto_state = PROTO_STATE_CONTEND;
int ctime = (int) intuniform(5, time);
printf(PRINT_MAC, “starting contention, will fire in %d”, ctime);
setRadioListen();
setProtocolTimeout(ctime);
}
}
接收函数
void SMac::rxFrame(Packet * msg)
{
assert(msg);
if (sched_state == SCHED_STATE_SLEEP && getForce()!=FORCE_NOSLEEP)
return; // 睡眠中，放弃
if (proto_state == PROTO_STATE_WFCTS && (PKT_KIND(msg) != KIND_CTS ||
msg->local_to != nodeId()))
{
printf(PRINT_MAC, “received packet, but not cts we want”);
cancelTimeout(TIMER_PROTOCOL);
proto_state = PROTO_STATE_IDLE;
}
if (proto_state == PROTO_STATE_WFACK && (PKT_KIND(msg) != KIND_ACK ||
msg->local_to != nodeId() || PKT_SERIAL(msg) != my_serial))
{
printf(PRINT_MAC, “received packet, but not ack we want”);
cancelTimeout(TIMER_PROTOCOL);
proto_state = PROTO_STATE_IDLE;
}
assert(sched_state != SCHED_STATE_SLEEP || getForce() == FORCE_NOSLEEP);
switch (PKT_KIND(msg))
{
case KIND_SYNC:
receiveSync(msg);
break;
case KIND_RTS:
receiveRts(msg);
break;
case KIND_CTS:
receiveCts(msg);
break;
case KIND_DATA:
receiveData(msg);
break;
case KIND_ACK:
receiveAck(msg);
break;
default:
assert(false);
}
evalState();
}
协议超时处理函数
void SMac::protocolTimeout()
{
int next_state;
switch (proto_state)
{
case PROTO_STATE_CONTEND:
assert(proto_next_state >= 0);
assert(!isReceiving());
assert(nav_state == NAV_STATE_CLEAR);
// RSSI是接收信号强度指示
setRadioListen(); // 侦听信号
if(getRssi()>0.5) { // 有信号
printf(PRINT_MAC,
“sensed communication, cancelling”);
setIdle();
return;
}
// 启动下个状态
next_state = proto_next_state;
proto_next_state = PROTO_STATE_INVALID;
switch (next_state)
{
case PROTO_STATE_SEND_SYNC:
sendSync();
break;
case PROTO_STATE_SEND_RTS:
sendRts();
break;
case PROTO_STATE_SEND_CTS:
sendCts();
break;
case PROTO_STATE_SEND_DATA:
sendData();
break;
case PROTO_STATE_SEND_ACK:
sendAck();
break;
default:
assert(false);
}
break;
case PROTO_STATE_WFCTS:
printf(PRINT_MAC, “wait-for-cts timeout”);
setIdle();
break;
case PROTO_STATE_WFDATA:
printf(PRINT_MAC, “wait-for-data timeout”);
setIdle();
break;
case PROTO_STATE_WFACK:
printf(PRINT_MAC, “wait-for-ack timeout”);
setIdle();
break;
default:
assert(false);
}
}
发送同步消息函数
void SMac::sendSync()
{
printf(PRINT_MAC, “sending sync”);
must_send_sync = 0;
proto_state = PROTO_STATE_SEND_SYNC;
Packet *msg = new Packet(“sync”);
msg->local_from = nodeId();
msg->local_to = -1; //-1表示广播
PKT_KIND(msg) = KIND_SYNC;
ushort now = currentTime();
unsigned long est = EST_SYNC_TIME;
assert(time_last_sched+(int)frame_time > now+EST_SYNC_TIME);
unsigned long stime = time_last_sched + frame_time // 下一帧的时间
- now // 下一帧之前的时间
- est; // 发送时延
//- EST_SYNC_TIME; // 发送时延
//assert(now>900);
assert(stime>0);
stime &= 0xFFFF;
assert(stime < frame_time);
PKT_SYNC(msg) = stime;
msg->setLength(SYNC_SIZE);
setRadioTransmit();
reg_tx_overhead(msg);
startTransmit(msg);
}
接收同步消息函数
void SMac::receiveSync(Packet * msg)
{
assert(msg);
reg_rx_overhead(msg);
ushort stime = (ushort) PKT_SYNC(msg);
delete msg;
if (sched_state == SCHED_STATE_STARTUP)
{
cancelTimeout(TIMER_SCHED);
printf(PRINT_MAC, “received SYNC, following”);
setMySchedule(stime);
return;
}
// 检查偏移
int ftime = (int)currentTime() + stime; // 帧启动时间
if (isSameSchedule(ftime, time_last_sched))
{
printf(PRINT_MAC, “received SYNC, my own schedule”);
return;
}
// 检查其他调度
int i;
for (i = 0; i < sched_count; i++)
{
if (isSameSchedule(ftime, time_last_sched + sched_table[i]))
{
printf(PRINT_MAC, “received SYNC, known schedule”);
return;
}
}
// 新的调度
printf(PRINT_MAC, “adopting foreign schedule”);
int offset = ftime - time_last_sched;
if (offset < 0)
offset += 65536;
offset %= frame_time;
assert(offset > 0);
//assert(offset < (int)frame_time);
adoptSchedule(offset);
}
计算调度状态函数
void SMac::calcSchedState()
{
ushort t = currentTime();
unsigned in_f = (ushort) (t - time_last_sched);
assert(listen_time>0);
// 检查是否在自己当前帧的发送时间内
if ( /*in_f >=0 && */ in_f < listen_time)
{
sched_state = SCHED_STATE_OWN;
ushort left = listen_time + 5 - in_f;
assert(left <= listen_time + 5);
printf(PRINT_MAC, “calc_sched: in own frame, left = %u”, (unsigned) left);
setSchedTimeout(left);
return;
}
// 检查自己是否在下一个侦听帧中
if (in_f > frame_time - 5 && in_f < frame_time + listen_time)
{
time_last_sched += frame_time;
in_f -= frame_time;
if (in_f == 0) { //检查帧开始
resync_counter–;
if (resync_counter <= 0) {
must_send_sync = 1;
resync_counter = NEW_RESYNC_COUNTER;
}
}
sched_state = SCHED_STATE_OWN;
ushort left = listen_time + 5 - in_f;
assert(left <= listen_time + 10);
printf(PRINT_MAC, “calc_sched: in next frame, left = %u”, (unsigned) left);
setSchedTimeout(left);
return;
}
// 检查自己是否在其他侦听帧中
assert(in_f < frame_time);
int i;
for (i = 0; i < sched_count; i++)
{
if (in_f > (unsigned) sched_table[i] - 5 && in_f < sched_table[i] + listen_time)
{
// 是
sched_state = SCHED_STATE_OTHER;
unsigned end_in_f = sched_table[i] + listen_time;
if (end_in_f > frame_time)
{
// 没有错过自己的时间间隔
end_in_f = frame_time;
}
ushort left = end_in_f - in_f + 5;
assert(left <= listen_time + 10);
printf(PRINT_MAC, “calc_sched: in foreign frame %d, left = %u”, i,
(unsigned) left);
setSchedTimeout(left);
return;
}
}
// 不在任何侦听帧中. 计算睡眠时间
sched_state = SCHED_STATE_SLEEP;
unsigned wake_at = frame_time;
// 检查是否有帧更早启动
for (i = 0; i < sched_count; i++)
{
if (sched_table[i] > in_f && sched_table[i] < wake_at)
wake_at = sched_table[i];
}
ushort left = wake_at - in_f;
assert(left <= sleep_time);
printf(PRINT_MAC, “calc_sched: in no frame, left = %u”, (unsigned) left);
setSchedTimeout(left);
if (getForce() != FORCE_NOSLEEP)
setRadioSleep();
return;
}
4.6 小结
本章介绍和分析了无线传感器网络中的MAC协议设计。结合传感器网络MAC协议分
类，介绍了几种无线传感器网络典型MAC协议。最后采用OMNeT++仿真实现了S-MAC协议，并给出具体分析。
无线传感器网络的MAC协议设计，需要考虑传感器网络的特性，结合不同的应用，侧
重不同的需求。充分利用传感器网络的分布式特点和对能量消耗的要求，结合节点的硬件条件和无线通信的信道条件，从功耗，信道接入，公平度，时延，吞吐量等不同方面设计扩展性强，鲁棒性好的协议。为网络上层提供稳定高效的比特通道，避免和解决媒体接入的竞争问题。
参考文献
[1] Ye W, Heidemann J, Estrin D. An energy-efficient MAC protocol for wireless sensor networks[C]. In: Proc 21st Int’l Annual Joint Conf IEEE Computer and Communications Societies (INFOCOM 2002), New York, NY, June 2002.
[2] Langendoen K, Van Dam T. An adaptive energy-efficient MAC protocol for wireless sensor networks.[C] In: Proc 1st Int’l Annual Joint Conf on Embedded Networked Sensor Systems (SenSys), Nov. 5-7,2003, Los Angeles, CA. 2003
[3] J. Ai, J. Kong, D. Turgut, An adaptive coordinated medium access control for wireless sensor networks, in: Proceedings of the International Symposium on Computers and Communications, Vol. 1, 2004, pp. 214–219.
[4] Lu G, Krishnamachari B, Raghavendra C. An adaptive energy-efficient and low-latency MAC for data gathering in wireless sensor networks.[C] In: Proc 18th Int’l Parallel and Distributed Processing Symp (IPDPS’04), April 26-30, 2004, Santa Fe, New Mexico. 224~230
[5] Rajendran V, Obracazka K, Garcia-Luna-Aceves J J. Energy-efficient, collision-free medium access control for
wireless sensor networks[A]. Proc 1st Int’l Annual Joint Conf on Embedded Networked Sensor Systems (SenSys)[C], Nov. 5-7,2003, Los Angeles, CA. 181~192
[6] Chatterjea S, van Hoesel L FW, Havinga P J M. AI-LMAC: An Adaptive, information-centric and lightweight MAC protocol for wireless sensor network[C]. IEEE ISSNIP, 2004.381-388.
[7] Sohrabi K, Gao J, Ailawadhi V, Pottie G J. Protocol for self-organization of a wireless sensor network.[M] IEEE Personal Communications Magazine, 2000, 7(5): 16~27
[8] Guo C, Zhong L, Rabaey J M. Low-power distributed MAC for ad hoc sensor radio networks.[C] In: Proc Internet Performance Symp (Globecom’01), San Antonio, TX, Nov. 2001. 2944~2948
[9] Le Boudec, J.-Y. Merz, R.Radunovic, B.Widmer, J. DCC-MAC: a decentralized MAC protocol for 802.15.4a-like UWB mobile ad-hoc networks based on dynamic channel coding. Broadband Networks, 2004. BroadNets 2004. Proceedings. First International Conference on
[10] M.Z.Win and R.A.Scholtz. Ultra-wide bandwidth time-hopping spread-spectrum impulse radio for wireless multiple-access communication. IEEE Transaction on Communication, 48(4):679-691,April 2000.
[11] IEEE 802.15.4a approved technical requirements document, may 04 - 04/198r2, available at
http://www.ieee.
[12] 孙利民, 李建中, 陈渝, 朱红松. 无线传感器网络. 北京: 清华大学出版社, 2005.
第五章 网络层仿真
概述
无线传感器网络中的路由协议主要任务是将数据分组从事件节点通过网络转发到目的节点，它主要包括两个方面的功能:寻找事件节点和目的节点间的优化路径，并将数据分组沿着优化路径正确转发。传统的无线网络的路由协议主要以避免网络拥塞、保持网络的连通性、提高网络QOS为主要目标[1]，原因是：
(1) 节点数量众多，分布密集。由于传感器网络通常工作在人难以接近或者危险的区域内，为了对一个区域执行监测任务，往往有成千上万传感器节点空投到该区域，外界的不确定性使得必须布置大量的传感节点并使之协同工作才能完成信息收集等任务；同时利用节点之间高度连接性来保证系统的容错性和抗毁性。
(2) 传感器节点的存储空间、计算能力和能量非常有限。节点由于受价格、体积和功耗的限制，其计算能力、程序空间和内存空间比普通的计算机功能要弱很多。技术的进步会降低器件的成本，但就目前的现状而言传感器节点资源紧张的状况还不会得到迅速的缓解。
(3) 电源容量有限，能耗是被首要考虑的因素。传感器网络特殊的应用领域决定了节点散布之后，不能更换电池或给电池充电，一旦电池能量用完，这个节点也就失去了作用（死亡）。因此，降低和平衡节点能耗，延长网络的生存时间就成为传感器网络研究中的一个关键领域，在传感器网络设计过程中，任何技术和协议的使用都要以节能为前提。
5.1 无线传感器网络路由协议研究
5.1.1 无线传感器网络协议分类
WSNs路由协议负责在sink点和其余节点间可靠地传输数据。由于WSNs与应用高度相关，单一的路由协议不能满足各种应用需求，因而人们研究了众多的路由协议。为揭示协议特点，我们根据路由协议采用的通信模式、路由结构、路由建立时机、状态维护、节点标识和投递方式等策略，运用多种分类方法对其进行了分类。由于研究人员组合多种策略来实现路由机制，故同一路由协议可分属不同类别 [2-4]. ：
(1) 根据传输过程中采用路径的多少，可分为单路径路由协议和多路径路由协议。单路径路由节约存储空间，数据通信量少；多路径路由容错性强，健壮性好，且可从众多路由中选择一条最优路由。
(2) 根据节点在路由过程中是否有层次结构、作用是否有差异,可分为平面路由协议和层次路由协议。平面路由简单，健壮性好，但建立、维护路由的开销大，数据传输跳数多，适合小规模网络；层次路由扩展性好，适合大规模网络，但簇的维护开销大，且簇头是路由的关键节点，其失效将导致路由失败。
(3) 根据路由建立时机与数据发送的关系，可分为主动路由协议、按需路由协议和混合路由协议。主动路由建立、维护路由的开销大，资源要求高；按需路由在传输前需计算路由,时延大;混合路由则综合利用这两种方式。
(4) 根据是否以地理位置来标识目的地、路由计算中是否利用地理位置信息，可分为基于位置的路由协议和非基于位置的路由协议。.有大量WSNs应用需要知道突发事件的地理位置，这是基于位置的路由协议的应用基础，但需要GPS定位系统或者其他定位方法协助节点计算位置信息。
(5) 根据是否以数据来标识目的地，可分为基于数据的路由协议和非基于数据的路由协议。有大量WSNs应用要求查询或上报具有某种类型的数据，这是基于数据的路由协议的应用基础，但需要分类机制对数据类型进行命名。
(6) 根据节点是否编址、是否以地址标识目的地，可分为基于地址的路由协议和非基于地址的路由协议。基于地址的路由在传统路由协议中较常见，而在WSNs中一般不单独使用而与其他策略结合使用。
(7) 根据路由选择是否考虑QoS约束,可分为保证QoS的路由协议和不保证QoS的路由协议。保证QoS的路由协议是指在路由建立时，考虑时延、丢包率等QoS参数，从众多可行路由中选择一条最适合QoS应用要求的路由。
(8) 根据数据在传输过程中是否进行聚合处理，可分为数据聚合的路由协议和非数据聚合的路由协议。数据聚合能减少通信量，但需要时间同步技术的支持,并使传输时延增加。
(9) 根据路由是否由源节点指定，可分为源站路由协议和非源站路由协议。源站路由协议节点无须建立、维护路由信息，从而节约存储空间，减少通信开销。但如果网络规模较大，数据包头的路由信息开销也大，而且如果网络拓扑变化频繁，将导致路由失败。
(10) 根据路由建立时机是否与查询有关，可分为查询驱动的路由协议和非查询驱动的路由协议。查询驱动的路由协议能够节约节点存储空间，但数据时延较大，且不适合环境监测等需紧急上报的应用。
5.1.2 无线传感器网络中平面路由
平面路由算法主要特点有：所需的信息域较小，一般仅需一跳（1 hop）内的信息；无需进行周期性的路由信息维护；复杂度较低。
（1）扩散法（Flooding）[5]：扩散法是一种传统的网络通信路由协议。源节点Source将报文传送给它的每一个邻居节点, 每一个邻居节点又将其传输给各自的所有邻居节点。如此继续下去, 直到将数据传输到汇集点Sink或为该报文所设定的生命期限变为零为止。
（2）闲聊法（Gossiping）[5]：Gossiping是对Flooding算法的一种改进，算法中节点随机选取一个相邻节点转发它接收到的分组，而不是采用广播形式。这种方法避免了消息的“内爆”现象，但有可能增加端到端的传输延时。
（3）SAR（Sequential Assignment Routing）：算法创建多棵树，每棵树的树根都是Sink的一跳邻居。在算法的初始阶段，树从根节点开始，不断吸收新的节点加入。在树延伸的过程中，将避免那些QoS不好及能量已经消耗较多的节点。初始阶段结束后，大多数节点都加入了某个树，各节点只需要知道自己的上一跳邻居，以转发报文。在网络工作过程中，一些树可能由于中间节点能量耗尽而断开，也可能有新的节点加入网络而使网络拓扑结构发生变化。所以网关周期性的发起“重新建立路径”的命令，以保证网络的连通性和最优的服务质量。
（4）SPIN ( Sensor Protocol for Information via Negotiation)[6]：算法用临时的请求/应答方式转发数据。Source和收到数据的节点向其邻接点发广告报文ADV表示自己有数据要发送（ADV中包括了对即将发送数据的描述）；有兴趣的邻接点发REQ报文响应；而后发送节点将数据封装为DATA发送过去，如此转发直到Sink。
算法通过使用节点间的协商制度和资源自适应机制, 解决了Flooding中存在的不足之处，即为了避免出现扩散法的信息爆炸问题和部分重叠现象, 传感器节点在传送数据之前彼此进行协商, 协商制度可确保传输有用数据。另外，节点间通过发送源数据(即描述传感器节点采集的数据属性的数据)而不是采集的整个数据进行协商。
（5）定向扩散（Directed Diffusion, DD）[7]：该模型是 Estrin 等人针对传感器节点资源有限等特点设计的路由策略。其实现机制如下：Sink 向所有传感器节点发送兴趣(兴趣是通过分配不同的属性值来表示不同任务的描述符) , 每个传感器节点在收到兴趣后将其保存在各自的 CACHE 中。每个兴趣项包含一个时间标签域和若干个梯度域。当一个兴趣传遍整个网络后, 从 Source 到 Sink 之间的梯度就建立起来了，梯度反映了网络中节点对匹配请求条件的数据源的近似判断。一旦Source 采集到兴趣所需的数据, 那么它将沿着该兴趣的梯度路径传输数据到汇集点或基站。
DD 中的网络梯度思想源自生物学中的蚂蚁种群模型。研究人员在实验过程中发现绝大多数盲蚂蚁在擦肩而过时通过彼此发送信息激素可找到一条从源点到目标点的最短路径。透过这一现象, 将其思想引用到网络中就产生了网络梯度的概念。图 5.1 描述了定向扩散模型的基本工作原理。
A．兴趣传播阶段 B.初始梯度的建立 C.数据沿增强路径传输
图5.1 DD 的实现机制
（6）Rumor协议[8] ：如果sink点的一次查询只需一次上报，Directed Diffusion协议开销就太大了，Rumor协议正是为解决此问题而设计的。该协议借鉴了欧氏平面图上任意两条曲线交叉几率很大的思想。当节点监测到事件后将其保存，并创建称为Agent的生命周期较长的包括事件和源节点信息的数据包，将其按一条或多条随机路径在网络中转发。收到Agent的节点根据事件和源节点信息建立反向路径，并将Agent再次随机发送到相邻节点，并可在再次发送前在Agent中增加其已知的事件信息。sink点的查询请求也沿着一条随机路径转发，当两路径交叉时则路由建立；如不交叉，sink点可flooding查询请求。在多sink点、查询请求数目很大、网络事件很少的情况下，Rumor协议较为有效。但如果事件非常多，维护事件表和收发Agent带来的开销会很大。图3表示了Rumor协议中Agent传播和Agent路径与查询路径的交叉情形。.
5.1.3 无线传感器网络中层次化路由
在层次路由算法中，网络通常被划分为簇（cluster），每个簇由一个簇头（cluster-head）和多个簇成员（cluster-member）组成，低一级网络的簇头是高一级网络中的簇成员。在这种分级结构中，簇头不仅负责簇内信息的收集和融合处理，还负责簇间数据转发。层次路由协议中簇的形成通常是基于节点的能量和其与簇头间的距离。为了延长整个网络的生存期，簇头节点需要周期更新。层次路由的优点是便于管理，可以对系统变化做出快速反应，能够提供高质量的通信服务，能量利用率较高。但簇的维护开销较大。
（1）LEACH（Low-Energy Adaptive Clustering Hierarchy）[9]：该协议是由Heinzelman 等人提出的。协议将操作分为若干轮（round），每轮包括创建阶段和稳定运行阶段。在创建阶段，每个节点取一个介于0 和1 之间的随机数q。若q大于门限值T(n)则该节点成为簇头。
当节点 n∈G时门限值T(n) =1/{1-P×[r mod (1/p)]}；否则T(n) = 0。其中p是簇头总数占全部节点总数的百分比；r是当前的轮次；G是在最近轮没有成为簇头的节点集合而后，簇头向所有节点广播这一消息。依据接收信号的强度，节点选择它所要加入的组，并告知相应的簇头。在稳定工作阶段，节点持续采集监测数据，传给本簇簇头，簇头进行数据融合处理后将数据发送到Sink。稳定工作阶段持续一段时间后，整个网络进入下一轮工作周期，重新选择簇头并分簇。
（2）TEEN（Threshold Sensitive Energy Efficient Sensornetwork Protocol）[11]：TEEN和LEACH的实现机制非常相似，只是TEEN中定义了硬、软两个门限值，以确定是否需要发送监测数据。只有当传感器检测的信息超过了设定的门限时才向簇头发送数据。当监测数据第一次超过设定的硬门限时，节点用它作为新的硬门限，并在接着到来的时隙内发送它。在接下来的过程中，如果监测数据的变化幅度大于软门限界定的范围，则节点传送最新采集的数据，并将它设定为新的硬门限。通过调节软门限值的大小，可以在监测精度和系统能耗之间取得合理的平衡。当检测的值超过了硬门槛，它被立刻发送出去；如果当前检测的值与上一次之差超过了软门限，也被立刻发送出去。采用这样的方法，可以监视一些突发事件和热点地区，减小网络内传输的报文数量。
（3）PEGASIS（Power-Efficient Gathering in Sensor Information Systems）[10]：PEGASIS也是由LEACH发展而来。它假定组成网络的传感器节点是同构且静止的，节点发送能量递减的测试信号，通过检测应答来确定离自己最近的相邻节点。通过这种方式使网络中的所有节点了解彼此的位置关系，进而每个节点依据自己的位置选择要加入的簇。簇头参照位置关系优化出到Sink节点的最佳链路。因为PEGASIS中每个节点都以最小功率发送数据分组,并有条件完成必要的数据融合，减小业务流量，因此整个网络的功耗较小。但其缺点在于节点维护位置信息需要额外的资源，而这一位置信息相当于传统网络中的拓扑信息。
(4) TTDD协议[12] ：这是一个层次路由协议，主要是解决网络中存在多sink点及sink点移动问题。当多个节点探测到事件发生时，选择一个节点作为发送数据的源节点，源节点以自身作为格状网(grid)的一个交叉点构造一个格状网。其过程是：源节点先计算出相邻交叉点位置，利用贪心算法请求最接近该位置的节点成为新交叉点，新交叉点继续该过程直至请求过期或到达网络边缘。交叉点保存了事件和源节点信息。进行数据查询时，sink点本地flooding查询请求到最近的交叉节点，此后查询请求在交叉点间传播，最终源节点收到查询请求，数据反向传送到sink点。Sink点在等待数据时，可继续移动，并采用代理(Agent)机制保证数据可靠传递。与Directed Diffusion协议相比，该协议采用单路径，能够提高网络生存时间，但计算与维护格状网的开销较大；节点必须知道自身位置；非sink点位置不能移动；要求节点密度较大。图8表示TTDD协议的格状网建立与数据查询情况。
（5）Estrin等人提出了多层分簇算法——一种新型的分簇实现机制。工作在网络中的传感器节点处于不同的层，所处层次越高，传感器能覆盖的面积就越大。开始时所有节点均在最低层，通过竞争获得提升高层的机会。在每个工作周期结束后，高层节点将视自己的状态信息(如有无子节点，功率是否充足等)决定是否让出簇头位置。
（6）Younis 等人提出了基于三层体系结构的路由协议。与LEACH 不同的是，该协议要求在网络运行前由终端用户将传感器节点划分成簇，并通知每个簇头节点的ID 标识和簇内所分配节点的位置信息。簇内节点可以以感知、转发、感知并转发、休眠这四种方式之一存在。簇头不受能量的限制，它可以监控节点的能量变化，决定并维护传感器的四种状态，并利用代价函数作为链路成本，选择最小成本的路径作为节点与其通信的最优路径。
5.1.4 经典算法的OMNET仿真
图5.2 OMNET 仿真框架图
用OMNET仿真路由算法的模块图如图5.2所示，传感器节点由四个模块构成，sm_application主要是应用层模块的程序，sm_cordinator模块是一个协调模块，协调各部分的模块工作，sm_layer0模块负责节点间的数据包的传送，以及路由的选择，sm_energy模块是能量模块。
图5.3 无线传感器网络拓扑图
1 Leach 算法的实现：
A Leach算法的原理参考5.2.3节
B 算法流程图：
C 算法关键部分代码
#include “application.h”
#include <math.h>
//消息定义
//初始化消息
#define SELF_INITIALIZE {
cMessage *msg = new cMessage(“SET_UP”);
msg->setKind(M_SELF);
scheduleAt(0.1,msg);
if(OCCUPATION != 5)
SEND_DECREASE_ENERGY(3);
}
//建立状态
#define SET_UP_PHASE {
cMessage *msg = new cMessage(“SET_UP”);
msg->setKind(M_SELF);
scheduleAt(simTime()+ 9000,msg);
if(OCCUPATION != 5)
SEND_DECREASE_ENERGY(3);
}
//等待建簇
#define WAITING_INVITATION_TIMER {
cMessage *msg = new cMessage(“WAIT_INVITATION_TIME_OUT”);
msg->setKind(M_SELF);
scheduleAt(simTime()+ 10,msg);
if(OCCUPATION != 5)
SEND_DECREASE_ENERGY(3);
}
//减少能量
#define SEND_DECREASE_ENERGY(QUANTITY){
cMessage *msg = new cMessage(“DECREASE_ENERGY”);
msg->addPar(“quantity”) = (int)QUANTITY;
send(msg,“cordinator_out”);
}
//建簇消息
#define SEND_INVITATION {
cMessage *msg = new cMessage(“INVITATION”);
msg->setKind(M_HIGHLOW);
msg->addPar(“group_id”) = ID;
send(msg,“lowergate_out”);
if(OCCUPATION != 5)
SEND_DECREASE_ENERGY(29);
}
//发送数据消息
#define SEND_SENSED_INFO {
cMessage *msg = new cMessage(“SENSING_DATA”);
msg->setKind(M_HIGHLOW);
msg->addPar(“time”) = simTime();
msg->addPar(“source”) = ID;
msg->addPar(“destination”) = FATHER;
msg->addPar(“X”) = PX;
msg->addPar(“Y”) = PY;
send(msg,“lowergate_out”);
if(OCCUPATION != 5)
SEND_DECREASE_ENERGY(820);
}
//初始化,组ID标识为false
void application::initialize()
{
group_flag = false;
SELF_INITIALIZE;
WAITING_INVITATION_TIMER;
}
void application::finish()
{
}
void application::handleMessage(cMessage *msg)
{
switch(msg->kind())
{
case M_SELF:
{
if (strcmp(msg->name(),“SET_UP”)==0)
{
//建立状态
//clean up the marked connection
if(OCCUPATION == 2)
{
UPDATECOLOR(“white”);
if (ev.isGUI())
parentModule()->gate("out",FATHER)->setDisplayString("m=m;o=lightgrey,0;");
}
//Delete father
this->parentModule()->par("FATHER")= 0;
if(OCCUPATION == 1)
{
//重置为普通节点
this->parentModule()->par("OCCUPATION") = 2;
//连接簇头节点
this->parentModule()->gate(“out”,MAXCONN -1)->disconnect();
this->parentModule()->gate(“in”,MAXCONN -1)->fromGate()->disconnect();
UPDATECOLOR(“white”);
}
if(OCCUPATION != 5)//Not the base
{
// 随机选择簇头
int cluster_head = rand()% (HEAD_DISTRIBUTION);
//if cluster_head = HEAD_DISTRIBUTION --> head cadidate
if(cluster_head == HEAD_DISTRIBUTION - 1)
{
//变成簇头节点
this->parentModule()->par(“OCCUPATION”)= 1;
group_flag =true;
SEND_INVITATION;
//更改显示
if (ev.isGUI())
UPDATECOLOR(“blue”);
}
}
delete msg;
break;
}
else if(strcmp(msg->name(),"WAIT_INVITATION_TIME_OUT")==0)
{
if(group_flag == false)//没有加入任何组
delete msg;
break;
}
else
{
ev << "unknown message received from another node.\n";
endSimulation();
}
}
case M_LOWHIGH:
{
if (strcmp(msg->name(),"SENSING_DATA")==0)
{
SEND_DECREASE_ENERGY(100);
forward(msg);
delete msg;
break;
}
else if (strcmp(msg->name(),"INVITATION")==0)
{
SEND_DECREASE_ENERGY(3);
//如果节点没有加入任何组
if(FATHER == 0 && OCCUPATION == 2) //occupation = 2 means not a cluster head or base
{
//设置组ID,父节点号
parentModule()->par("FATHER") = msg->par("group_id");
group_flag =true; //组ID标识为真表明加入其他组
if (ev.isGUI()) parentModule()->gate("out",FATHER)->setDisplayString("m=a;o=blue,0;");
}
delete msg;
break;
}
else if (strcmp(msg->name(),"SENSOR_INFO")==0)
{
if(SENSOR_SWITCH) {
SEND_DECREASE_ENERGY(100);
parentModule()->bubble("DETECTED") ;
SEND_SENSED_INFO;
}
delete msg;
break;
}
else
{
ev << "unknown message received from another node.\n";
endSimulation();
}
}
default:
{
ev << "unknown message received\n";
endSimulation();
}
}
}
void application::forward(cMessage msg)
{
if((int)msg->par(“destination”) == ID)
{
if(OCCUPATION == 1) //簇头节点
{
//前传信息给Sink节点
cMessage tmpmsg = new cMessage(“SENSING_DATA”);
tmpmsg->setKind(M_HIGHLOW);
tmpmsg->addPar(“time”) = msg->par(“time”);
tmpmsg->addPar(“source”) = ID; //message from cluster head
tmpmsg->addPar(“destination”) = FATHER;
tmpmsg->addPar(“X”) = msg->par(“X”);
tmpmsg->addPar(“Y”) = msg->par(“Y”);
send(tmpmsg,“lowergate_out”);
if(DISTANCE > CRADIUS)
{
SEND_DECREASE_ENERGY(200+ 0.1DISTANCEDISTANCE); }
else
{
SEND_DECREASE_ENERGY(920);//100 for creating + 820 for sending
}
parentModule()->bubble("FWD");
}
else if(OCCUPATION == 5) //基站节点
{
sprintf(str,"%d,%d",(int)msg->par("X"),(int)msg->par("Y"));
parentModule()->bubble(str);
}
}
}
图5.4 Leach 算法结果演示图
结果演示图解释：红色节点标识Sink节点，黄色节点标识普通源节点，蓝色节点标识簇头节点，源节点之间通过随机簇头选举机制选出簇头节点，簇头节点然后直接将收集到的数据传送给Sink节点。
5.2 无线传感器网络路由协议研究的发展趋势
由于WSNs资源有限且与应用高度相关，研究人员采用多种策略来设计路由协议。其中好的协议具有以下特点：针对能量高度受限的特点，高效利用能量几乎是设计的第一策略；针对包头开销大、通信耗能、节点有合作关系、数据有相关性、节点能量有限等特点，采用数据聚合、过滤等技术；针对流量特征、通信耗能等特点，采用通信量负载平衡技术；针对节点少移动的特点，不维护其移动性；针对网络相对封闭、不提供计算等特点，只在sink点考虑与其他网络互联；针对网络节点不常编址的特点，采用基于数据或基于位置的通信机制；针对节点易失效的特点，,采用多路径机制，通过对当前的各种路由协议进行分析与总结，可以看出将来WSNs路由协议采用的某些研究策略与发展趋势：
(1) 减少通信量以节约能量。由于WSNs中数据通信最为耗能，因此应在协议中尽量减少数据通信量。例如，可在数据查询或者数据上报中采用某种过滤机制，抑制节点上传不必要的数据：采用数据聚合机制，在数据传输到sink点前就完成可能的数据计算。
(2) 保持通信量负载平衡。通过更加灵活地使用路由策略让各个节点分担数据传输，平衡节点的剩余能量，提高整个网络的生存时间。例如，可在层次路由中采用动态簇头；在路由选择中采用随机路由而非稳定路由；在路径选择中考虑节点的剩余能量。
(3) 路由协议应具有容错性。由于WSNs节点容易发生故障，因此应尽量利用节点易获得的网络信息计算路由，以确保在路由出现故障时能够尽快得到恢复；并可采用多路径传输来提高数据传输的可靠性。
(4) 路由协议应具有安全机制。由于WSNs的固有特性，其路由协议极易受到安全威胁，尤其是在军事应用中。.目前的路由协议很少考虑安全问题，因此在一些应用中必须考虑设计具有安全机制的路由协议。
(5) WSNs路由协议将继续向基于数据、基于位置的方向发展。这是由WSNs一般不统一编址和以数据、位置为中心的特点决定的。
5.3 无线传感器网络层路由协议与OMNET++仿真
5.3.1 无线传感器网络层路由与OMNET++仿真的基本概念[19]
集传感、卫星定位、数据处理及网络通信功能于一体的无线集成网络传感器[20]，具有体积小、价格便宜、彼此之间可以近距离无线通信等特性，因此在环境与军事监控、地震与气候预测、地下、深水以及外层空间探索等方面具有非常广泛的应用前景。而外界环境的不确定性导致需要布置成百上千个传感器协同工作，故对由大规模传感器构成的传感器网络的研究正引起广泛关注，并被认为是本世纪一项具有挑战性的研究课题[21]。
作为一种新型的无线自组织网络[22]，传感器网络与传统的移动Ad Hoc网络(M0bile Ad hoe Networks，MANET)相比，有着以下的不同之处：
(1)网络规模不同：在MANET中，节点数量较少，而在传感器网络中，由于节点稠密分布，节点数量比MANET指数级增加；
(2)节点的能量、存储及处理能力不同：在MANET中，节点的能量较大且可补充，节点具有较强的存储及数据处理能力，受环境的影响小；而在传感器网络中，节点的能量、存储及数据处理能力十分有限，且节点通常运行在人无法接近的恶劣甚至危险的远程环境中，节点的能源无法补充，易于受环境的影响而失效。
5.3.1.1 传感器网络的体系结构
5.3.1.1.1 传感节点的物理结构
传感节点一般由传感单元、数据处理单元、GPS定位装置、移动装置、能源(电池)及网络通信单元(收发装置)等6大部件组成[23-27] 。其中传感单元负责被监测对象原始数据的采集，采集到的原始数据经过数据处理单元的处理之后，通过无线网络传输到一个数据汇聚中心节点Sink，Sink再通过因特网或卫星传输到用户数据处理中心。其结构如下图1所示。
5.3.1.1.2 传感器网络的体系结构与网络模型
传感器网络的体系结构：
传感器网络的体系结构如图2所示。在传感器网络中，节点被任意散落在被监测区域内，以自组织形式构成网络，通过多跳(Multi-hops)中继方式将监测数据传到Sink节点，最后Sink节点借助卫星链路或临时建立的Sink链路将汇聚数据传送到远程中心进行集中处理。
传感器网络的网络模型：
依据传感器网络节点的连接特点，可以利用图论的方法将传感器网络抽象成一种单位圆平面图，即假设传感节点具有相同的有效传输半径，则认为彼此处于传输半径范围内(半径为R内的平面圆内)的节点之间存在一条单位长度的无向边。按照源节点的分布情况，传感器网络模型可分为事件半径模型和随机源节点模型两类。事件半径模型表示以待监测的事件为圆心，半径为R的圆内的所有非Sink节点的传感节点被选择作为数据源所构成的网络模型。而随机源节点模型则通过随机选择k个非Sink节点的传感节点作为数据源，从而构成的网络模型。
5.3.2 传感器网络层路由协议的基本概念
5.3.2.1 网络通信模式[28]
当前的网络中有三种通讯模式：单播、广播、组播(多播)，其中的组播出现时间最晚但同时具备单播和广播的优点，最具有发展前景。
5.3.2.1.1 单播：
Sink节点与目标节点之间“一对一”的通讯模式，网络中的节点和Sink节点对数据只进行转发不进行复制。如果10个目的节点需要相同的数据，则Sink节点需要逐一传送，重复10次相同的工作。单播能够针对每个节点作出及时的响应。网络中的Sink节点根据其目标地址选择传输路径，将单播数据传送到其指定的目的节点。
单播的优点：
Sink节点能够及时响应目标节点的请求。
Sink节点针对每个节点不同的请求发送不同的数据，容易实现个性化服务。
单播的缺点：
Sink节点针对每个目标发送数据流，Sink节点流量＝目标节点数量×各跳数；在目标节点量大、到每个目标节点跳数多的应用中Sink节点不堪重负。
现有的网络带宽是金字塔结构，城际省际主干带宽仅仅相当于其所有用户带宽之和的5％。如果全部使用单播协议，将造成网络主干不堪重负。
5.3.2.1.2 广播：
Sink节点与目标节点之间“一对所有”的通讯模式，网络对其中每一各节点发出的信号都进行无条件复制并转发，所有节点都可以接收到所有信息（不管你是否需要），由于其不用路径选择，所以其网络成本可以很低廉。
广播的优点：
网络设备简单，维护简单，布网成本低廉。
由于Sink节点不用向每个节点单独发送数据，所以Sink节点流量负载极低。
广播的缺点：
无法针对每个节点的要求和时间及时提供个性化服务。
网络允许节点提供数据的带宽有限，节点的最大带宽＝Sink节点总带宽。无法向众多节点提供更加多样化、更加个性化的服务。
5.3.2.1.3 组播：
Sink节点与目标节点之间“一对一组”的通讯模式，也就是加入了同一个组的节点可以接受到此组内的所有数据，网络中的Sink节点和首节点只向有需求者复制并转发其所需数据。节点可以向首节点请求加入或退出某个组，网络中的Sink节点和首节点有选择的复制并传输数据，即只将组内数据传输给那些加入组的节点。这样既能一次将数据传输给多个有需要（加入组）的节点，又能保证不影响其他不需要（未加入组）的节点的其他通讯。
组播的优点：
需要相同数据流的目标节点加入相同的组共享一条数据流，节省了服务器的负载。具备广播所具备的优点。
由于组播协议是根据接受者的需要对数据流进行复制转发，所以服务端的服务总带宽不受客户接入端带宽的限制。
组播的缺点：
与单播协议相比没有纠错机制，发生丢包错包后难以弥补，但可以通过一定的容错机制和QOS加以弥补。
无线网络虽然有支持组播的传输，但在客户认证、QOS等方面还需要完善，这些缺点在理论上都有成熟的解决方案，只是需要逐步推广应用到网络当中。
5.3.2.2 传感器网络层设计[29]
网络层负责路由查找和数据包传送。自组织传感器网络中大量节点是随机部署的，因此在网状网中查找多跳路由十分困难，当节点出现故障或重新部署后进行路由维护和修复(自愈)将同样困难。过去几年中出现了大量可支持自组多跳网络的分布式路由算法。总的来说，这些路由算法可分为两类：主动式(proactive)和被动式(reactive)。在主动式路由协议中，网络中的所有节点都常常保持着源地址与目的地址之间的路由列表，不管是否需要这些路由。
由于无需花时间查找路由，主动式路由能比被动式路由更快地传输数据包。不过，随着网络规模增加，这些路由列表也呈指数级增加，因此对于包含大量节点的典型传感器网络来说，要继续保持这些列表十分困难。而在被动式路由协议中，源节点只有在需要向某个目的节点传输数据时才开始查找路由。找到路由后该节点会将路由信息保持一定时间。路由列表规模相对较小，与网络规模大致相同。不过查找路由通常会有较长的延时，在要求实时性的应用中不可采用。
多数自组移动网采用的分布式路由算法都是基于网状网等平面网络结构而开发的，而无论是主动式路由还是被动式路由。由于自组网不分层，每个节点都充当其它节点的中继，其承担的责任相同。在这种采用全分布式路由算法的平面网络中，不进行传输的所有节点都必须主动监听信道，以实现中继。因此，网状网中的分布式路由算法产生较高的功耗。使用星型-网状混合结构可开发一种智能路由，实现高功效、降低延时并增强连接性。由于每个传感器的路由列表存储空间有限，被动式路由可为传感器网络应用提供更紧凑的解决方案。通过将信息传输到充当数据集中站的少量节点上，可有效解决被动式路由的延时问题。每个集中站负责收集邻近区域的通信信息。
将通信保持在局部邻近范围内十分重要，它可保证自组网的可伸缩性。据观察，每个节点的传输能力随着自组网规模增加而下降，这是因为网络规模增大后源节点与目的节点间的平均路径长度也成比例增加。为了避免大型网络中的节点传输能力逐渐降低，网络中所有通信都应当保持在局部区域内，即数据包的平均跳跃次数应该比网络的总中继数少。
5.3.3 OMNET++仿真软件的基本概念
OMNET++是一个事件驱动的仿真器，适合做离散事件网络系统仿真。通常可进行通信系统通信模型仿真、协议仿真、硬件体系结构验证、复杂软件系统性能评估、任何其他离散事件驱动应用的建模与仿真。它是一种开源的，学术性的和非营利性的使用是免费的离散事件仿真系统，操作时需要自己编写代码，但是有很好的GUI界面，并且可以在GUI中配置参数，其风格有些介于OPNET和NS2之间，与NS2相比，其高度的模块化，使得它在增加一些协议时不需要重现编译整个源代码，使用NED(类似于NS2中使用得TCL)来定义网络的拓扑结构，对基本的网络模块元件使用C++语言来定义其行为。OMNET++仿真软件结构清晰，界面显示丰富，又可以在windows环境下编译、运行，这样就为广大网络仿真软件用户提供了一个非Liunx环境的仿真平台。而且相较于OPNET来讲OMENT++运行速度要快不少，这一点对于大规模网络仿真来讲是一个不错的特点[30]。
它的特征为：
• 模块类型分层次嵌套定义；
• 模块是模块类型的实例；
• 模块间通过通道传递消息；
• 提供灵活的模块参数；
• 网络拓扑描述语言；
OMNET++仿真是基于网络的，网络定义相当于定义了一个复合模块变量（实例）。完全符合OOP思想。
1、simple模块定义
simple 简单模块名
parameters: //参数，在中使用
gates: //外部接口
endsimple
2、复合模块定义
module 复合模块名
parameters: //子模块中使用
gates: //
submodules: //子模块列表
connections: //子模块gates间的连接关系
endmodule
3、网络定义
network 网络名: 复合模块类型名 //不能含gates，整个网络没有外部接口
parameters: //参数初始化列表
endnetwork
4、import子句
引用其它已有描述文件。
5.4 无线传感器网络路由协议介绍
当前无线传感器网络路由协议的研究，从路由发现策略的角度，可以分为主动路由(表驱动table—driven)和被动路由(按需)两种类型；依据网络管理的逻辑结构可分为平面路由和分层结构路由两类[31]。
主动和被动路由协议的路由发现机制和路由信息维护与无线自组网中的路由协议类似，两种路由协议各有优缺点，使用时根据具体的应用要求选择。
平面路由是指各节点在路由功能上地位相同，没有引入分层管理机制，网络流量均匀地分散在网络中，路由算法易于实现。
分层路由协议采用簇的概念对传感器节点进行层次划分，若干相邻节点构成一个簇，每个簇内有一个簇首。簇与簇之间可以通过网关进行通信，网关可以是簇首或是其他簇成员。网关之间的连接构成上层骨干网，所有簇间通信都通过骨干网转发。分层路由协议包括成簇协议、簇维护协议、簇内路由协议和簇问路由协议四个部分。成簇协议解决如何在动态分布式网络环境下使移动节点高效地聚集成簇，它是分层路由协议的关键。簇维护协议要解决在节点移动过程中的簇结构维护，其中包括移动节点退出和加入簇，簇的产生和消亡等功能。分层路由协议比较适合用于无线传感器网络，但成簇过程会产生一定的能源消耗，如何产生有效的簇类是当前的研究热点问题。本章节介绍几种路由协议。
5.4.1 泛洪法(Flooding)[32]
泛洪法是一种传统的网络路由协议，如图3所示。节点S希望发送数据给节点D，首先通过网络将数据副本传给它的每一邻居节点，每一个邻居节点又将其传输给各自的邻居节点，如此继续下去，直到将数据传到目标节点D为止，或者为该数据所设定的生存时间变为零或者所有节点都拥有此数据副本为止。优点是实现简单，不需要为保持网络拓扑信息和实现复杂的路由发现算法而消耗计算资源；适用于健壮性要求高的场合。缺点是①存在信息爆炸问题，即出现一个节点可能得到一个数据多个副本的现象；② 会出现部分重叠现象，如果处于同一观测环境的两个相邻同类传感器同时对一个事件做出反应，二者采集的数据性质相同，数值相近，那么，这两个节点周围的邻居节点将收到双份数据副本；③造成盲目使用资源，即扩散法不考虑各节点能量可用状况，因而无法做出相应的自适应路由选择。
图3 扩散法
5.4.2 定向扩散(Directed Diffusion：DD)[33]
DD算法是一种以数据为中心的路由协议，与已有的路由协议有截然不同的实现机制，其突出特点是引入了梯度来描述网络中间节点对该方向继续搜索获得匹配数据的可能性（图4）。Sink节点向所有传感器节点发送其兴趣(interest，即通过分配不同属性值来表示不同任务的描述符)，每个传感器节点在收到兴趣后保存在各自的缓存中。每个兴趣项(interest entry)包含一个时间标签域和若干个梯度域(按成本最小化和能量自适应原则引导数据扩散的方向)。当一个兴趣传遍整个网络后，从源节点即兴趣所在区域的传感器节点到汇节点之间的梯度就建立起来了。一旦源节点采集到兴趣所需的数据，那么源节点沿着该兴趣的梯度路径传输数据到汇聚节点。其中，源节点采集的数据首先在本地采用数据融合技术进行整合，然后在网上传输。加的缺点是没有形成的到Sink节点多条路由，路由健壮性不好。
图4 定向扩散法
5.4.3 LEACH( Energy Adaptive Clustering Hierarchy)[34]
LEACH是一种基于聚类的分层路由协议，其他许多基于聚类的路由协议大都由LEACH发展而来，协议分为两个操作阶段，簇准备阶段(ready phase)和就绪阶段(set—up phase)；为了使能耗最小化，就绪阶段持续的时间比簇准备阶段要长。簇准备阶段和就绪阶段所持续的时间总和为一轮。在簇准备阶段，LEACH协议随机地选择一个传感器节点作为类头节点，这种随机性选择确保类头节点与Sink之间数据传输的高能耗成本均匀地分摊到所有传感器节点。具体的选择办法是：一个传感器节点随机选择0和l之间的一个值，如果选定的值小于某一个阈值T(n)，那么这个节点成为类头节点。
T(n)值按以下公式计算：
其中，n为网络中传感器节点的总数；P为一轮中网络的簇头节点个数；r已完成的轮数；Gr剩余未成为簇头节点的传感器节点组成的集合。
在簇头节点选定后，该簇头节点对网络中所有节点进行广播，广播数据包含该节点成为簇头节点的信息。一旦传感器节点收到广播数据包，根据接收到的各个类头节点广播信号强度，该节点选择信号强度最大的类头节点加入，向其发送成为其成员的数据包。类形成后，簇头节点采用TDMA策略分配通道使用权给类内节点。簇形成后进人就绪阶段，簇头节点开始接收簇内各节点采集的数据，然后采用数据融合技术进行处理，将整合后的数据传输给汇聚节点。相比平面路由协议，分层的路由协议在路由的发现和数据的传递过程中，消耗的能量较少，建立路径的时间短，可以将网络整体生存时间延长15％。
图5 LEACH算法
5.5. OMNET++仿真实例
5.5.1 泛洪法
泛洪法是基于广播的路由协议，当某个节点完成广播消息的初始化后，就把这条消息发送给它的所有邻居节点。邻居节点是指处于该节点的传输范围内的节点。当某个节点第一次接收到FAM（flooding algorithm message）时，它就接着广播给自己的邻居节点，如已收到过就丢弃该FAM，最终实现整个网络的每个节点都收到过FAM。
如图6所示[35]，泛洪算法的实现是在MAC协议层和应用层之间建立一个泛洪算法层。应用层与泛洪算法层之间有2个操作：应用层发起广播；FA层递交FAM。FA层与MAC层也有2个操作：FA层发送FAM；FA层接收FAM,判断其是继续发送还是丢弃。
图6 仿真网络实体的体系结构
在仿真中，所有的FAM直接发往MAC地址，MAC层接收FAM后直接送到FA层处理，不再需要传输层协议和路由层。
泛洪算法的程序实现相当简单，具体如下：
／／节点i初始化FA发送(AP层)
initiate(i)； ／／初始化
send()； ／／发送FAM，FA层一MAC层
deliver()； ／／递交FAM，FA层一AP层
／／FA层收到FAM后处理(FA层)
if(receive()== true) ／／判断是否第一次收到该FAM
{
deliver()；／／递交FAM，FA层一AP层
send()； ／／转发FAM，FA层一MAC层
}
else discard()；／／丢弃FAM
OMNET中的模块如下图7：
图7 各模块
整个模块中有3种子模块，application模块、layer0模块和manager模块。其中application模块代表的是应用层，layer0模块代表的是FA层，manager模块代表的是调度节点模块，每个模块都有自己的功能。
用NED语言表示出来的代码为：
//-----------------------------------------------
// default components:
//-----------------------------------------------
simple application
gates:
in: lowergate_in;
in: uppergate_in;
in: blackboard_in;
out: lowergate_out;
out: uppergate_out;
endsimple
simple layer0
gates:
in: lowergate_in[];
in: uppergate_in;
in: blackboard_in;
out: lowergate_out[];
out: uppergate_out;
endsimple
//-----------------------------------------------
// sensor node definition:
//-----------------------------------------------
module sensornode
parameters:
CNNCTVTY: numeric,
KIND: numeric,
COLOR: numeric,
PX: numeric,
PY: numeric;
gates:
in: in[];
out: out[];
submodules:
sm_layer0: layer0;
gatesizes:
lowergate_in[CNNCTVTY],
lowergate_out[CNNCTVTY];
display: “p=158,258;i=layer0”;
sm_application: application;
display: “p=158,86;i=application”;
connections nocheck:
for i=0…CNNCTVTY-1 do
in[i] --> sm_layer0.lowergate_in[i];
out[i] <-- sm_layer0.lowergate_out[i];
endfor;
sm_application.lowergate_in <-- sm_layer0.uppergate_out;
sm_application.lowergate_out --> sm_layer0.uppergate_in;
display: “b=290,485,rect;o=white”;
endmodule
// the central manager
simple manager
parameters:
P_FMAP: numeric,
N_FMAP: numeric;
gates:
in: in;
out: out;
endsimple
//-------------------------------------------------
// the parent module
//-------------------------------------------------
module test
parameters:
MAXCONN: numeric,
NNODES: numeric,
SSTRENGTH: numeric;
submodules:
snode: sensornode[NNODES];
parameters:
CNNCTVTY = MAXCONN,
KIND = 2,
COLOR = 2,
PX = 0,
PY = 0;
gatesizes:
in[MAXCONN],
out[MAXCONN];
man: manager;
parameters:
P_FMAP = 0,
N_FMAP = 0;
connections nocheck:
display: “p=0,0;b=860,560,rect;o=white”;
endmodule
//-------------------------------------------------
// the network
//-------------------------------------------------
network thetest : test
endnetwork
如下图就是一个泛洪算法，图中有10个节点，拓扑是自己生成的，正在执行的是第2轮的消息发送。当整个网络中的节点都接收到由源节点发送的消息的时候，图中的所有节点都变成红色。如下图8。
图8 拓扑结构
5.5.2 gossiping协议
Gossiping协议是对Flooding协议的改进，节点将产生或收到的数据随机转发，避免了内爆，但增加了时延．这两个协议都是不需要维护路由信息，也不需要任何算法，简单但扩展性很差。该算法实现的基本模型跟flooding算法相似，其NED文件相同的。下面仿照Gossiping协议做了一个仿真试验，使随机产生的一个包按照自己随机选择的路径进行传输。
NED文件与Flooding相同，只是在其中增加了源地址和目的地址两个参数。仿真结果如图9。图中有40个节点，节点之间的连接是通过一个子模块的定义使其随机连接的。
图9 仿真图
图10 仿真中节点发送信息的过程图
图10就是仿真运行过程中的节点发送信息的过程图。
图中的绿色节点为目的节点，是仿真开始前自己设定的。仿真过程中，系统随机产生一个从某个节点到此目的节点的链路，消息通过这条链路传送到目的节点，完成一个消息的发送。
5.6 本章总结
近年来，路由协议成为无线传感器网络最重要的研究领域之一，有很多研究机构跟学院都已经有了相当的工作和贡献。但是针对这些协议还有很对的问题还需要进一步的研究，比如：如何为应用对QoS的确保和对带宽有效利用，尤其是针对于采集图象和传播视频数据的应用进行设计；如何高效进行集群分组，协调集群内sensor节点工作负载，并确保覆盖范围；等等问题都需要我们解决。
参考文献
[1] Akyildiz IF, Su W, Sankarasubramaniam Y, Cayirci E. A survey on sensor networks. IEEE Communications Magazine, 2002,40(8)
[2] Akyildiz IF, Su W, Sankarasubramaniam Y, Cayirci E. Wireless sensor networks: A survey. Computer Networks, 2002,38
[3] Cui L, Ju HL, Miao Y, Li TP, Liu W, Zhao Z. Overview of wireless sensor networks. Journal of Computer Research and Development, 2005,42
[4] Niculescu D, Americ NL. Communication paradigms for sensor networks. IEEE Communications Magazine 2005,43(3):
[5] Haas ZJ, Halpern JY, Li L. Gossip-Based ad hoc routing. In: Proc. of the IEEE INFOCOM. New York: IEEE Communications Society, 2002.
[6] Kulik J, Heinzelman WR, Balakrishnan H. Negotiation based protocols for disseminating information in wireless sensor networks. Wireless Networks, 2002,8(2-3)
[7] Intanagonwiwat C, Govindan R, Estrin D, Heidemann J. Directed diffusion for wireless sensor networking. IEEE/ACM Trans. on Networking, 2003,11(1)
[8] Braginsky D, Estrin D. Rumor routing algorithm for sensor networks. In: Proc. of the 1st workshop on sensor networks and applications. Atlanta: ACM Press, 2002.
[9] Heinzelman W, Chandrakasan A, Balakrishnan H. Energy-efficient communication protocol for wireless microsensor networks. In: Proc. of the 33rd Annual Hawaii Int’l Conf. on System Sciences. Maui: IEEE Computer Society, 2000.
[10] Lindsey S, Raghavendra CS. PEGASIS: Power-efficient gathering in sensor information systems. In: Proc. of the IEEE Aerospace Conf. Montana: IEEE Aerospace and Electronic Systems Society, 2002.
[11] Manjeshwar A, Agrawal DP. TEEN: A protocol for enhanced efficiency in wireless sensor networks. In: Int’l Proc. of the 15th Parallel and Distributed Processing Symp. San Francisco: IEEE Computer Society, 2001.
[12] Ye F, Luo H, Cheng J, Lu S, Zhang L. A two-tier data dissemination model for large-scale wireless sensor networks. In: Proc. of the 8th Annual Int’l Conf. on Mobile Computing and Networking. Atlanta: ACM Press, 2002.
[13] Sohrabi K, Gao J, Ailawadhi V, Pottie GJ. Protocols for self-organization of a wireless sensor network. IEEE Personal Communications, 2000,7(5):
[14] Chang JH, Tassiulas L. Maximum lifetime routing in wireless sensor networks. IEEE/ACM Trans. on Networking, 2004,12(4)
[15] Karlof C, Wagner D. Secure routing in sensor networks: attacks and countermeasures. Ad Hoc Networks, 2003,1(1)
[16] Ye F, Chen A, Lu S, Zhang L. A scalable solution to minimum cost forwarding in large sensor networks. In: Proc. of the 10th Int’l Conf. on Computer Communications and Networks. Arizona: IEEE Communications Society, 2001.
[17] Schurgers C, Srivastava MB. Energy efficient routing in wireless sensor networks. In: Proc. of the MILCOM on Communications for Network-Centric Operations: Creating the Information Force. Virginia: IEEE Communications Society, 2001.
[18] Chu M, Haussecker H, Zhao F. Scalable information-driven sensor querying and routing for ad hoc heterogeneous sensor networks. The Int’l Journal of High Performance Computing Applications, 2002,16
[19]陈治平，王雷.无线传感器网络中路由算法研究进展.福建工程学院学报，2005：600～607
[20]J Agre J，Clare L．An integrated mehitecture for cooperative sensing networks[J]．Computer，2000，33(5)：106—108．
[21]崔莉，鞠海玲，苗勇，等．无线传感器网络研究进展[J]．计算机研究与发展，2005，42(1)：163～174．
[22]Sehrabi K，Gao J，Ailawadhi V，et a1．Protocols for self-organization of a wireless sensor network[J]．IEEE Personal Communications，2000，7(5)：16—27．
[23]Akyildiz I F，Su W，Y，et a1．A Survey on Sensor Networks[J]．IEEE Communications Magazine，2002．lO2～ll4．
[24]Min R，Bhardwaj M，Cho s H，et a1．An Architecture for a Power-Aware Distributed Micro sensor Node[A]．IEEE Workshop on Signal Processing Systems[C]．New York：IEEE，345E47THST，2000．581～590．
[25]Shen C，Srizathapornphat C，Jaikaeo C．Sensor Information Networking Architecture and Applications[J]．IEEE Personal Communication，200l，8：52～59．
[26]Megnerdichien S，Koushanfar F，Qu G，et a1．Exposure In Wireless Ad．Hoc Sensor Networks[A]．ACM／IEEE International Conference on Mobile Computing and Networking[C]．New York：ACM Press，2001．139～150．
[27]Li Q，Aslam J，Rus D．Hierarchical Power-aware Routing in Sensor Networks[EB／OL]．http：／／www．CS．wm．edu／llqun／paper／dimacs．pdf．2001．5．
[28]http://blog.sina/u/490620c3010005f9
[29]宋晓勤，胡爱群.无线传感器网络中数据链路层和网络层设计.工业技术.2005
[30]http://blog.chinaunix/u/13991/showart.php?id=229797
[31Jamal N．Ahmed E.Kamal．Routing Techniques in Wireless Sensor Networks：A Survey．San Francisco：IEEE Computer Society．2002．1696—1705．
[32]S. Hedemiemi，A．Liestman．A survey of gossiping and broadcasting
in communication networks．Networks，1988，18(4)：319～349
[33]C. Intanagonwiwat，R．Govindan，D．Estrin．Directed diffusion：A scalable and robust communication paradigm for sensor networks in the Proceeding s of the 6th Annual ACM／IEEE International Conference on Mobile Computing and Networking ( MobiCom’00)，Boston。MA。August 2O00
[34]Heinzelman W ChandrakasanA，BalakrishnanH．An application—specific protocol architecture for wireless micro sensor networks[J]．IEEE Transactions on Wireless Communications，2002，(1O)：660～670．
[35]胡贵龙，许力，郑宝玉.仿真软件在MANET环境下的分析和比较.江苏通信技术.2003.
第六章 应用层仿真
6.1 无线传感器网络节点定位
6.1.1 节点定位的基本概念
节点定位是无线传感器网络配置和运行的一个基本和关键问题。所谓节点定位是指对于一组未知位置坐标的网络节点，通过估计至邻居节点的距离或邻居数目，利用节点间交换的信息，确定每个节点位置的机制。通常配置网络时不能对所有节点实施精确控制和人工设置。
6.1.1.1 节点定位的定义
对于某区域内的N个节点，若存在某种机制使各节点通过通信和感知可找到自己的邻居节点，并估计出到它们的距离，或识别出邻居的数目。每一对邻居关系对应网络图G的边e=(i，j)，设rij为节点i、j间的测量距离，dij为真实距离。定位的目的在于给定所有邻居对之间的距离测量值rij的基础上，计算出每个节点的坐标Pi，使其与测距结果相一致，即对于任意e∈G，使得｜｜Pj-Pi｜｜=dij。
如果两个节点之间能够相互无线通信，则它们互称为邻居节点。测距是指两个相互通信的节点测量估计彼此之间的距离。锚节点是指通过其它方式预先获得位置坐标的节点，也称作信标节点。相应的网络中的其余节点称为非锚节点。下文中所描述的节点一般指非锚节点。节点连接度是指节点可探测发现的邻居节点个数。网络连接度是指所有节点的邻居数目的平均值，它反映了节点配置的密集程度。在节点定位中覆盖率的含义是指能够确定坐标位置的非锚节点数目在总节点数目中所占的比例。
对于某些网络图，由于存在旋转、平移和偏转因素，符合测距结果的坐标位置并不保证唯一性。如图1所示，假设各边长即节点之间距离保持不变，如果要确定节点位置，则图1(a)是全局固定的，图1(b)是部分固定，其中有一个三角形可沿着边翻转，而图1©则是不固定的。由于全局固定的网络图只有一种位置方式，即通过自组织方式，在给定边长的条件下，得到节点唯一的位置布局。对于全局固定的网络图，要找出所有节点的精确位置分配则属于NP-hard问题。目前大多数节点定位算法允许定位误差在一定范围之内，求解过程和结果是基本合理的。但对于图1(b)、图1©两种情形，目前尚未有成熟的解决方案。
(a) (b) (c)
图1 测距计算得到的网络形状
6.1.1.2 节点定位的重要性
无线传感器网络的应用大多需要掌握节点的位置信息，节点定位的重要性在于：
(1)须知道节点感知数据的发生位置才有应用价值。
(2)无线传感器网络的很多通信协议是在已知节点位置的基础上运行的。另外基于节点的已知位置可优化网络运行期间的值守调度机制，使网络中冗余节点不定期地轮休以延长寿命。
6.1.2 节点定位的研究
6.1.2.1 测距方法
节点定位算法通常需预先拥有节点与邻居节点之间的距离或角度信息，因此测距是算法运行的前提。常用测距方法及优缺点分析如下：
(1)接收信号强度指示法(RSSI)。RSSI方法是接收机通过测量射频RF信号的能量来确定与发送机的距离。由于实现简单已被广泛采用，不足之处是遮盖或折射会引起接收端产生严重的测量误差，因此精度较低，有时RSSI的测距误差可达到50％。
(2)到达时间/到达时间差法(TOA/TDOA)。TOA/TDOA方法通过测量传输时间来估算两节点之间的距离，精度较好。缺点是无线信号的传输速度快，时间测量上的很小误差可导致很大的距离误差值，另外要求节点的CPU计算能力较强。Savvides[21]等的定位系统就采用了TOA/TDOA。这两种基于时间的测距方法适用于各种信号。
(3)到达角法(AOA)。AOA方法通过配备特殊天线来估测其它节点发射的无线信号的到达角度。Niculescu等采用AOA方法定位节点的位置。它对硬件要求较高，每个节点要安装昂贵的天线阵列和超声波接收器。
无线传感器网络中同一节点的感知距离与无线通信距离的范围可能有所不同，也可能相等，下文中假设两者近似相等。另外根据具体应用场景，同一网络内的各节点感知范围会稍有不同，而且同一节点随着电能的消耗，感知距离也会随之减少。这些物理因素的变化以及测距的不精确性，都会影响节点定位算法的定位精度。
以上测距方法考虑的是如何得到相邻节点之间的观测物理量，有些算法还需要通过间接计算获得锚节点与其它不相连节点之间的距离。所谓相连是指无线通信可达，即互为邻居节点。通常此类算法从锚节点开始有节制地发起泛洪，节点间共享距离信息，以较小的计算代价确定各节点与锚节点之间的距离。
6.1.2.2 节点定位原理
目前各种节点定位算法基于不同的节点定位原理，通常是利用节点之间的距离或角度，少数则采用节点的连接度信息或者干脆不采用测距方法。根据节点间的边长或角度定位的方法可分为三类：
(1)三角测量法。根据三角形的几何关系进行位置估算。前提是已知锚节点数，可进行“点在三角形中”的测试，即任意选取三个锚节点组成三角形，以测试节点是否落在该三角形内。根据测试结果的交集，大致确定节点位置。因此测试次数越多，位置估算的精度越高。三角测量法也可结合角度测量，即通过方向性天线，利用AOA测量的角度值来定位。确定二维坐标分别需要一个距离和角度值；确定三维位置则需两个角度、一个距离和方位角，方位角是在水平方向上从正北开始顺时针旋转的角度。
(2)单边测量法。基于距离测量的结果。确定二维坐标至少具有三个节点到节点的距离值；确定三维坐标，则需四个此类测距值。根据最小均方估计可求得解，当矩阵求逆不能计算时，单边测量法则不适用，否则可成功得到位置估计 。
(3)多边测量法。单边测量法的浮点运算量大，计算代价高。多边测量法则以新确定的节点位置作为锚节点，再计算其它位置。它是三角测量法和单边测量法的扩展。Savvides等提出一种简单的N跳多边测量min-max算法，后人多以此为基础衍生出自己的定位方案，其主要思想是各锚节点根据位置以及到待求节点的距离值，创建一边界框，所有边界框的交集形成一个矩形，取此矩形的中心点作为节点坐标。
6.1.2.3 节点定位算法分类
近年来节点定位算法出现较多，在特定条件下，某些算法在某些性能指标上可能优于其它算法，而在其它方面可能处于劣势。在一定意义下，可公认为最优秀的节点定位算法目前尚未产生。即使很优秀的算法也还有待于提高整体性能。在统计和系统分析已有节点定位算法的基础上，通过研究和归纳后认为，可根据四种分类标准对它们进行区分。算法分类和部分重要算法的细节讨论如下：
6.1.2.3.1 锚节点分类
根据有无锚节点可分为无锚节点算法和有锚节点算法。
(1)无锚节点算法。无锚节点算法无预先位置信息，仅根据局部距离值来定位。此类算法有ABC算法和AFL算法。ABC算法以节点间连接建立的顺序，一次计算一个未知节点坐标，在理想情况下可得到所有节点的坐标，特别是如果测距精度不够高，ABC算法很有利于减少定位误差。AFL算法在著名的Cricket定位系统[5] [6]中得到重要应用。该算法分两步，第一步是运用启发式原理得到一个无折叠布局，使之结构大致接近实际的布局图。如果网络图为中心辐射结构，则逼近效果更有效。第二步采用基于质点-弹簧模型的优化算法来修正和平衡局部最优解，以保证新位置的能量比原来位置的能量小。AFL的最大特点是保证不产生局部最优解。
(2)有锚节点算法。有锚节点算法依赖于某些已知坐标位置的节点。这种定位算法需要预先定位锚节点，否则无法正常运行，另外为了减小定位误差，锚节点数目还须足够多。目前除上述两种无锚节点算法外，其余均属此类算法。有锚节点算法的重要特征是定位精度取决于锚节点密度。
Terrain算法是以无锚节点的ABC算法为基础，先从每个锚节点向周围扩散，如果某节点接收到至少三个独立锚节点的距离信息，则由三角测量法求出自身坐标。锚节点数越多，定位越精确。通常当测距误差为5％时，产生的平均位置误差为25％；而ABC算法在同样的情况下会产生60％的平均位置误差。Savarese提出稳健定位算法[19]，其中第一步提出的Hop-Terrain算法是Terrain算法的变形，该算法对测距误差有较好的容错性。GPS-Free算法，建立节点自身的本地坐标系统和网络坐标系统，当每个节点的本地坐标系统建立完毕后，网络调整整个坐标，成为全局网络坐标系统。主要过程包括对本地坐标系统进行旋转和转换。
采用锚节点的优势在于：
(1)使用锚节点允许可扩展的、非集中式的定位计算；
(2)集中式算法使用锚节点可在收敛性和估计精度上得到很大的提高。
6.1.2.3.2 计算方式分类
根据计算方式可分为集中式算法、增量式算法和分布式算法。
集中式定位是指节点将数据传输到一个中央控制器件，在该处计算节点坐标。Doherty等人根据锚节点的连接度信息，采用凸优化法[10] [11]统一计算节点位置。为了使算法可靠运行，需要将锚节点放置在网络外框边界，最好位于边界角上。如果锚节点放置在网络内部，则许多节点的定位误差很大。MDS-MAP方法[25]也是只使用连接度信息，采用集中式的多维标度计算原理。MDS-MAP的特点在于只使用少量的3-4个锚节点，但需要计算全网内所有节点之间的距离或连接度，而通常的多边测量法只依赖邻居节点之间的距离信息。由于集中式算法具有很高的通信代价，其可行性很差。通过配置窥探器进行集中式定位的两种方案，需要的硬件条件包括中央服务器和一些窥探器。窥探器对所有给定信道上的业务量进行监听。一种方案是直方图计算，即在固定基站估计信号强度，使用贝叶斯模型确定窥探器监测的条件概率，进行监测量合成。当从一个位置得到一些监测结果后，算法进行位置计算，选择具有最高概率的坐标作为结果。另一方案是差分法计算，它与直方图方案类似，直方图法测量信号强度值，但差分法采用的是每对窥探器之间的信号强度差。
增量式算法从三个或四个已知坐标的中心节点开始，寻找合适的新节点，通过测量距离来迭代求解，再将这些节点加入中心节点组，逐步得到所有节点的坐标。缺点是距离误差被逐步放大，有些增量算法设置了一个优化过程来减缓这种误差的积累。另外在增量阶段还可能产生局部最优解。ABC算法、协作式多边测量法和AOA算法属此类算法，对距离误差很敏感。
人们倾向于采用分布式算法。分布式算法也称并发式算法，即定位过程只需与邻居节点进行通信，计算在本节点处完成。除上述集中式和增量式算法以外的其它算法均为分布式定位算法。Yi Shang在其原先的集中式算法MDS-MAP基础上进行了改进，提出改进型多维标度定位算法[27]，在不同的通信跳数内先计算相对较小的局部图块，最后拼接成一幅全局位置图。在两跳路由的无线范围内计算各局部图，则节点定位系统的整体性能较好。
6.1.2.3.3 测距分类
根据是否采用测距分为基于无测距的算法和测距的算法。
无测距定位时节点不装配测距或测角设备，硬件成本低，但相对基于测距的算法则定位精度稍差。无测距的定位算法仅依赖所接受的通信消息，但需要锚节点配合，目前有质心算法[8]、APIT算法[23]、DV-HOP算法[15]和不定形算法。在质心算法中，节点根据接受到的所有锚节点位置的质心来定位，如果锚节点配置精确，则节点定位精度较好。APIT算法根据锚节点的位置，将监测地区分成若干三角形区域，采用栅格法确定节点可能位于的区域，算法要求锚节点的密度足够大。DV-HOP算法解决了低锚节点密度引发的问题，它根据距离矢量路由协议的原理在全网范围内广播跳数和位置。每个节点设置一个至各锚节点最小跳数的计数器，根据接收的消息更新计数器。锚节点广播其坐标位置，当节点接收到新的广播消息时，如果跳数小于存贮的数值，则更新并转播该跳数。不定形算法采用类似原理，锚节点坐标在全网内泛洪，节点维护到锚节点的跳数，根据接收的锚节点位置和跳数计算自身位置。
基于测距的算法使用点到点之间的距离或角度，但需要特定的硬件设备，除上述四种算法外其它算法均属此类。Niculescu等提出一种有锚节点、分布式的、基于AOA测角的定位方案[16]，节点反复接收来自锚节点的位置和方位数据。由于使用AOA法在电子工程领域设计成本高，且获得精确的角度值也很困难，目前不倾向采用。在部署大规模的无线传感器网络应用中，测量节点之间的距离是一种经济可行的定位手段。
6.1.2.3.4 节点移动性分类
根据节点的移动性分为静止节点定位算法和移动节点定位算法。
目前多数定位方案属静止节点定位算法，即节点处于静止状态。虽然在移动机器人领域有关于移动定位的成熟方案，但机器人器件的内存大，且CPU可进行计算量很大的运算，这些方案不能直接移植到无线传感器网络中。移动节点的定位算法尚待进一步的研究。
6.1.2.4 节点定位性能评价[37]
目前针对节点定位性能评价有多种方式，主要包括以下几种，其它大多是其变化形式。
(1)定位精度。节点定位技术首要的评价指标就是定位精度，一般用误差值与节点无线射程的比例表示。
(2)规模。不同的节点定位系统或算法也许可在园区内、建筑物内、一层建筑物或仅仅是一个房间内实现定位。另外，给定一定数量的基础设施或在一段时间内，一种技术可以定位多少目标也是一个重要的评价指标。
(3)锚节点密度。锚节点定位通常依赖人工部署或全球定位系统实现。人工部署锚节点的方式不仅受网络部署环境的限制，还严重制约了网络和应用的可扩展性。而使用全球定位系统定位，锚节点的费用会比普通节点高两个数量级，这意味着即使仅有10%的节点是锚节点，整个网络的价格也将增加10倍。因此，锚节点密度也是评价定位系统和算法性能的重要指标之一。
(4)节点密度。在无线传感器网络中，节点密度增大不仅意味着网络部署费用的增加，而且会因为节点间的通信冲突问题带来有限带宽的阻塞。节点密度通常以网络的平均连通度来表示。许多定位算法的精度都受节点密度的影响。
(5)容错性和自适应性。节点定位算法都需要比较理想的无线通信环境和可靠的网络节点设备。但在真实应用场合中常会有诸如以下的问题：外界环境中存在严重的多径传播、衰减、非视距、通信盲点等问题；网络节点由于周围环境或自身原因而出现失效的问题；外界影响和节点硬件精度限制造成节点间点到点的距离或角度测量误差增大的问题。由于环境、能耗和其他原因，物理地维护或替换传感器节点或使用其他高精度的测量手段常常是十分困难或不可行的。因此，节点定位算法的软、硬件必须具有很强的容错性和自适应性，能够通过自动调整或重构纠正错误、适应环境、减小各种误差的影响，以提高定位精度。
(6)功耗。功耗是对无线传感器网络的设计和实现影响最大的因素之一。由于传感器节点电池能量有限，因此在保证定位精度的前提下，与功耗密切相关的定位所需的计算量、通信开销、存储开销和时间复杂度是一组关键性指标。
(7)代价。节点定位算法的代价可从几个不同方面来评价。时间代价包括一个系统的安装时间、配置时间、定位所需时间。空间代价包括一个定位算法所需的基础设施和网络节点的数量、硬件尺寸等。资金代价则包括实现一种定位算法的基础设施、节点设备的总费用。
上述七个性能指标不仅是评价无线传感器网络节点定位算法的标准，也是其设计和实现的优化目标。同时，这些性能指标是相互关联的，必须根据应用的具体需求做出权衡，以选择和设计合适的节点定位算法。
6.1.3基于OMNET++的DV—Hop定位算法仿真
6.1.3.1 DV—Hop定位算法的基本思想
DV—Hop定位算法非常类似于传统网络中的距离向量路由机制，其算法的定位过程可以分为以下三个阶段。
第一阶段，首先使用典型的距离矢量交换协议，使网络中所有节点获得距锚节点的跳数。为了获得到节点间的跳数，锚节点向所有邻居节点广播一个包含其位置信息和跳数（初始值为0）的数据包。接收到该数据包的节点将跳数加1，继续向它的邻居节点转发（除了来源方向），这个过程一直持续下去，直到网络中每个节点都获得每个锚节点的位置信息和相应的跳数值。如果某个节点接收到来自相同锚节点的多个数据包，这表明它到该锚节点有多条路径，此时，节点将保留含有最小跳数值的数据包，而忽略其它数据包，这样就可保证每一个节点得到和锚节点的最小跳数。如图2所示，锚节点A广播的数据包以近似于同心圆的方式在网络中逐次传播，图中的数字代表距离锚节点A的跳数。
图2 锚节点A广播数据包的示意图
第二阶段，在获得其他锚节点位置和相隔跳距之后，锚节点i根据下式计算它和周围节点的网络平均每跳距离，
其中，（Xi，Yi）、（Xj，Yj）是锚节点i、j的坐标，h(i，j)是锚节点i与锚节点j之间的跳数。hdi用来计算锚节点i和周围待定位节点的距离。锚节点进行第二次广播，锚节点向所有邻居节点广播一个包含hd的数据包，同样，当一个节点接收到了第一个hd 后，便丢弃所有后来者，这样确保所有节点可从最近的锚节点接收到hd。未知节点接收到hd后，便用hd与它接收到的最小跳数hops的乘积来近似代替它到锚节点i的距离,
di=hops×hdi
第三阶段，当未知节点获得3个或更多锚节点的距离后，利用三边测量法或极大似然估计法计算自己的位置。
6.1.3.2 DV—Hop定位算法仿真
下面采用OMNET++作为仿真平台对DV—Hop定位算法进行性能评估，OMNET++是布达佩斯技术大学电信学院开发的面向对象的离散事件仿真工具，它可用于通信协议、计算机网络多处理器和分布式系统、管理系统等的建模和仿真。仿真分析的网络模型的主要参数如下：
(1)所有节点（除锚节点）具有相同的功能和性能，没有影响通信的干扰存在；
(2)节点之间的通信正常或者失败的概率是固定的，通信半径为100；
(3)测试区域大小为一个 800×500 的平面区域，30个节点（其中锚节点3个，未知位置节点27个）随机分布在该区域范围内。
图3 DV—Hop定位算法的网络拓扑
DV—Hop定位算法的仿真过程如下：第一步，创建定位算法工作目录，并进入该目录；第二步，建立定位算法网络拓扑文件.ned文件，如图3所示；第三步，创建定位算法模块实现文件.h文件和文件；第四步，如图4所示，在命令行内分别使用nedtool *.ned命令，opp_nmakemake -f -e cc命令，nmake -f Makefile.vc命令进行编译，生成仿真执行文件DV—Hop.exe文件；第五步，建立仿真配置文件omnetpp.ini文件；第六步，运行DV—Hop.exe，得到定位算法的仿真结果，仿真结果显示锚节点比例为10%的各向同性网络中平均定位精度大约为33%。DV—Hop定位算法的缺点是仅在各向同性的密集网络中，才能合理地估算平均每跳距离。
图4 DV—Hop定位算法的编译过程
图5 DV—Hop定位算法的仿真结果
使用OMNET++仿真DV—Hop定位算法核心部分的参考源代码如下：
#include “application.h”
Define_Module( application );
void application::initialize()//初始化函数
{
last_seen_id = -1; //上次接收的节点的id为-1
msgcount = 0; //每个节点发出的消息数初始化为0
TTL=0;
}
void application::finish()
{
int i;
double tmp;
ev<<“Node “<<ID<<” position, px=”<<PX<<"; py="<<PY<<"\n";
for(i=0;i<NUM_ANC;i++)
{
ev<<“least hops to anchor[”<<i<<"]is “<<hopto[i]<<”\n";
ev<<“len to anchor[”<<i<<"] is “<<lento[i]<<”\n";
}
if(ID>=NUM_ANC)
{
commatrix();
tmp=sqrt((PX-rp.rx)(PX-rp.rx)+(PY-rp.ry)(PY-rp.ry));
ev<<“we get the position px=”<<rp.rx<<", py="<<rp.ry<<"\n";
ev<<“cha=”<<tmp<<"\n";
}
else
ev<<“we get the position px=”<<PX<<", py="<<PY<<"\n";
ev<<"\n\n";
}
void application::handleMessage(cMessage *msg)
{
switch(msg->kind())
{
case M_LOWHIGH:
{
if (strcmp(msg->name(),“FLOOD”)==0)
{
processFlood(msg);
return;
}
if(strcmp(msg->name(),“GGHOPS”)==0)
{
processHops(msg);
return;
}
ev << “unknown message received from another node.\n”;
endSimulation();
}
case M_START:
{
cMessage *msgnew = new cMessage(“FLOOD”);
msgnew->setKind(M_HIGHLOW);
msgnew->addPar(“flood_id”) = ++last_seen_id;
msgnew->addPar(“source”)=ID; //set source for the message
msgnew->addPar(“hops”)=0;
msgnew->addPar(“spx”)=PX;
msgnew->addPar(“spy”)=PY;
send(msgnew,“lowergate_out”);
UPDATECOLOR(msgcount+2);
msgcount++;
break;
}
case M_S2:
{
if(strcmp(msg->name(),“GGHOPS”)==0)
{
double hopsize=comhopsize();
TTL=INTTL;
cMessage *hopsmsg=new cMessage(“GGHOPS”);
hopsmsg->setKind(M_HIGHLOW);
hopsmsg->addPar(“source”)=ID;
hopsmsg->addPar(“hopsize”)=hopsize;
hopsmsg->addPar(“ttl”)=INTTL;
sendDelayed(hopsmsg,RETRANSMITDELAY,“lowergate_out”);
seens[ID]=true;
UPDATECOLOR(ID+2);
break;
}
}
default:
ev << “unknown message received\n”;
endSimulation();
}
}
void application::processFlood(cMessage *msg)
{
int flood_id = (int)msg->par(“flood_id”);
if (flood_id <= last_seen_id)
{
delete msg;
return;
}
int source =msg->par(“source”);
int hop=msg->par(“hops”);
if(seen[source]==false)
{
seen[source]=true;
ancpos[source].x=msg->par(“spx”);
ancpos[source].y=msg->par(“spy”);
hopto[source]=hop+1;
msg->par(“hops”)=hopto[source];
msg->setKind(M_HIGHLOW);
sendDelayed(msg,RETRANSMITDELAY,“lowergate_out”);
UPDATECOLOR(flood_id+2);
}
else if(seen[source]==true)
{
if(hopto[source]>hop+1)
{
hopto[source] = hop+1;
msg->par(“hops”)=hopto[source];
msg->setKind(M_HIGHLOW);
sendDelayed(msg,RETRANSMITDELAY,“lowergate_out”);
}
else
delete msg;
return;
}
msgcount++;
last_seen_id = flood_id;
}
double application::comhopsize()//此函数计算（PX，PY）到所有锚节点距离总和和跳数总和，并计算平均每跳距离
{
double len=0.0,hs=0.0;
int hop=0,i;
for(i=0;i<NUM_ANC;i++)
{
len+=sqrt((PX-ancpos[i].x)(PX-ancpos[i].x)+(PY-ancpos[i].y)(PY-ancpos[i].y));
hop+=hopto[i];
}
hs=len/hop;
return hs;
}
void application::processHops(cMessage msg)
{
int soc,ttl;
ttl=msg->par(“ttl”);
ttl–;
hopsize=msg->par(“hopsize”);
soc=msg->par(“source”);
if(seens[soc]==true||ttl<0)
{
delete msg;
return ;
}
if(seens[soc]==false)
{
seens[soc]=true;
if(TTL<ttl)
{
TTL=ttl;
msg->setKind(M_HIGHLOW);
msg->par(“ttl”)=ttl;
sendDelayed(msg,GENERATIONDELAY,“lowergate_out”);
UPDATECOLOR(soc+2);
}
else
{
msg->setKind(M_HIGHLOW);
msg->par(“ttl”)=ttl;
sendDelayed(msg,GENERATIONDELAY,“lowergate_out”);
}
lento[soc]=hopto[soc]hopsize;
}
}
void application::commatrix()
{
int sel[NUM_ANC],i,j,t;
double dt,b11,b21,a11,a12,a21,a22,ap11,ap12,ap21,ap22;
ap11=ap12=ap21=ap22=0.0;
a11=a12=a21=a22=0.0;
b11=b21=0.0;
dt=0.0;
for(i=0;i<NUM_ANC;i++)
sel[i]=i;
for(i=0;i<NUM_ANC-1;i++)
for(j=i+1;j<NUM_ANC;j++)
{
if(hopto[j]<hopto[i])
{
t=hopto[j];
hopto[j]=hopto[i];
hopto[i]=t;
t=sel[j];
sel[j]=sel[i];
sel[i]=t;
}
}
ap11=(double)(2(ancpos[sel[0]].x-ancpos[sel[2]].x));
ap12=(double)(2(ancpos[sel[0]].y-ancpos[sel[2]].y));
ap21=(double)(2*(ancpos[sel[1]].x-ancpos[sel[2]].x));
ap22=(double)(2*(ancpos[sel[1]].y-ancpos[sel[2]].y)); b11=ancpos[sel[0]].xancpos[sel[0]].x-ancpos[sel[2]].xancpos[sel[2]].x+ancpos[sel[0]].yancpos[sel[0]].y-ancpos[sel[2]].yancpos[sel[2]].y+lento[sel[2]]lento[sel[2]]-lento[sel[0]]lento[sel[0]]； b21=ancpos[sel[1]].xancpos[sel[1]].x-ancpos[sel[2]].xancpos[sel[2]].x+ancpos[sel[1]].yancpos[sel[1]].y-ancpos[sel[2]].yancpos[sel[2]].y+lento[sel[2]]lento[sel[2]]-lento[sel[1]]lento[sel[1]];
double test[2][4]={ap11,ap12,1.0,0.0,ap21,ap22,0.0,1.0};
dt=test[0][0];
for(i=0;i<4;i++)
test[0][i]=test[0][i]/dt;
dt=test[1][0];
for(i=0;i<4;i++)
test[1][i]=test[1][i]-dttest[0][i];
dt=test[0][1]/test[1][1];
for(i=0;i<4;i++)
test[0][i]=test[0][i]-test[1][i]dt;
dt=1.0/test[1][1];
for(i=0;i<4;i++)
test[1][i]=test[1][i]dt;
a11=test[0][2];
a12=test[0][3];
a21=test[1][2];
a22=test[1][3];
rp.rx=a11b11+a12b21;
rp.ry=a21b11+a22*b21;
}
6.4节点定位面临的技术挑战
对于无线传感器网络节点定位问题，还存在以下技术挑战：
(1)有效的测距方法；
(2)减少节点定位带来的通信开销；
(3)复杂的算法可以提高定位精度，但无线传感器网络节点有能量限制，需要研究在算法复杂度与能量消耗之间的合理折中。
6.2 网络管理
6.2.1概叙
随着现代网络技术的发展，信息技术的应用模式发生了很大的变化，对网络的应用提出了更高的要求。网络数量急剧增长，网络结构日益复杂，网络担负的工作越来越繁重。
ISO(International Organization for Standardization)将网络管理的功能需求划分五大类，分别以五个功能域表示，即
1．性能管理
2．故障管理
3．配置管理
4．计费管理
5．安全管理
通过这五大网络管理功能，IP 网管系统就能够实时调整网络状态、充分提高每个被管对象的利用率，使网络不发生故障或拥塞、网络中的各种资源得到更加高效的利用，在保证网络的可用时间和设备的利用率、网络性能、服务质量的同时，实现网络正常、高效地运行。
在 网 络 管 理 技 术 的 研 究 、 发 展 和 标 准 化 方 面 ， 国 际 标 准 化 组 织ISO和 Internet 体系结构委员会IAB(Internet Architecture Board)及其下属的工作组都作了卓有成效的工作。他们所制定的基于 OSI 参考模型的公共管理信息服务与协议 CMIS/CMIP(Common Management Information Services/Protocol)和基于 TCP/IP 的简单网络管理协议SNMP(Simple Network Management Protocol)已经成为目前网络管理系统中运用较为广泛的两种协议。
但由于无线传感器网络自身的特点，在WSN网络管理中不能完全照搬Internet中的网络管理体系和协议，那么在WSN中网络管理体系及协议又是怎么样的呢？本章将一一回答这些问题。
在8.1节中，我们将给出当前WSN网络管理的定义、分类及设计标准。接着将介绍当前WSN中已有的网络管理系统，包括能量管理系统、拓扑管理系统以及其它方便管理者管理的可调试、可配置、可编程等各类系统；最后我们将在omnet上模拟当前典型的WSN网络管理算法。
6.2.1.1 wsn网络管理的定义及范畴
网络管理是一通用术语，其中包括许多事情。它可能是手工网络管理者为了解决网络相关问题而交互使用的网络工具的集合，它也有可能是由分布式数据库、具备出错自动恢复的分布式数据采集程序、资源规划、未来网络规划所构成的“交响曲”[36]。网络管理的一个准确且有用的定义可以在Cisco网站上找到，上面写到：“网络管理者是一种服务，提供大量工具、应用程序和设备来帮助手工网络管理者监控和维护网络”。我们可以为手工（人类）网络管理者增加一个目标――帮助网络使用者尽可能有效的执行它们的网络任务（如高质量 使用更小的资源）。而且“监控和维护网络”的任务有利于实现这一目标。所有的这些活动都应该要以最少的能量和对用户最少的干涉来完成。在WSN中，提供这些活动的服务应该作为一个分布式应用程序来执行，而不仅是从单个节点返回信息到管理节点跟传统数据网络中网络管理相对比，WSN中没有传统网络中的性能和权限管理（performance and accounting management.）但具有一些新的特性：
安全管理。 在WSN中，由于拥有有限的处理能力、能量和传输带宽，安全问题是一个富有挑战性的课题。一段恶毒的代码很容易破坏整个WSN的功能。因此，这使得大部分的WSN应该是自组织的，这一点变得尤其重要。
容错管理。 容错恢复确实不在wsn的管理层中。但错误发生的如此频繁以致于用户的程序应在设置时就应考虑它。WSn原本不应该关心节点在执行中死亡、也不关心由于动态的变化节点的突然链路的突然消失。换句话说，如果我们（网络管理层）发现异常，我们可能认为这是应用程序的bug。但由于被设计成一个基本的服务，是分布式的，因此调试对wSN来说是非常重要的问题。
动态可编程、可配置。 对wsn来说，一个动态可编程平台可以被当成网络管理的一部分，因为它允许用户执行各种各样的分布式算法从而有效的利用了网络资源。最后，考虑可配置的管理，在wsn中，它的应用在传统意识中并不明确。在传感器网络中，并没有许多不同平台和系统和系统倾向如同构和平坦（flat）或在分层次结构中有轻微的异构。
6.2.1.2 wsn网络管理系统的分类
Wsn中的网络管理可能包括广泛的中间件服务（如 分布式调试、动态可编程平台），分布式应用（如 覆盖度的监控、能量监控）和规划工具（如 部署仓库）。WSN网络管理系统可能以结构、协议、或者算法等形式提出。 依据功能,它们可以分为如下几类[37]:
(1) 被动监控。 该类系统搜集网络状态信息。 它可能有一个post-man，用于数据分析。
(2)故障检测监控。 该类系统搜集网络状态信息以便确定是否有故障发生。
(3)响应性监控。 该类系统搜集和分析网络状态信息以便检测感兴趣的事件是否发生以及自适应、再配置网络。
(4)预测性监控。 为了维护网络性能该系统积极收集并分析网络状态信息以便预测网络事件的发生。
依据结构模型, 网络管理系统也可分为如下几类:
(1)集中式管理系统。 基站作为网管,搜集各节点信息、控制整个网络。
(2)分布式管理系统。 它采用多重网管模式. 每个网管控制一个子网, 每个网管为履行管理职能还可以直接与其他网管以协作方式通信。
(3)分层式网络管理。 它是介入集中式和分布式之间的一种混合管理模型. 它利用中间管理节点来分发管理任务和中间管理节点不直接与对方通信. 每个管理者负责管理其子网内的节点、传递其子网信息到更高一级管理者以及传播来自上级管理者的管理任务到其子网。
表1给出了当前网络管理系统的分类信息：
表1前网络管理系统的分类信息
网络管理系统 出版年 功能 结构模型
Two-Phase Monitoring System 2006 故障检测监控 分布式
MOTE-VIEW 2005 被动监控 集中式
SNMS 2005 被动监控 集中式
AppSleep 2005 被动监控 分层式
Agilla 2005 响应性监控 分布式
BOSS 2005 预测性监控 集中式
Agent-Based Power Management 2005 预测性监控 分布式
Agent-Based Policy Management 2005 预测性监控 分层式
Siphon 2005 预测性监控 分布式
Sympathy 2005 预测性监控 集中式
RRP[18] 2004 预测性监控 分层式
STREAM 2004 被动监控 分层式
MANNA 2003 N/A N/A
Sectoral Sweeper 2003 被动监控 分布式
Node-Level Management 2003 响应性监控 分布式
SenOS 2003 响应性监控 分层式
TinyDB 2002 被动监控 集中式
TopDisc 2001 被动监控 分层式
DSN Resource Management 2001 预测性监控 分层式
6.2.1.3 wsn网络管理系统的设计标准
无线传感器网络管理系统设计应提供的一套管理功能,集成配置、运行、管理和维修等所有功能和服务,同时兼顾传感器网络的独特性。下面给出了衡量传感器网络管理系统设计好坏的标准[37]:
(1) 轻量级操作： 系统应能运行在传感器节点上，在不消耗过多的能量且不影响传感器节点正常工作的前提下能节约节点能源和提高网络的寿命。
(2) 鲁棒性、容错性。 能量局限性使得传感器节点加入和离开网络频繁，因此传感器网络链路易变。系统要适应网络动态编号、能够在实现不了网络拓扑情况下自主的再配置网络；即针对拓扑变化具备自配置和自适应能力。
(3) 自适应性、应变性。 系统应能重绘并适应当前网络状态或改变网络的条件(例如网 拓扑,节点的能量能级，覆盖度)。
(4) 最小的数据存储。 用于数据管理的数据结构必须是可扩展的,且在WSN内存约束的前提下能包括所需的全部管理信息。
(5) 控制功能。系统应能控制整个网络,以便于维护网络的性能,如能开关传感器,控制wsn资源的使用(无线带宽和功率), 控制传感器灵敏度阈值,以及取样频率。
(6) 大规模性。 系统应能在任何规模的网络中有效运作。
6.2.2 wsn网络管理系统
当前提出的WSN网络系统其管理模式有[38]：
(1) 能量图。给出网络不同部分节点的能量层次。
(2 网络拓扑图。描述当前网络连通/可到达的图。
(3) usage pattern。描述了网络中活动节点的活动时间，每单位时间传送的数据量，追踪网络中热点。
(4)Non-deterministic。传感器网络具有高度的不确定性和不可靠性，在估计网络行为上，统计和概率模型比确定性模型更高效。
(5) 动态可编程、调试、配置模型。该模型以有效满足网络中不同用户的瞬时需求为目标。
6.2.2.1 能量管理系统
能量是无线传感器网络最重要的资源,节能已成为无线传感器网络研究的主要目标之一。能量管理是一种重要的节能手段,其基本思想是让网络中的冗余节点休眠。很多学者开展了能量管理的研究,提出了SPAN、GAF、ASCENT、PEAS、NSSS、CCP AppSleep等协议以及SenOs系统。目前的能量管理协议的主要问题是网络中节点能量消耗不均衡,导致一些覆盖保持和数据传输的关键节点能量消耗过快,缩短了网络的生命周期[39]。在当前的能量管理系统或协议中，比较典型的SenOS系统。
6.2.2.1.1 SenOs[5]
Sen OS是一个基于有限状态机模型的无线传感器操作系统，以小尺寸、低功耗、支持并发性、及时响应性和动态重构能力为设计目标；在WSN能量管理上有着显著的成效，因此我们把它列位能量管理系统。基于状态机的软件模型可以支持受控的并发性和及时响应性， 简化设计， 并提供了大量代码生成工具以自动产生运行代码。
图1 Sen OS的系统结构
如图1所示，Sen OS的系统结构包括三个构件：由接收输入事件的状态排序器和事件队列构成的内核、状态转换表以及回调函数库。内核检查事件队列并在输入事件有效时根据状态转换表转换状态、触发回调函数。回调函数库包含一组用户定义的函数，决定了传感器结点的功能。内核及回调函数库静态构建并存储在ROM中，而状态转换表可以进行动态的修改或替换。SenOS 通过多张状态转换表支持多个用户应用的共存，并通过切换状态转换表提供并发支持。也就是说，每个状态转换表定义了一个用户应用。在发生应用任务的抢占时，由内核负责保存当前任务的状态、恢复后续任务的状态、替换当前的状态转换表。
6.2.2.2 拓扑控制系统
WSN拓扑管理模块负责保持网络连通和数据有效传输。由于传感器节点被密集地部署于监控区域，为了节约能源，延长WSN的生存事件，部分节点将按照某种规则进入休眠状态。拓扑管理的目的就是在保持网络连通和数据有效传输的前提下，协调WSN中个节点的状态转换[6]。为完成上述目标，网络管理者首先需求得到网络拓扑信息图，了解网络中个节点的活动状态，这通常就是拓扑发现的过程。本章将介绍TopDisc[40]拓扑发现算法。
6.2.2.2.1 TopDisc 算法
TopDisc算法来源于Guha等人在图论中提出的思想，是基于最小支配集问题的经算法。
在TopDisc算法中，由网络中一个节点启动发送用于查询邻居节点的查询消息。查询消息携
带查询节点的状态信息。随着查询节点在网络中的传播，TopDisc依次为每个节点标志不同
颜色。最后按照颜色区分出簇头节点，并依据反向寻找查询的传播路径构建出通信链路。
TopDisc提出了三色和四色算法，三色算法将节点分别着上白色、黑色和灰色。白色节点
代表未被发现的节点或者是没有收到任何拓扑请求包的节点；黑色节点为簇头节点；灰色节
点为至少被一个黑色节点覆盖的节点。算法具体过程如下：
(1)初始节点将自己标志为黑色，并广播查询消息。
(2)白色节点收到来自黑色节点的包后变成灰色，灰色节点随机等待一段时间后再广播查询消息，等待时间的长度与它收到的黑色节点之间的距离成反比。
(3)当白色节点收到一个灰色节点的查询消息后将等待一段随机延迟时间后变成黑色节点；但如果在等待时间内收到其它黑色节点的任何包它都将变成灰色。随机延迟等待时间跟向它发出查询消息的灰色节点的距离成反比。
(4)当节点变为黑色或者灰色后，它将忽略其它节点的查询消息。
(5)通过方向查找查询消息的传播路径形成骨干网，黑色节点成为簇头，灰色节点成为簇内节点。
下图2描绘了执行TopDisc算法后的拓扑情况。
图2 执行TopDisc算法后的拓扑情况
6.2.2.3 可调试、可配置、可编程系统
需长期运行的传感器网络应支持多个临时用户来提供不同的应用需求，因此网络中将运行许多不同的分布式算法――先前不为人所知的算法。而且研究人员需要而且研究人员常常需要在运行中某些参数、再配置网络。这就是传感器网络管理的另一大模块――如何有效的向用户提供动态编程服务?
科研人员开发传感器网络的算法都不关心如何写程序。提出的算法大部分都是假定被硬编码到每个节点上。 在一些平台上,应用开发商可以利用节点层次的操作系统(例如tinyos)创造应用程序， 节点层次的操作系统具有模块化,多任务,和硬件抽象层方面的优势。 尽管如此,开发商仍必须建立一个单一的可执行映像并手动下载到每个节点上。 不过,人们普遍认为,传感器网络具有较长的部署周期和用户的多种临时需求。 显然这需要动态传感网络编程。传感器网络需要什么样的动态编程? 硬编码算法到每个节点,通过改变参数来调试程序是不足够灵活的适应各种各样的传感器网络应用。由于大多数节点是物理不可达的（unreachable）或花费很大代价才可达（reachable），因此下载可执行映像到每个节点是不可行的, 一种方案是可执行映像通过网络传输到每一个节点 ，然而这是非常低效的(因为高级通信费用和有限的节点能量)，而且这还将使得不能让多用户共享传感器网络。理想上的方案是能够动态作为一个整体—融合- 不是仅仅作为单个节点编程传感器网络动态。这意味着一个连接到网络上的用户在任何时候能够注入指令到网络中来完成某个(可能是分布式的)任务。 指令根据用户需求、网络状态和物理现象把任务分给个别节点，而不不干扰由用户最初的指令。此外,由于多用户并发的使用传感器网络, 传感器节点的资源/服务对多个用户/应用程序应是共享的。这种类型的编程－mability－被称为"系统级可编程性[41]。
6.2.2.2.1 sympathy 系统[42]
sympathy 系统通过收集网络性能参数来鉴定、定位网络失败的原因的可调试系统。系统花费最小的内存开销。系统开发人员发现网络失败大多归功于节点间的干扰。Sympathy提供一种机制—通过查找各种不相关事件的关系来确定网络失败的原因。
Sympathy能够通过检测具有一些能决定他们spatiotemporal context 的metrics的事件来找出网络失败的原因。传统的调试和错误检测机制都常常假设无线节点是资源无穷的且节点的失败都是由于自身的原因造成的；而sympathy充分考虑了多个节点之间的交互性，提供机制来分析事件发生的环境、维护网络状态。
6.2.2.2.2 Agilla系统[7]
这是在tinyos上开发的一个支持移动代理的中间件。作者使用Agilla来实现了火势追踪程序。在火势追踪程序中各个代理的功能如下：
据事故源最近节点发送报警代理（高优先级），通知基站，确定事发地点。
事故源附近节点产生追踪代理，并不断克隆自己，最终形成一个圈包围事故源；且追踪代理随着事故（如火势）的扩展而扩展，始终不断克隆自己以此来追踪事故（如火势），最终确定正在影响事故的范围。
待营救人员赶到后，营救人员发出搜索-营救代理。 发送搜索-营救代理的节点将提高发射功率，同时尽量往追踪代理多的地方去，搜索-营救代理也是不断的克隆自己，在部分搜索-营救代理中找到受困的矿井人员后，搜索-营救代理之间的协同合作将形成一条安全的路传送给营救人员，最终确定受困人员的位置并展开救援。
其模型和结构如下：
6.2.3典型网络管理算法的Omnet 模拟
6.2.3.1 基于Wsn的一个简单拓扑查找算法算法模拟
本节介绍omnet模拟一个简单的WSN拓扑查找算法。所谓简单的拓扑查找,是指理想环境下,节点具有固定的信号强度(这意味着仅限于双向链接的用法),且从通信的角度看算法不是很有效的(消息的数量可以被减少)。本文只描述算法的原理和模拟实现过程，而不涉及算法的应用以及意义，事实上该算法在现实中是没有什么应用价值的，从它的假设就可以看出来，但对于我们学习omnet 以及了解wsn 中网络发现算法的原理有一定的帮助。
1） 网络设置：
由某一固定数目的节点(20到80)组成的静态网络。
每一个节点都有单独的ID号,以区别于其他的节点。在我们的仿真中,ID数被简单地设置为节点数。
所有节点具有相同的固定传输范围。这导致网络只有双向的链接。
没有任何故障(既没有永久硬件故障,也没有暂时的冲突)。
理想的MAC协议使得所有发送的消息都能被接收成为可能。
2） 算法描述：
在描述算法之前,需要介绍一些概念。为了能清晰地阐述,先假设网络中只有一个节点想要查找拓扑。这个节点被看做主节点。首先,网络中的节点可以这样来分层:根据一个消息沿最短路径,从主节点到达它们所需的跳数。如下图3,假设黑色节点远离主节点为n跳.然后该黑色节点就可以对其邻居节点分类了:
n-1邻近范围包含了所有距离主节点n-1跳的邻居节点。
n邻近范围包含了所有距离主节点n跳的邻居节点。
n+1邻近范围包含的就是更远一跳的邻居节点。
图3 一些符号
我们要测试的拓扑算法有两个阶段。第一个阶段:拓扑请求阶段。节点通过对网络泛洪一个短消息,以通知所有节点它需要知道拓扑信息。拓扑请求终止时,网络边界节点将发动该算法的第二个阶段:拓扑应答阶段。在这个阶段中,拓扑信息将从网络的边界处返回主节点。途中的节点将集合所得到的信息,保持最小的通信量。下面将更加详细地描述拓扑算法的两个阶段和执行特性。
3） 拓扑请求阶段：
当源节点需要知道网络的拓扑信息时,拓扑请求阶段开始启动。它通过广播一个请求消息来宣布自己,这个消息将泛洪整个网络(方法同上所说)。拓扑请求消息包含以下几部分:
源节点地址；
需要查找的网络拓扑跳数；
消息传输经过的跳数；这样,每个节点就能找出自己离源节点多少跳了。
转发消息节点的ID号；对每一个节点来说,找到它自己的邻居节点是必要的。
一个数据结构-------用来存储查找跳数范围内所有节点的位置信息；
每一个第一次收到拓扑请求信息的节点,转发该信息。同时它启动一个计数器。如果该计数器终止,而节点还没有听到任何邻居节点转发它的信息,那么它就判定自己处于网络的边界,它必须发起拓扑应答了。
这个阶段结束时,每个节点都知道了以下信息:
自己远离主节点多少跳；
哪些节点是自己的邻居节点,以及它们都位于什么位置(见图3)；
它自己是否是网络的边界节点(它没有n+1跳邻居节点)；
代码实现如下:
void application::processTopologyRequest(cTopMessage *msg)
{
int source =(int)msg->par(“sourceaddr”); // 得到源地址
int rehops = (int)msg->par(“requirehops”); // 得到网络中要求的hop数
int realhops = (int)msg->par(“hops”); // 得到包实际经历的hop
realhops=realhops+1; // hop 加 1
if (sourceID) // 判断是否是自己发的包
{ delete msg;
return ;
}
//是否曾经收到过这个meesage？
if (IsMessageSeen[source]) // 曾经收到过这个message
{
if(realhops-1>MinHops[ID])
{
if (msgtimerreply[source]!=NULL)
{
delete cancelEvent(msgtimerreply[source]); // 取消定时事件
msgtimerreply[source] = NULL;
}
}
delete msg;
}
Else // 第一次收到这个message
{
IsMessageSeen[source] = true;
MinHops[ID]=realhops;
if(PosOfAllNodes[ID].x-1)
{
cModule *mod = this->parentModule();
PosOfAllNodes[ID].x=mod->par(“PX”);
PosOfAllNodes[ID].y=mod->par(“PY”);
}
if (realhops<rehops) // 实际hop小于设置的hop，转发拓扑请求
{
SEND_TOPOLOGY_REQ(source,realhops);
SET_SELF_TIMER_REPLY(source);
delete msg;
}
if (realhops==rehops) // 实际hop等于设置的hop，因此该节点为规定的边界节点
{
ev <<“source:”<<source<< " ID"<<ID<<" rehops:"<<rehops <<"\n";
SEND_TOPOLOGY_REPLY_NEW(source,MinHops[ID],PosOfAllNodes[ID].x,PosOfAllNodes[ID].y);
delete msg;
}
if (realhops>rehops)
{
delete msg;
}
// setup timer for route reply
}
}
4）拓扑应答阶段：
将转发途中集合到的信息返回给目的端有几种实现方法。我们采用的是利用边界节点直接回复其邻居节点信息给源节点的方法。所谓边界节点,(如前所说)是指远离源节点n跳,又没有n+1跳邻居节点的节点。位于网络边界的节点起动拓扑应答阶段。当一个节点确定自己是边界节点的时候,它直接给给源节点发送一个包含n跳范围内邻居节点信息的消息。 没有在边界的节点当它收到转发来的包的时候,并不马上给源节点回复一个消息,而是启动一个定时器,等待一段时间。如果这段时间内,有边界节点给源回复信息,它则取消发送。若没有,而等待时间又满期,则开始发送信息给源节点。这样,大大地节省了通信量,加快了速度。拓扑应答消息只朝主节点方向转发。为了保证这一点,每个收到应答消息的节点,只有当它比原来发送该消息的节点更靠近主节点一跳时,才允许使用并转发它。
拓扑应答消息包括以下信息:
产生应答消息的节点ID；
目的节点ID；
产生该消息的节点到达目的节点所需的最小跳数；
转发该消息时,到达中间节点的真实跳数；
一个数据结构------描述至今为止所采集到的部分拓扑节点位置信息；
这个阶段结束时,发出拓扑请求的节点将得到一个数据结构,它包含了查找跳
数范围内所有的拓扑信息。
5） 测试结果：
模拟结果图
模拟结果
0 : 1 3 15
1 : 3 15
2 : 4 13
3 : 6 7 15
4 : 5 9 11 13 18 19
5 : 8 9 11 13 18 19
6 : 7 12 15 17
7 : 8 17
8 : 9 10 17 18 19
9 : 17 18 19
10 : 17
11 : 14 18 19
12 : 16
13 : 18 19
18 : 19
6.2.4 结论
本章介绍了无线传感器网络管理的概念、分类及传感器网络管理系统的设计标准；并着重介绍了基于能量管理的SenOS系统、拓扑发现算法TopDisc、可调试的sympathy系统和可编程的Agilla系统。我们还用omnet模拟了一个简单的拓扑发现算法。
6.3 基于路由层安全协议的OMNeT++仿真
6.3.1 基础知识介绍
6.3.1.1无线传感器网络安全性的重要性和必要性
无线传感器网络的应用范围非常广泛，应用场景包括军事、商业、家庭、医疗健康、环境等各个领域。针对不同的应用，WSN 对于安全和容错机制的要求也不同。例如在家庭的应用上，WSN 所在环境较佳，因此对安全和容错机制的要求标准可能降低。相对而言，应用于战场上WSN 则要求非常严格的容错和安全机制。总的来说，由于部署在无人职守的外部环境中，WSN 需要保证数据安全和节点容错来防止敌方或者恶意分子对系统的利用和破坏[45,46,47]。
然而，大多数研究都集中在网络的多跳路由协议这个关键技术上，却很少考虑无线传感器网络的路由安全问题，在所提出的路由协议中，基本上没有一种协议是为了安全目的而设计的。随着无线传感器网络的广泛应用，路由安全必将成为改领域中一个至关重要且急需解决的问题[49]。
6.3.1.2 无线传感器网络的安全目标
(1)访问控制：禁止非授权节点访问网络，给数据包附加消息认证码（MAC）
可以有效防止非授权节点发送合法的数据包。
(2)数据完整性：接收节点应该能够检测数据包在传送过程中是否被篡改，
这可以阻止中间人攻击。WSN 通常用基于分组密码的MAC来保证数据的完整性。
(3)数据保密性：禁止非授权节点知晓数据包的内容，由于共享的无线信道，攻击者可以很容易地窃听传送中的数据包。为了防止信息的泄漏，需要在发送之前对数据包进行加密处理。
(4)防止重放：即使数据包被加密，从而使其内容不被泄漏，攻击者仍然可以捕获合法的数据包，并在稍后重放改包。因此，WSN需要有防止重放的机制。一般地，可以通过网络同步或增加额外的通信负荷来阻止重放攻击。
6.3.1.3无线传感器网络中的路由协议概述
无线传感器网络（WSN）路由协议负责在sink点和其余节点间可靠地传输数据.由于WSN与应用高度相关,单一的路由协议不能满足各种应用需求,因而人们研究了众多的路由协议。
对于目前存在的网络路由协议，可从不同的角度对它们进行分类。按路由发现策略可分为先验式(Proactive)路由和反应式(Reactive)路由。按网络逻辑视图可分为平面路由和层次路由，其中，平面路由协议主要有泛洪(Flooding)、闲聊(Gossiping)[11]、连续分配路由协议(SAR)、基于最小代价场的路由协议(Minimum Cost Field)、通过协商的传感器协议(SPIN)[12]和定向扩散(DD)；层次路由协议主要有低能量自适应分群(LEACH)[8]、门限敏感的传感器网络节能协议(TEEN)[10]和PEGAGIS[9]、多层聚类算法等。路由协议还可按是否基于地理位置进行划分，基于地理位置的协议包括：地理位置和能量感知路由协议(GEAR)、贪婪型无边界路由(GPSR)[13]等；另外，一些最初为Ad Hoc网络设计的协议，也可适用于无线传感器网络。如：SPAN和GAF协议等。
6.3.1.4无线传感器网络路由协议的攻击方法
这里，将网络路由攻击方法归结为以下几种：窃听、欺骗、篡改或重放(Relay)路由信息、选择性转发攻击、“塌陷”(Sinkhole)攻击、“女巫”(Sybil)攻击、“蛀洞”(Wormhole)攻击、HELLO泛洪攻击、应答欺骗(Acknowledgement Spoofing)等[49, 50]。这些攻击适合于不同的路由协议，如表1所示。
(1)窃听、欺骗、篡改或重放路由信息
对路由协议最直接的攻击目标是节点之间交换的路由信息。攻击者通过窃听、欺骗、篡改或重放路由信息，可生成路由环路、引诱或拒绝通信流量、延长或缩短源路由、产生虚假的错误消息、分隔网络、增加端到端的延迟(Latency)等。
(2)选择性转发攻击
多一跳(Multihop)网络通常假设参与传输的节点会透明地转发它接收到的消息。在选择性转发攻击中，恶意节点可能会拒绝转发某些消息并丢弃它们。该攻击的一种简单形式就是恶意节点象黑洞(Black Hole)一样拒绝转发它接收到的数据包。但是，该攻击的弱点就是邻近节点可识别出恶意节点的无效性从而选择另外一条路由。因此，该攻击的一种更巧妙形式就是攻击者选择性地转发数据包，攻击者通过删除或更改一些感兴趣节点的数据包，并将其它信息进行转发以减少节点对其非法操作的猜疑。当攻击者处于数据流路径中时，选择性转发攻击一般最有效。
(3)Sinkhole攻击
在Sinkhole攻击中，攻击者的目标是通过“叛变”节点引诱特定区域内的所有通信流量，在该区域中心造成类似“塌陷”一样的攻击。例如，一些协议是依据链路可靠性、延迟等信息来验证路由质量的。在这种情况下，攻击者可利用足够大的发射功率或Wormhole攻击来提供一条高质量的路由。通过“叛变”节点的真实或虚拟的高质量路由，攻击者的邻近节点很可能通过攻击者向基站转发包，还可以向其邻近节点传播该路由。实际上，攻击者建立一个很大的“洞”，从而可吸引所有节点发往基站的通信。
(4)Sybil攻击[60]
在Sybil攻击中，攻击者对网络中的其他节点以多个身份出现。Sybil攻击能够对基于地理位置的路由协议有显著的威胁。位置感知路由协议通常需要节点与其邻近节点交换坐标信息，从而有效地发送标有指定地址的数据包。一般情况，节点仅从与其相邻的节点接收唯一的一组坐标值，但是使用Sybil攻击的攻击者可以“同时拥有多个位置的坐标”。
(5)Wormhole攻击[61]
在Wormhole攻击中，常见的攻击形式是两个相距很远的恶意节点通过特定方式一起虚报它们之间的距离。位于基站附近的攻击者通过适当设置的Wormhole可以完全破坏路由。攻击者通过Wormhole可以使到基站正常为多跳的节点相信它们到基站只有一两跳的距离。这样可以产生一个Sinkhole，因为Wormhole另一方的攻击者可以人为地提供到基站的高质量路由，如果其他路由没有明显的吸引力则周围区域所有可能的通信将被引诱到这条路由上来。图1(a)给出了一个使用Wormhole产生Sinkhole的例子。
图1 路由协议攻击方法示意图
(6)HELLO泛洪攻击
HELLO泛洪攻击是一种新型的针对传感器网络的攻击方法。许多协议需要节点广播HELLO包来向其相邻节点广播自己。攻击者用足够大的发射功率广播路由或其他信息，这使网络中的每一个节点都相信攻击者是它的邻居。例如，如图1(b)所示，攻击者向网络中每个节点作高质量的路由广告(Advertisement)，从而可以使大量的节点都试图使用这样的路由，但这些节点离攻击者足够远，从而会使所发送的包被丢弃。为了使用HELO泛洪攻击的攻击者不需要构建合法的通信。攻击者可以简单地使用足够大的功率重播窃听(Overheard)到的包，以使网络中每个节点都能接收到。
(7)应答欺骗
由于许多路由协议依赖于固定的链路层应答，因此攻击者可通过欺骗链路层应答来“窃听”相邻节点的数据包。应答欺骗的目标包括使发送者相信实际效率低的链路效率很高，或者认为已经停用或禁用的节点还有效。例如，路由协议可根据链路可靠性选择路径中下一跳。人为增加效率低或无效的链路是使用这种计划的巧妙方式。由于所发送的包在效率低或无效的链路上丢失了，所以攻击者可以使用应答欺骗方式促使目标节点向这些链路上发送包，从而有效地进行选择性转发攻击。
6.3.1.5无线传感器网络中经典路由协议安全性分析
(1) 定向扩散 (Directed Diffusion)协议
定向扩散(Directed Difusion)协议模型是Estrin等人专门为传感器网络设计的路由策略，节点用一组<属性，值>来命名它所生成的数据。Sink节点发出的查询业务用兴趣(interest)来表示，兴趣是一组<属性，值>的组合，逐级扩散，最终遍历全网，找到所有匹配的原始数据。有一个称为“梯度”的变量与整个业务请求的扩散过程相联系，反映了网络中间节点对匹配请求条件的数据源的近似判断。更直接的方法是节点用一组标量值表示它的选择，值越大意味着向该方向继续搜索获得匹配数据的可能性越大，这样的处理最终将会在整个网络中为sink节点的请求建立一个临时的“梯度”场，可以根据“梯度”场，建立多条从数据源到sink节点的路径，然后选择增强其中的一条，用于数据的传输。图2描述了定向扩散模型的工作原理。
图2 Directed Diffusion 定向扩散协议的路由建立过程
针对Directed Difusion，攻击者可以进行多种攻击，包括采用虚假的路由信息，阻止数据流传输到sink节点；攻击者声称自己是sink节点，形成sinkhole攻击；路由路径的攻击者可以进行选择重发，修改数据报内容等攻击；Wormhole攻击以及Svbil攻击等。虽然维持多条路径的方法极大地增强了该协议的健壮性，但是由于缺乏必要的安全保护，使得该协议仍然是十分脆弱的。
(2) LEACH (Low Energy Adaptive Clustering Hierarchy)协议
LEACH是MIT的Chandrakasan等人为无线传感器网络设计的低功耗自适应聚类路由算法。与一般的平面多跳路由协议和静态聚类算法相比，LEACH可以将网络生命周期延长15％，主要通过随机选择聚类首领，平均分担中继通信业务来实现。LEACH定义了“轮(round)” 的概念，一轮由初始化和稳定工作两个阶段组成。为了避免额外的处理开销，稳定工作状态一般持续的时间相对较长。
在初始化阶段，聚类首领是通过下面的机制产生的。传感器节点生成0，1之间的随机数，如果大于阚值T(n)，则选该节点为聚类首领。T(n)的计算方法如下：其中p为节点中成为聚类首领的百分数，r是当前的轮数，G是在过去的1/p轮没有被选择为聚类首领的节点的集合。一旦聚类首领被选定，它们便主动向所有节点广播这一消息。依据接收信号的强度，节点选择它所要加入的组，并告知相应的聚类首领。基于时分复用的方式，聚类首领为其中的每个成员分配通信时隙。在稳定工作阶段，节点持续采集监测数据，传与聚类首领，进行必要的融合处理之后，发送到sink节点，这是一种减小通信业务量的合理工作模式。持续一段时间以后，整个网络进入下一轮工作周期，重新选择聚类首领。
由于节点根据信号的强弱来加入相应的组，因此恶意攻击者可以轻易的采用HELLO Flood攻击，攻击者以大功率进行广播，使得大量的节点都想加入到该组中，然后恶意节点可以采用其他的攻击方法，例如选择重发，修改数据包等，来达到攻击的目的。根据聚类首领的产生机制，节点可以采用Svbil攻击，来增加自己被选择为首领的机会。
(3) GEAR(Geographic and Energy Aware Routing)协议[62]
GEAR也可以认为是Directed Difusion方法一种改进。该协议并不采用向整个网络广播兴趣，而是利用位置信息，向某一个特定的区域进行兴趣的广播，然后利用位置信息(尽可能的选择最短路径)和节点能量剩余的情况，将数据包发回到sink节点。该方法可以极大地节省能源，延长传感器网络的使用寿命。对于GEAR路由协议，节点可以使用虚假的位置信息，sybil攻击，以及总是声称自己的能量处于最大状态，来提高自己成为路由路径中的节点的概率，然后选择重发等攻击方法相结合，达到攻击的目的。
6.3.1.6 安全路由技术分析
由于无线传感器网络路由面临的特殊威胁，可把安全路由技术分为两个层次：采用有效的密钥管理技术，以及设计有效的安全路由协议。针对某一具体攻击，以使用相应的安全策略和防御措施。
6.3.1.6.1 密钥管理技术[20, 23, 24, 25]
对路由面临的攻击和威胁，采用有效的密钥管理技术，对节点间的通信实施加密，以增大路由的安全性。Newsome J 等人就应用对称密钥管理技术，提出了针对Sybil攻击的防御方案[21]。
该方案首先对Sybil攻击进行定义和分类，把攻击类型分为直接通信和非直接通信、虚构认证和偷窃认证、模仿和非模仿等；针对攻击目标又分为分布式存储、路由、数据融合、投票、公正资源分配、误行为检测等。然后在每个节点与一个可信赖的基站之间建立惟一的对称密钥，两个节点之间使用一个像Needham-Schroeder样的协议进行身份认证并且建立一个共享密钥，相邻节点使用产生的共享密钥对它们之间的连接实现加密。虽然一个入侵者仍能利用一个Wormhole在两个节点间建立一个虚假的连接使它们确信它们是邻居，但是入侵者将不能窃听或修改在它们之间的任何将来的连接信息。此安全方案设计方便，针对性强，但是安全措施仅采用对称密钥，整个网络易受到攻击；另外把安全性作为主要设计目标，而忽略了能耗问题。
6.3.1.6.2 安全路由协议
无线传感器网络路由设计的重要目标是降低节点能源损耗，提高网络生命周期。但是，增加安全机制将增大节点能量消耗，使得安全路由协议的设计更为复杂。目前采用的一般方法是在现有路由协议基础上增加安全机制。
对于Sinkhole攻击和Wormholes攻击，采用密钥管理技术防御效果不很好。哈佛大学的Brad Karp等提出了贪婪周边的无状态路由GPSR(Greedy Perimeter Stateless Routing)[13]，在其基础上通过定期广播探测帧来检测黑洞区域，可以有效地发现和抵御Sinkhole攻击和Wormhole攻击。
针对确认欺骗、虚假路由信息等攻击，复旦大学的Yin Changqing等人设计了关于直径的路由协议并增加安全机制，提出了关于直径的启发式安全路由(Heuristic Secure Routing on the Diameter，SRD)[26]。该协议设计思想是首先以源节点A为中心，以r跳数为半径作圆，寻找最小距离的节点B，然后再以B为圆心作圆，以此下去，最终寻找到目的节点D。在此基础上，考虑能量有限问题，将Tokens代替公钥而采取认证和加密机制。该协议以数字签名和密钥管理作为路由安全机制的方法，把计算复杂的能量消耗来代替通信复杂的能量消耗，在尽量保证网络生命期不减弱的情况下，增加了安全机制。但是计算量大，同时，所有节点都在直径范围内进行广播自己的路由信息，使得能量浪费。
综上所述，无论是增加安全机制的GPSR，还是SRD、INTRSN和SLRSN等安全路由协议，都在复杂性、能量损耗和安全性等方面难以平衡，一般都侧重于强化某些性能，而以牺牲其他性能为代价。另一方面，一些安全路由协议是在现有路由协议基础上增加了安全机制，这使得在设计上增加了成本。
6.3.2 在OMNeT++ 中的仿真
定向扩散(Directed Diffusion)仿真过程：
第一步. 建立diffusion工作目录，进入此目录。
第二步. 建立网络拓扑文件node.ned和node.msg：
[node.msg]
message intMessage
{
fields:
int source;
int destination;
int hopCount = 0;
}
[node.ned]
simple Diffusion
gates:
in: in[];
out: out[];
endsimple
module Node
submodules:
node: Diffusion[7]; // we’ll have 7 modules
display: “i=misc/node_s”;
connections:
node[6].out++ --> delay 100ms --> node[5].in++;
node[6].in++ <-- delay 100ms <-- node[5].out++;
node[6].out++ --> delay 100ms --> node[4].in++;
node[6].in++ <-- delay 100ms <-- node[4].out++;
node[6].out++ --> delay 100ms --> node[3].in++;
node[6].in++ <-- delay 100ms <-- node[3].out++;
node[3].out++ --> delay 100ms --> node[4].in++;
node[3].in++ <-- delay 100ms <-- node[4].out++;
node[3].out++ --> delay 100ms --> node[5].in++;
node[3].in++ <-- delay 100ms <-- node[5].out++;
node[3].out++ --> delay 100ms --> node[2].in++;
node[3].in++ <-- delay 100ms <-- node[2].out++;
node[3].out++ --> delay 100ms --> node[1].in++;
node[3].in++ <-- delay 100ms <-- node[1].out++;
node[3].out++ --> delay 100ms --> node[0].in++;
node[3].in++ <-- delay 100ms <-- node[0].out++;
node[4].out++ --> delay 100ms --> node[2].in++;
node[4].in++ <-- delay 100ms <-- node[2].out++;
node[5].out++ --> delay 100ms --> node[1].in++;
node[5].in++ <-- delay 100ms <-- node[1].out++;
node[2].out++ --> delay 100ms --> node[0].in++;
node[2].in++ <-- delay 100ms <-- node[0].out++;
node[1].out++ --> delay 100ms --> node[0].in++;
node[1].in++ <-- delay 100ms <-- node[0].out++;
endmodule
network node : Node
endnetwork
第三步. 创建diffusion.cpp文件如下：
[diffusion.cpp]
#include <stdio.h>
#include <string.h>
#include <omnetpp.h>
#include “node_m.h”
class Diffusion : public cSimpleModule {
protected:
virtual intMessage *genMessage();
virtual void forwardMessage(intMessage *msg);
virtual void updateDisplay();
virtual void initialize();
virtual void handleMessage(cMessage *msg);
};
Define_Module(Diffusion); //在OMNeT中注册模块类
void Diffusion::initialize()
{
// node[0], 即sink节点发送第一个查询消息（interest message）
if (index() == 0)
{
// 调用一个self-message作为启动消息
intMessage *msg = genMessage();
scheduleAt(0.0, msg);
}
}
void Diffusion::handleMessage(cMessage *msg)
{
if (simTime() < 0.3)
{
ev << simTime() << " ";
intMessage *intMsg = check_and_cast<intMessage *>(msg); //强制类型转换
forwardMessage(intMsg); //转发消息
}
else
{
//提取网络的拓扑结构
cTopology topo;
topo.extractByModuleType(“Diffusion”,NULL);
for (int i=0; i<topo.nodes(); i++)
{
cTopology::Node *node = topo.node(i);
ev << "Node i=" << i<< " is " << node->module()->fullPath()<< endl;
ev<<"It has " << node->outLinks()<<" conns to other nodes\n";
ev<< "and " << node->inLinks()<<" conns from other nodes\n";
ev << "Connections to other modules are:\n";
for(int j=0;j<node->outLinks();j++)
{
cTopology::Node *neighbour = node->out(j)->remoteNode();
cGate *gate = node->out(j)->localGate();
ev << " " << neighbour->module()->fullPath()
<< " through gate " << gate->fullName() << endl;
}
}
//调用最短路径算法求到达目标节点node(6)的最短路径 ，以跳数计算
cTopology::Node *targetnode = topo.node(6);
topo.unweightedSingleShortestPathsTo(targetnode);
cTopology::Node *node = topo.node(0);
if (node == NULL)
{
ev << "We(" << fullPath() << ") are not included in the topology.\n";
}
else if (node->paths() == 0)
{
ev << "No path to destination.\n";
}
else
{
while (node != topo.targetNode())
{
ev << "We are in " << node->module()->fullPath() << endl;
ev << node->distanceToTarget() << " hops to go\n";
ev << "There are " << node->paths()
<< " equally good directions, taking the first one\n";
cTopology::LinkOut *path = node->path(0);
ev << "Taking gate" << path->localGate()->fullName()
<<" we arrive in" << path->remoteNode()->module()->fullPath()
<< " on its gate" << path->remoteGate()->fullName() << endl;
node = path->remoteNode();
}
}
if(index() == 6) updateDisplay();
if(index() == 3) updateDisplay();
if(index() == 0) updateDisplay();
}
}
//消息包生成函数
intMessage* Diffusion::genMessage()
{
// 生成源节点和目标节点的地址.
int src = index(); // 模块ID
int n = size(); // 模块向量大小
int dest = intuniform(0,n-1);
char msgName[20];
// 创建消息对象设置源节点和目标节点的域成员.
intMessage *msg = new intMessage(msgName);
msg->setSource(src);
msg->setDestination(dest);
return msg;
}
//转发消息包函数
void Diffusion::forwardMessage(intMessage *msg)
{
int n = gate(“out”)->size();
if (index() != 6)
{
for( int i=0; i<n; i++)
{
ev << "Forwarding message " << “on port out[” << i << “]\n”;
intMessage copy=(intMessage) msg->dup();
send(copy, “out”, i);
}
}
}
//字符更新显示函数
void Diffusion::updateDisplay()
{
char buf[40];
sprintf(buf, “Best Path!”);
displayString().setTagArg(“t”, 0, buf);
}
第四步. 在命令行内进行编译:
nedtool node.ned;
opp_nmakemake -f -e cpp;
nmake -f Makefile.vc;
如下图所示，最终生成diffusion.exe文件。
第五步. 创建一个配置文件[omnetpp.ini]，通过该文件使得模拟程序得知将要模拟的网络，还可以通过该配置文件传递一些参数。
[omnetpp.ini]
Lines beginning with `#’ are comments
[General]
preload-ned-files=*.ned
network=node
第六步. 运行可执行文件diffusion.exe，结果如下图：
6.3.3 总结
通过研究分析，传感器网络是否安全取决于路由协议的设计、密钥的分配管理以及算法是否安全。研究无线传感器网络的安全技术时，可从以下角度进行考虑：
(1)安全性也作为设计路由协议的目标之一。如果最初的网络的协议没有正确地考虑安全问题，而是在后来引入和补充安全机制，将是痛苦和昂贵的事情。
(2)扩展已有路由协议。当前的路由协议如SPIN和GPSR在路由性能方面较为成熟，在设计安全路由协议时，如果通过少量的修改就能达到安全目的，这种扩展原有协议的方法，也给我们提供了很好的研究思路。如SRD、INTRSN等。
(3)对称密钥算法和公钥加密技术并用。在密码学中，虽然公钥加密技术比对称密钥算法表现出了很多的优越性，但对无线传感器网络节点的资源和能量受限等因素，单使用某一加密技术并不理想。因此，研究安全路由技术时，可考虑对称密钥算法和公钥密钥技术并用，以减少计算量而不降低安全强度。
参考文献
[1]Want R, Hopper A, Falcao V, Gibbons J. The active badge location system. ACM Trans. on Information Systems, 1992,10(1): 91102.
[2]Harter A, Hopper A, Steggles P, Ward A, Webster P. The anatomy of a context-aware application. In: Proc. of the 5th Annual ACM/IEEE Int’l Conf. on Mobile Computing and Networking. Seattle: ACM Press, 1999. 5968.
[3]Bahl P, Padmanabhan VN. RADAR: An in-building RF-based user location and tracking system. In: Proc. of the IEEE INFOCOM 2000. Vol.2, Tel Aviv: IEEE Computer and Communications Societies, 2000. 775784.
[4]Hightower J, Boriello G, Want R. SpotON: An indoor 3D location sensing technology based on RF signal strength. Technical Report UW CSE 2000-02-02, Seattle: Department of Computer Science and Engineering, University of Washington, 2000.
[5]Priyantha NB, Chakraborty A, Balakrishnan H. The cricket location-support system. In: Proc. of the 6th Annual Int’l Conf. on Mobile Computing and Networking. Boston: ACM Press, 2000. 3243
[6]Priyantha N B. The cricket indoor location system: [dissertation] Massachusetts institute of
technology, 2005
[7]Lorincz K, Welsh M. Motetrack: a robust decentralized approach to RF-based location tracking. In: Proceedings of the International workshop on location and context-awareness. Pervasive, 2005
[8]Bulusu N, Heidemann J, Estrin D. GPS-Less low cost outdoor localization for very small devices. IEEE Personal Communications, 2000,7(5):2834.
[9]Bulusu B, Heidemann J, Estrin D. Density adaptive algorithms for beacon placement in wireless sensor networks. In: IEEE ICDCS’01,Phoenix, AZ. April 2001
[10]Doherty L, Pister KSJ, Ghaoui LE. Convex position estimation in wireless sensor networks. In: Proc. of the IEEE INFOCOM 2001. Vol.3, Anchorage: IEEE Computer and Communications Societies, 2001. 16551663.
[11]Doherty L. Algorithms for position and data recovery in wireless sensor networks [MS. Thesis]. Berkeley: University of California, 2000.
[12]Capkun S, Hamdi M, Hubaux J-P. GPS-Free positioning in mobile ad-hoc networks. Cluster Computing, 2002,5(2):157167
[13]Iyengar R, Sikdar B. Scalable and distributed GPS free positioning for sensor networks. In: Proc. of IEEE Int’l Conf. on Communications 2003. Vol.1, Anchorage: IEEE Communications Society, 2003. 338342.
[14]Nicolescu D, Nath B. Ad-Hoc positioning systems (APS). In: Proc. of the 2001 IEEE Global Telecommunications Conf. Vol.5, San Antonio: IEEE Communications Society, 2001. 29262931.
[15]Niculescu D, Nath B. DV based positioning in ad hoc networks. Journal of Telecommunication Systems, 2003,22(1/4):267280.
[16]Niculescu D, Nath B. Ad hoc positioning system (APS) using AoA. In: Proc. of the IEEE INFOCOM 2003. Vol.3, San Francisco: IEEE Computer and Communications Societies, 2003. 17341743.
[17]Beutel J. Geolocation in a PicoRadio environment [MS. Thesis]. Berkeley: UC Berkeley, 1999.
[18]Savarese C, Rabaey JM, Beutel J. Locationing in distributed ad-hoc wireless sensor network. In: Proc. of the 2001 IEEE Int’l Conf. on Acoustics, Speech, and Signal. Vol.4, Salt Lake: IEEE Signal Processing Society, 2001. 20372040.
[19]Savarese C, Rabay J, Langendoen K. Robust positioning algorithms for distributed ad-hoc wireless sensor networks. In: Ellis CS, ed. Proc. of the USENIX Technical Annual Conf. Monterey: USENIX Press, 2002. 317327.
[20]Bergamo P, Mazzini G. Localization in sensor networks with fading and mobility. In: Proc. of the 13th IEEE Int’l Symp. on Personal, Indoor and Mobile Radio Communications. Lisbon: IEEE Communications Society, 2002,2:750754.
[21]Savvides A, Han C-C, Srivastava MB. Dynamic fine-grained localization in ad-hoc networks of sensors. In: Proc. of the 7th Annual Int’l Conf. on Mobile Computing and Networking. Rome: ACM Press, 2001. 166179.
[22]Avvides A, Park H, Srivastava MB. The bits and flops of the N-hop multilateration primitive for node localization problems. In: Proc. of the 1st ACM Int’l Workshop on Wireless Sensor Networks and Applications. Atlanta: ACM Press, 2002. 112121.
[23]He T, Huang C, Blum B M, Stankovic J A Abdelzaher T. Range-free localization schemes for
large scale sensor networks. In: Proc 9th Annual Int’1 Conf on Mobile Computing and Networks, San Diego, CA.,2003
[24]Chong L,Kui W. Sensor localization with ring overlapping based on comparion of received signal strength indicator.2004
[25]Borg I, Groener P. Modern multidimensional scaling, theory and applications. Springer-Verlag, New York, 1997
[26]Shang Y, Ruml W, Zhang Y, Fromherz MPJ. Localization from mere connectivity. In: Proc. of the 4th ACM Int’l Symp. on Mobile Ad Hoc Networking & Computing. Annapolis: ACM Press, 2003.
[27]Shang Y, Ruml W, Zhang Y, Fromherz MPJ. Improved MDS-Based Localization. In: Proc. of the IEEE InforCom, March 2004
[28]Ahmed A, Shang Y, Shi H. Variants of multidimensional scaling for node localization. In: Proceedings of the 2005 11’th International Conference on Parallel and Distributed Systems,2005
[29]Ji X., Zha H. Robust Sensor localization in wireless ad hoc sensor networks. In: Proc. of the IEEE InforCom 2003
[30]Ji X., Zha H. Sensor positioning in wireless ad-hoc sensor networks using multidimensional scaling. In: Proc. of the IEEE InforCom March 2004
[31]Patwari N, Hero III A.O. Distributed Weighted-Multidimensional Scaling for Node Localization in Sensor Networks. In: ACM Journal, June 2005
[32]Cheng K W, So H C, A multidimensional scaling framework for mobile location using time-of-arrival measurements. In: IEEE transactions on signal processing, vol,53,No 2, 2005,2
[33]Tao P，Rudys A，I_add A M，Wallach D S．Wireless LAN Location—Sensing for Security Applications[A]，Proceedings of the Second ACM Workshop on Wireless Security (WiSe)[C]，San Diego，CA，USA，2003
[34]Lingxuan Hu, David Evans.Localization for Mobile Sensor Networks.In: ACM MobiCom 2004
[35] http://www.omnetpp/index.php
[36]Athanassios Boulis, Sanjay Jha Network management in new realms: wirelesssensor networks. INTERNATIONAL JOURNAL OF NETWORK MANAGEMENT，2005; 15（4）: 219–221
[37]Winnie Louis Lee,_ Amitava Datta, Rachel Cardell-Oliver ,Network Management in Wireless Sensor Networks,
[38]B. Deb, S. Bhatnagar, and B. Nath, Tech. Rep. A Topology Discovery Algorithm for Sensor
Networks with Applications to Network Management. DCS-TR-441, Rutgers University (2001).
[39] 梁韦，刘振宇，车 畅，无线传感器网络的能量管理协议研究. 仪 器 仪 表 学 报，2006，27(6):291:293.
[40] S. Hong and T. Kim, SenOS: State-driven Operating System Architecture for Dynamic Sensor Node Reconfigurability, International Conference on Ubiquitous Computing
(2003).
[41] 于海斌 曾 鹏 尚志军 梁 英.分布式无线传感器网络管理机制研究,2005,26(11):1203~1209.
[42]C.-L. Fok, G.-C. Roman, and C. Lu. Mobile agent middleware for sensor networks: An application case study. In Proceedings of the 4th International Conference on Information Processing in Sensor Networks (IPSN’05), 2005.
[43] Athanassios Boulis, “Models for Programmability in Sensor Networks,”
in Handbook of Sensor Networks: Compact Wireless and Wired Sensing Systems, M. Ilyas and I. Mahgoub, eds., Boca Raton, FL,pp. 1.1–1.14, CRC Press, 2004.
[44]N. Ramanathan, E. Kohler, and D. Estrin, Sympathy for the Sensor Network Debugger International Journal for Network Management 15, 223 (2005).
[45] Akyildiz IF, Su W, Sankarasubramaniam Y, Cayirci E. A survey on Sensor Networks. IEEE Communications Magazine, 2002,40(8): 102-114.
[46] Akyildiz IF, Su W, Sankarasubramaniam Y, Cayirci E. Wireless Sensor Networks: A Survey. Computer Networks, 2002,38(4): 393-422.
[47] 任新辉，刘斌，徐勇军，李晓维. 无线传感器网络的通信安全
[48] Kemal Akkava and Mohamed Younis. A Survey on Routing Protocols for Wireless Sensor Networks. November 2003.
[49] GUO Zhi-yuan,HE Qi-yuan. Study on Security of Routing Protocol in Wireless Sensor Network.
[50] Karlof C, Wagner D. Secure Routing in Sensor Networks: Attacks and Countermeasures. Ad Hoc Networks, 2003,1(1):293-315.
[51] C Intanagonwiwat, R Govindan and D Estrin. Direeted Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks[C]. in the Proceedings of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking(MobiCom’O0),Boston, MA,August 2000.
[52] Heinzelman W, Chandrakasan A, Balakrishnan H. Energy-efficient Communication Protocol for Wireless Microsensor Networks. In: Proc. of the 33rd Annual Hawaii Int’l Conf. on System Sciences. Maui: IEEE Computer Society, 2000. 3005-3014.
[53] Lindsey S, Raghavendra CS. PEGASIS: Power-efficient gathering in sensor information systems. In: Proc. of the IEEE Aerospace Conf. Montana: IEEE Aerospace and Electronic Systems Society, 2002. 1125-1130.
[54] Manjeshwar A, Agrawal DP. TEEN: A protocol for enhanced efficiency in wireless sensor networks. In: Int’l Proc. of the 15th Parallel and Distributed Processing Symp. San Francisco: IEEE Computer Society, 2001. 2009-2015.
[55] Haas ZJ, Halpern JY, Li L. Gossip-Based ad hoc Routing. In: Proc. of the IEEE INFOCOM. New York: IEEE Communications Society, 2002. 1707-1716.
[56] Kulik J, Heinzelman WR, Balakrishnan H. Negotiation based protocols for disseminating information in wireless sensor networks. Wireless Networks, 2002,8(2-3):169-185.
[57] Karp B, Kung H. GPSR: Greedy perimeter stateless routing for wireless networks. In: Proc. of the 6th Annual Int’l Conf. on Mobile Computing and Networking. Boston: ACM Press, 2000. 243-254.
[58] W. Heinzelman, A. Sinha, A. Wang, A. Chandrakasan. Energy-scalable algorithms and protocols for wireless microsensor networks. Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP '00), June 2000.
[59] W. Heinzelman, A. Chandrakasan, H. Balakrishnan. An application-specific protocol architecture for wireless microsensor networks. in press: IEEE Transaction on Wireless Networking.
[60] I. R. Uouceur. The Sybil Attack. In: 1st lnremotionnl Workshop on
Peer-to-Peer Syslcmr (IPTPS '0202). March 2002.
[61] Y.-C. Hu, A. Perrig, and U. B. Johnson. Wormhole detection in wireless
ad hoc networks. Depmenent of Computer Science, Rice University. Tech. Rep. TR01-384, June 2002.
[62] Y. Yu, R. Govindan, and U. Estrin. Geographical and energy awaremuting: A recursive dam dissemination pmtocol for wireless sensornetworkss. University of California at Los Angeles Computer Science Department. Tech. Rep. UCLAKSU-TR-01-0023. May 2001.
[63] Wang Xiao-yun, Yang Li-zhen, Chen Ke-fei. SLEACH: Secure Low-Energy Adaptive Clustering Hierarchy Protocol for Wireless Sensor Networks. Wuhan University Journal of Natural Science, Vol.10 No.1 2005. 127-131
[64] Haowen Chan，Adrian Perrig，Dawn Song. Random Key Predistribution Schemes for Sensor Networks
[65] Newsome J, Shi E, Song D, et a1．The Sybil Attack in Sensor Networks: Analysis&Defenses[C]．In: Proceedings of the 3rd International Symposium oil Information Processing in Sensor Networks (IPSN’04), April 26-27, 2004. 259-268．
[66] Chan Haowen, Perrig A. Security and Privacy in Sensor networks[J]. Computer，2003，36(10)：103-105．
[67] Haowen Chan, Adrian Perrig, Dawn Song. Random Key Predistribution Schemes for Sensor Networks.
[68] Laurent Eschenauer, Virgil D. Gligor A Key-Management Scheme for Distributed Sensor Networks.
[69] Seyit A.Camtepe, Bulent Yener Key Distribution Mechanisms for Wireless Sensor Networks: a Survey.
[70] Yin Changqing, Huang Shaoyin, Su Pengcheng, et a1. Secure Routing for Large-scale Wireless Sensor Networks[C]． In: Proceedings of ICCT’2003.2003:1282-1286.
[71] 贾玉福，董天临，石坚. 无线传感器网络安全问题分析
[72] 王英龙，牛秋娜，王美琴. 移动Ad Hoc 网路的安全路由协议研究
[73] TANG Yong, HOU Ming-Tian, HANG Xin. Overview of Routing Protocols in Wireless Sensor Networks.
[74] 乔晓军，张馨，王成，任东，何秀红. 无线传感器网络在农业中的应用
第七章 实例（无线传感器网络移动节点定位仿真）
概述
无线传感器网络作为一种全新的信息获取和处理技术，可以在广泛的应用领域内实现复杂的大规模监测和追踪任务，而网络节点的自身定位是大多数应用的基础。
大多数应用中，不知道传感器位置而感知的数据是没有意义的[1]。传感器节点必须明确自身位置才能为用户提供“在什么位置或区域发生了特定事件”的信息，实现对外部目标的定位和追踪[2]。另一方面，了解传感器节点位置信息还可以提高路由效率[3，4]，为网络提供命名空间[5]，向部署者报告网络的覆盖质量[6,7]，实现网络的负载均衡[8，9]以及网络拓扑的自配置[10]。而人工部署和为所有网络节点安装GPS接收器都会受到成本、功耗、扩展性、节点尺寸等因素的限制，甚至在某些场合（如室内无法使用GPS定位）可能根本无法实现。因此无线传感器网络必须采用一定的机制，使得网络在小部分节点位置已知或者所有节点位置未知的情况下，实现WSN中位置未知节点的自身定位。
无线传感器网络中定位系统按照无线传感器节点是否可以移动可分为：静态节点的定位系统和移动节点的定位系统。本章主要介绍移动节点定位系统的算法。
7.1 移动定位算法介绍
随着微机电和网络技术的发展，无线传感器网络的应用愈来愈广泛。很多应用要利用到移动无线传感器网络节点的位置，如移动目标的跟踪、用移动目标来收集信息、移动无线传感器网络中基于位置的路由等等。这使得迅速获得移动节点的位置十分重要。
移动节点定位算法按应用场合可分为室内（In-door）移动节点定位算法和室外(Out-door)移动节点定位算法。
7.1.1 室内移动节点定位算法
室内移动节点定位算法有Active Badge系统[11]、RADAR系统[12]、Cricket系统[13]等等。这些定位算法也适用于静态节点的定位。
7.1.1.1 Active Badge系统
Active Badge系统由英国Olivetti研究中心1992年开发研制，它是最早的室内定位跟踪系统之一。
该系统在待定位的物体上附上标识，标识使用红外发射机定期发送自身唯一的ID识别码。同时，在定位区域(建筑物) 的每一个房间里固定放置红外接收机，用于提取红外信号携带的数据，并通过有线网络发送给控制中心数据库。墙壁对红外线的屏蔽作用，确保接收机只能接受到同一房间中的标识信号，也就是说接收机和标识位于同一个房间，从而实现对运动物体的准确定位。但是，有线网络的使用大大增加了系统的成本，一定程度上限制了系统容量的扩充。同时，对于红外线本身，房间中存在着一些死角，如果物体到达这些位置，红外接收机不能正确检测，严重影响了系统定位的实时性和准确性。
7.1.1.2 RADAR系统
RADAR系统是由Microsoft公司2000年开发研制的，它也是室内定位跟踪系统之一。
与其他室内定位系统相仿，该系统也是通过采集接收器与多个发射器之间的距离，并使用三角测量法计算出用户的位置。数据可以由接收器本地处理，也可由中心服务器集中处理。不同之处在于RADAR系统把信号强度作为估算射频发射器与接收器间距的依据，并且发射器的射频信号可以覆盖整个定位区域（建筑物）。系统建立射频信号的传输信道模型，确定信号衰减与发射器、接收器间墙壁数量的关系，从而得到给定位置接收器最优的距离估算参数。但是在建筑物内，射频信号传输环境是不断变化的，如果采用同一传输模型，不可避免地影响了系统的精确度。
7.1.1.3 Cricket系统
Cricket系统是美国MIT实验室2000年研制的，该系统是室内定位和跟踪系统之一。
Cricket室内定位系统是由用户携带的接收器、固定放置在建筑物内的信标（信标包括射频发送器和超声波发送器）以及中心服务器组成。每一个信标被赋予唯一的识别码，以识别自身所在的区域，并使用射频信号定时广播该位置信息。接收器则接收信标发来的信号，确定距离自身最近的信标，该信标识别码标识的区域即为用户所在区域，然后把位置信息转发给服务器。由服务器完成对数据的进一步计算处理，从而实现定位功能。
为了使接收器准确地确定到信标的距离，系统使用了射频信号和超声波进行测距。射频信号的速率接近300，000，000m/s，远远高于超声波340m/s的速率。接收器会先收到射频信号，而后才是超声波脉冲。通过测量两种信号的到达时间差，来估算出与信标之间的距离，找出最近的一个信标。
7.1.2 室外移动节点定位算法
室外移动节点定位算法有基于静态定位的移动定位算法和纯移动定位算法。
7.1.2.1 基于静态定位的移动定位算法
基于静态定位的移动定位算法主要用于静态网络节点的定位。这些算法在静态定位后考虑节点的移动性。他们都有一个共同的特点：同一时刻只允许小部分节点移动，而且定位错误容易累积。这种类型的算法有DV-Hop算法[14]和Amorphous算法[15]等等。
DV-Hop算法是美国鲁特格斯大学（Rutgers University）Niculescu等人提出的。DV—Hop算法 由3个阶段组成。首先使用典型的距离矢量交换协议，使网络中所有节点获得距锚节点的跳数。第2阶段，在获得其他锚节点位置和相隔跳距之后，锚节点计算网络平均每跳距离，然后将其作为一个校正值广播至网络中。校正值采用可控洪泛法在网络中传播。这意味着一个节点仅接受获得的第1个校正值，而丢弃所有后来者，这个策略确保了绝大多数节点可从最近的锚节点接收校正值。在大型网络中，可通过为数据包设置一个TTL域来减少通信量，当接收到校正值之后，节点根据跳数计算与锚节点之间的距离。当未知节点获得与3个或更多锚节点的距离时，则在第3阶段执行三边测量定位。在定位完成以后，如果有小部分节点移动，需要重新定位，则可以发送请求给邻居节点，取得邻居节点的位置，然后用跳距估计到邻居节点的距离，最后采用三边测量法定位。
Amorphous算法[15]和DV-Hop[14]算法不同之处在于估算到锚节点距离和计算节点位置的方法。它利用网络节点密度来估计每跳的距离，并且把邻居节点到锚节点的跳数平均值作为到锚节点的跳数，最后利用多边测量法进行定位。定位完成后，如果有小部分节点移动，需要重新定位，则广播一个位置服务请求，在通信半径内的所有节点通过发送其自身的位置来响应。请求者获取每一个应答节点的位置，并且使用信号强度预测到应答节点的距离。因为请求者获得了应答节点的位置和到应答节点的距离，它可以使用多边测量法来计算其自身的位置。
7.1.2.2 纯移动定位算法
无线传感器网络纯移动定位算法有全部节点都使用GPS定位的移动定位系统、部分节点使用GPS的移动定位系统和不需使用GPS的移动定位系统。 全部节点都使用GPS定位的移动定位系统有ZebraNet系统[16]。部分节点使用GPS的移动定位系统有MCL(Monte Carlo Localization)算法[17]。不需使用GPS的移动定位系统有DL(directional localization)系统[18]。
2002年，Princeton University大学的Philo Juang等人设计了ZebraNet系统,该系统用于跟踪研究肯尼亚的野生斑马群。系统由很多带有GPS定位系统的节点和一个移动基站组成。节点安置在部分斑马身上，节点每隔3分钟使用GPS定位系统确定自己的位置，并且把收集的数据和相关位置保存在节点上。基站位于研究人员驾驶的车上，当车靠近斑马群时，节点通过射频把收集到的数据发送到基站。该系统虽然节点都是移动的，但不需要特定的算法进行定位，因为所有的节点采用GPS定位。
蒙特卡罗定位法首先用于机器人定位领域。2004年，Virginia大学的Lingxuan Hu等人首次将蒙特卡罗定位法（MCL）应用于无线传感器网络。此前很少有定位技术考虑节点的移动性。尽管移动性似乎使得定位更加困难，但Lingxuan Hu等人提出了顺序蒙特卡罗方法，这种方法能够利用移动性来提高定位精度。其论文中提到的是一种无需测距的定位方法，不需要额外的硬件，核心思想是用包含N个样本的集合来表示节点的位置分布。算法假设已知节点移动的最大速度为V，如果现在传感器的位置在A点，过一个时间单位后，节点一定分布在以A为圆心，V为半径的圆内，从这个圆里随机抽取一点，根据一跳和二跳锚节点来判断此节点是否是符合连通性条件的节点，从而把不符合条件的节点过滤掉。算法每次抽取50个符合连通性条件的样本点，计算这50个样本的平均值作为对节点位置的估计。实验结果表明，这种方法在很多条件下优于已知的最好静态定位方法。
2006年，美国纽约科技大学（Polytechnic University）Akcan等人提出了DL定位方法。该方法应用于没有锚节点的场合，易于布置。但时它也有一些限制条件，如它需要节点上安装有感知运动方向和运动速度的设备，并且有测距设备测量到邻居节点之间的距离。节点可以获得自身的运动方向和速度，通过与邻居节点通信可以获得邻居节点的运动方向和速度，通过测距设备可以测得到邻居节点间的距离。利用这些方向、速度和距离，该方法可以实现移动节点的定位。
7.2 移动定位算法的OMNeT++仿真
OMNeT++是一个面向对象的离散事件网络仿真工具，能用于无线传感器网络的模拟。本小节主要介绍MCL算法在OMNeT++中的仿真。
7.2.1 MCL（Monte Carlo Localization）定位算法简介
MCL方法首先用于机器人定位，直到2004年，Virginia大学的Lingxuan Hu等人才将蒙特卡罗定位法（MCL）应用于无线传感器网络。仿真结果表明，在移动传感器网络中算法的定位性能比较理想。
MCL方法主要有两个阶段：预测阶段和过滤阶段。预测阶段根据上一个时刻样本点的位置估计现在的位置。假如t-1时刻传感器可能的位置是，传感器最大的速度是，则t时刻传感器的位置在以为圆心，为半径的圆内，如图1所示。
图1
S是一跳锚节点 S是两跳锚节点
图2
过滤阶段是根据传感器感知到的数据把不可能的样本过滤掉，这里主要是根据传感器接收到的一跳和两跳锚节点信息来过滤样本。如果S是一跳锚节点的集合，T是两跳锚节点的集合，则过滤条件为：。图2中的阴影部分是节点可能的位置。算法每次抽取50个符合过滤条件的样本点，用这50个样本的平均值作为对节点位置的估计。
其算法伪码如下：
//初始化： 节点不知道自己的初始位置，从其传感器布置区域随机选取N个位置。
//使用t时刻的传感器数据(1跳和2跳锚节点信息)，t-1时刻位置和状态转移函数转移计算t时刻的位置
While（size()<N） do
//预测阶段
//过滤阶段
定位算法的流程图如下：
7.2.2 MCL（Monte Carlo Localization）的OMNeT++仿真
建立一个仿真分为两个阶段：建立网络拓扑阶段和编码阶段。
7.2.2.1 建立网络拓扑
建立网络拓扑有两个步骤：建立网络节点的描述文件(.ned文件)和建立网络的描述文件。首先建立节点的网络描述文件。网络节点有三个模块:mobility,bottomlayer,position。mobility实现节点的移动，bottomlayer实现节点间的物理层连接，position实现定位算法。网络节点的拓扑图如下：
相应的mobileHost.ned文件为：
simple Mobility
parameters:
minSpeed: numeric const, // 最小速度
maxSpeed: numeric const, //最大速度
movKind: numeric const, //节点运动到边界时的处理方式
XRange: numeric const, // 节点布置区域的宽度
YRange: numeric const, //节点布置区域的长度
pauseTime: numeric const, //到达一个目标后的等待时间
moveInterval: numeric const, //两步之间的时间
gates:
out: out;
endsimple
simple bottomLayer
parameters:
seed_r: numeric const, // 锚节点的通信半径
node_r: numeric const, // 待定位节点的通信半径
isSeed: numeric const; // 是否是锚节点
gates:
in: fromMobility;
in: fromPosition;
out: toPosition;
endsimple
simple Positioning
parameters:
isSeed: numeric const, // 是否是锚节点
announceInterval: numeric const, // 锚节点广播自身位置的时间间隔
updateInterval: numeric const, // 待定位节点两次定位间的时间间隔
seed_r: numeric const, // 锚节点的通信半径
node_r: numeric const, // 待定位节点的通信半径
max_v: numeric const, // 最大速度
delta: numeric const; //抽样点可能的误差
gates:
in: fromBottom;
out: toBottom;
endsimple
module MobileHost
parameters:
isSeed: numeric const, // 是否是锚节点
numHost: numeric const, // 总的结点数
x: numeric, // 真实位置的x坐标
y: numeric, // 真实位置的y坐标
Xbound: numeric, // 布置区域的宽度
Ybound: numeric, // 布置区域的长度
seed_r: numeric const, // 锚节点的通信半径
node_r: numeric const, // 待定位节点的通信半径
mobilityModel: string, // 移动模型
posAlgorithm: string; // 定位算法
submodules:
mobility: mobilityModel like Mobility;
parameters:
XRange = Xbound,
YRange = Ybound;
display: “p=260,64;b=24,26”;
bottomlayer: bottomLayer;
parameters:
isSeed = isSeed,
seed_r = seed_r,
node_r = node_r;
display: “p=148,62;b=104,10”;
position: posAlgorithm like Positioning;
parameters:
isSeed = isSeed,
seed_r = seed_r,
node_r = node_r,
max_v = input,
delta = input,
announceInterval = input,
updateInterval = input;
display: “p=148,171;b=104,10”;
connections:
mobility.out --> bottomlayer.fromMobility;
position.toBottom --> bottomlayer.fromPosition;
bottomlayer.toPosition --> position.fromBottom;
display: “p=10,10;b=287,250”;
endmodule
然后建立网络。网络中有seed和node两种节点，seed是锚节点，node是待定位节点。网络中节点数为numHost，锚节点的比率为anchorFraction。网络的拓扑图如下：
相应的mcl.ned文件为：
import “mobileHost.ned”;
module MobileSensorNet
parameters:
numHost: numeric const,
anchorFraction: numeric const,
playgroundSizeX: numeric const,
playgroundSizeY: numeric const;
submodules:
seed: MobileHost[numHost * anchorFraction];
parameters:
isSeed = 1,
numHost = numHost,
Xbound = playgroundSizeX,
Ybound = playgroundSizeY,
x = intuniform(0,playgroundSizeX),
y = intuniform(0,playgroundSizeY);
node: MobileHost[numHost - numHost * anchorFraction];
parameters:
isSeed = 0,
numHost = numHost,
Xbound = playgroundSizeX,
Ybound = playgroundSizeY,
x = intuniform(0,playgroundSizeX),
y = intuniform(0,playgroundSizeY);
endmodule
network mobilesensornet : MobileSensorNet
endnetwork
7.2.2.2 编码阶段
仿真中，我们要用C++代码定义simple模块的行为。这个仿真包含三个简单模块：Mobility，bottomLayer和Positioning。Mobility定义节点的移动方式，bottomLayer定义节点间物理层，Positioning定义MCL定位算法。这里主要介绍MCL定位算法的仿真实现。
MCL算法中，锚节点每隔一定时间要向邻居广播自己的位置：
cMessage *annouceMsg = new cMessage(“Annouce”);
annouceMsg->setKind(MCL_MSG_ANNOUNCE_LOCATION);
scheduleAt(simTime()+announceInterval, annouceMsg);
广播的位置消息格式为：
message LocAnnounce
{
fields:
double x=0;
double y=0;
int hops=0;
int id;
};
待定位节点每隔一定时间要根据收到的锚节点信息确定自身位置：
cMessage *updateMsg = new cMessage(“Update”);
updateMsg->setKind(MCL_MSG_UPDATE_LOCATION);
scheduleAt(simTime()+updateInterval, updateMsg);
算法主要在handlemessage()中处理三种消息：MCL_MSG_ANNOUNCE_LOCATION， MCL_MSG_SEED_LOCATION ，MCL_MSG_UPDATE_LOCATION。
收到MCL_MSG_ANNOUNCE_LOCATION消息后，锚节点向邻居节点广播自己的位置。代码如下：
if(msg->kind() == MCL_MSG_ANNOUNCE_LOCATION)
{
LocAnnounce *locmsg = new LocAnnounce();
int x,y;
bottomlayer->getPos (x,y);
locmsg->setX(x);
locmsg->setY (y);
locmsg->setHops (0);
locmsg->setId(parentModule()->id());
locmsg->setId (MCL_MSG_SEED_LOCATION);
send(locmsg,“toBottom”);
scheduleAt(simTime()+announceInterval, msg);
}
收到MCL_MSG_SEED_LOCATION消息后，待定位节点保存收到的1跳和2跳锚节点位置。
if(msg->kind() == MCL_MSG_SEED_LOCATION)
{
LocAnnounce *locmsg = (LocAnnounce *)msg;
int hops = locmsg->getHops ()+1;
cNeighbourPos *npos = new cNeighbourPos();
npos->x = locmsg->getX ();
npos->y = locmsg->getY ();
npos->id = locmsg->getId ();
if(hops == 1)
nbs1hop.insert(npos); //保存1跳锚节点信息
else if(hops == 2)
nbs2hop.insert(npos); //保存2跳锚节点信息
if(hops < MCL_MAX_HOPS) // 转发锚节点的位置
{
locmsg->setHops (hops);
send(locmsg,“toBottom”);
}
else
delete locmsg;
}
收到MCL_MSG_UPDATE_LOCATION消息后，待定位节点根据收到的锚节点信息估计自己位置，这里主要列出两个关键的函数：getSample（）和meetCondition（）。
getSample（）从以前一时刻一个样本点p为圆心，最大速度radius为半径的圆内随即抽取一点。代码如下：
Coord Algorithm_MCL::getSample(Coord p, double radius)
{
Coord sample_p;
for (; ? {
sample_p.x = p.x - radius + uniform(0,2 * radius);
sample_p.y = p.y - radius + uniform(0,2 * radius);
if (sample_p.distance§ < radius)
return sample_p;
}
}
meetCondition（）判断一个点是否满足1跳和2跳邻居节点的限制条件。代码如下：
int Algorithm_MCL::meetCondition(Coord p)
{
int ret = 1; //放松限制后满足条件
int ql1 = nbs1hop.length();
int ql2 = nbs2hop.length();
if(ql1==0 && ql2==0)
return -1; //不符合条件返回-1
while(ql1-- >0)
{
cNeighbourPos *np = (cNeighbourPos *)nbs1hop.pop();
Coord pt;
pt.x = np->x;
pt.y = np->y;
nbs1hop.insert(np);
if(pt.distance (p) >= seed_r + delta)
return(-1);
else if(pt.distance (p) >= seed_r)
ret = 0; //符合条件返回0
}
while(ql2-- >0)
{
cNeighbourPos *np = (cNeighbourPos *)nbs2hop.pop();
Coord pt;
pt.x = np->x;
pt.y = np->y;
nbs2hop.insert(np);
if ( (pt.distance(p) < seed_r - delta) || (pt.distance(p) >= seed_r + node_r + delta))
return(-1);
else if( (pt.distance (p)<seed_r) || (pt.distance(p) >= seed_r + node_r) )
ret = 0;
}
return ret;
}
7.2.2.3 算法的性能评价
我们用OMNeT++实现了MCL算法，在OMNeT++上运行效果如图3所示：
图3
绿色节点表示锚节点，红色节点表示待定位节点，黄色节点表示已经定位好的节点，黑色节点表示因信息不够未能定位的节点。
MCL定位算法在移动传感器网络中表现了良好的性能，【17】中有对MCL算法的详细分析，并对MCL、Centroid和Amorphous算法进行了比较。如图4所示：
图4
图4中，移动传感器网络节点的通信距离为r，锚节点密度为1，节点密度为10，节点的最大运动速度为r的情况下，MCL的定位精度在0.5r左右。在相同的条件下,MCL的定位性能比Centroid和Amorphous都要好。
7.3.总结和发展趋势
随着技术的进步，无线传感器网络的应用越来越广泛，其中很多无线传感器网络应用涉及到移动节点的定位。移动节点定位由于其移动性而使得算法更加复杂，在各种场合实现适用的移动定位算法是摆在研究者面前的一个重要课题。本章概述了各种移动节点定位算法，并用OMNeT++仿真了MCL移动定位算法。
目前的移动传感器网络的定位算法主要考虑在理想条件下的定位，如MCL，DL定位等。然而，无线传感器网络应用领域在不断延伸，已经有些领域涉及到复杂环境，如矿井、水下和太空。这些环境和理想环境大不一样，比如存在多径、非视距和信号衰减不同等影响。在这些复杂环境下研究出符合要求的定位算法正在成为移动定位研究中的重要课题。
参考文献
[1]Rabacy JJ, Ammer MJ, da Silva Jr. JL, Patel D, Roundy S. Picorodio supports ad hoc ultra-low power wireless networking. Computer, 2000,33(7):4248
[2]Savarese C, Rabaey JM, Beutel J. Locationing in distributed ad-hoc wireless sensor network. In: Proc. of the 2001 IEEE Int’l Conf. on Acoustics, Speech, and Signal. Vol.4, Salt Lake: IEEE Signal Processing Society, 2001. 20372040.
[3]Capkun S, Hamdi M, Hubaux J-P. GPS-Free positioning in mobile ad-hoc networks. Cluster Computing, 2002,5(2):157167.
[4]Doherty L, Pister KSJ, Ghaoui LE. Convex position estimation in wireless sensor networks. In: Proc. of the IEEE INFOCOM 2001. Vol.3, Anchorage: IEEE Computer and Communications Societies, 2001. 16551663.
[5]Girod L, Estrin D. Robust range estimation using acoustic and multimodal sensing. In: Proc. of the IEEE/RSJ Int’l Conf. on Intelligent Robots and Systems (IROS 01). Vol.3, Maui: IEEE Robotics and Automation Society, 2001. 13121320.
[6]Meguerdichian S, Koushanfar F, Potkonjak M, Srivastava MB. Coverage problems in wireless ad-hoc sensor networks. In: Proc. of the IEEE INFOCOM 2001. Vol.3, Anchorage: IEEE Computer and Communications Societies, 2001. 13801387.
[7]Bulusu N, Heidemann J, Estrin D. Adaptive beacon placement. In: Young DC, ed. Proc. of the 21st Int’l Conf. on Distributed Computing Systems. Mesa: IEEE Computer Society, 2001. 489498.
[8]Chang J-H, Tassiulas L. Energy conserving routing in wireless ad-hoc networking. In: Proc. of the IEEE INFOCOM 2000. Tel Aviv: IEEE Computer and Communications Societies, 2000,1:2231.
[9]Xu Y, Heidemann J, Estrin D. Geography-Informed energy conservation for ad hoc routing. In: Proc. of the 7th Annual Conf. on Mobile Computing and Networking. Rome: ACM Press, 2001. 7084.
[10]Alberto Cerpa, Deborah Estrin. Ascent: Adaptive self-configuring sensor network topologies. ACM SIGCOMM Computer Communication Review, 2002,32(1):6262.
[11]BAHL, P., AND PADMANABHAN, V. RADAR: An In-Building RF-based User Location and Tracking System. InProc. IEEE INFOCOM (Tel-Aviv, Israel, Mar. 2000).
[12]WANT, R., HOPPER, A., FALCAO, V., AND GIBBONS, J.The Active Badge Location System. ACM Transactions on Information Systems 10, 1 (January 1992), 91–102.
[13]Priyantha NB，Chakraborty A，Balakrishnan H．The cricket location-support system．In：Proc．of the 6th Annual Int’l Conf．on Mobile Computing and Networking．Boston：ACM Press．2000．32—43．
[14]D. Niculescu and B. Nath, Ad hoc positioning system (APS), in GLOBECOM. IEEE, November 2001.
[15]Radhika Nagpal, Howard Shrobe, and Jonathan Bachrach. Organizing a Global Coordinate System from Local Information on an Ad Hoc Sensor Network. 2nd International Workshop on Information Processing in Sensor Networks (IPSN). April 2003.
[16]JUANG, P., OKI, H., WANG, Y., MARTONOSI, M., PEH, L. S., AND RUBENSTEIN, D. Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with zebranet. Proc. of ASPLOS '02 (October 2002), 96–107.
[17]L.Hu, D.Evans: Localization for Mobile Sensor Networks. Tenth Annual International Conference on Mobile Computing and Networking (MobiCom 2004), USA.2004.
[18]Hüseyin Akcan, Hervé Brönnimann,Vassil Kriakov,Alex Delis, GPS Free Node Localization in Mobile Wireless Sensor Networks. Proceedings of the 5th ACM international workshop on Data engineering for wireless and mobile access, USA,2006.
更多推荐
OMNeT++理论算法仿真详述
发布评论