（计算机系统结构专业论文）无线传感器网络中标识分配机制的研究.pdf

摘要 摘要 随着嵌入式系统、低功耗无线通信和微电子机械系统等技术的发展，传感 器网络作为近几年新兴的研究热点之一，可应用于军事，商业，医疗，环境保 护以及灾难拯救等许多重要领域，已经成为计算机学科一个活跃的研究分支。 由于传感器节点体积微小，携带电量十分有限，因此一直以来，网络的节能性 成为衡量传感器网络性能的一个重要指标。与处理和传感过程相比，通信过程 消耗了传感器节点的绝大部分能量。而相对于通过数据融合技术降低数据载荷 而言，节点标识的能耗开销显得比较突出。因此，研究如何减少地址标识的能量 消耗，对于降低节点能耗、延长传感器网络的生命期有着十分重要的意义。 本文围绕如何设计和实现高效的标识分配机制这一问题，开展了以下研究 工作： 针对传感器网络地址分配过程中为了避免地址冲突而导致通信能耗较大的 问题，提出一种基于静态博弈模型的地址标识分配算法。在采用地址复用技术 的基础上，算法将每个传感器节点看作博弈模型中的一个决策者，定义每个决 策者的利益为分配到与其两跳范围内邻居不产生冲突的地址标识。模型的平衡 状态即是指每个决策者的利益得到满足，各节点分配到局部唯一的地址标识。 因此，算法可通过使博弈模型达到纳什平衡来解决传感器网络中的地址标识分 配问题。在进行地址分配时，利用博弈模型中每个决策者根据其邻居节点信息 可独立地进行决策的特性，算法避免节点间发送大量的交互信息，降低了地址 分配算法的通信消耗。实验结果表明，与p r o 删v e 相比，m a a s 算法的地址冲 突率降低了6 1 ，地址分配过程中传输的数据包数目减少了6 2 。 针对传感器网络中地址标识分配未考虑节点传输频率从而增加了传输能耗 的问题，基于合作博弈模型，提出一种适用于传感器网络的m a c 地址分配算法。 算法将数据传输频繁节点与其数据传输频率较低的邻居节点组成联盟进行地址 分配。节点的s h a p i e y 值与其数据传输频率成正比，从而提高了传输频繁节点在 联盟内部的利益比率，使其所分配到的地址长度小于其它节点，节省了数据传 输中的能量消耗。实验结果表明，与p m a c t i v e 和r e a c t i v e 地址分配算法相比， c m a a 在地址分配过程中传输的数据包数目分别减少了6 2 和3 1 i 与全局地 摘要 址分配相比，c m a a 所分配的地址平均长度减少了约2 0 。 针对传感器网络的整体效益优化的问题，在地址标识分配过程中，从网络 整体出发，提出一种能量有效的m a c 地址分配算法。在地址分配模型中，将所 有节点的共同利益看作传感器网络的整体效益，并引入社会福利函数来解决传 感器网络中的m a c 地址分配问题。算法将每个传感器节点看作是福利经济学中 的一个个体，定义传感器网络的整体效益函数为社会福利函数，并根据节点在 数据传输过程中的能量消耗对其进行地址分配。通过对社会福利函数的求解， 使得所有节点的地址能耗负载更加均衡，从而达到降低节点能量消耗、延长网 络生命期的目的。 针对当前地址标识分配算法没有对分配过程中影响能耗的因素进行评估的 问题，基于对传感器节点工作能耗特点的分析和数据传输能耗模型，建立传感 器网络地址标识分配能量评估模型，对影响地址分配算法能耗的因素进行分析 评估，并比较分析不同分配算法的性能表现。 关键词：无线传感器网络；标识分配；m a c 地址分配；静态博弈；合作博弈； s h a p l e y 值：社会福利函数；福利经济学；能量评估模型 第一章绪论 第一章绪论 随着无线通信、嵌入式系统等技术的发展和实际应用的需要，无线传感器网 络已经成为计算机学科的一个热点研究领域。传感器网络有着广阔的应用前景， 在军事，商业，医疗，环境保护以及灾难拯救等领域都有着巨大的应用优势。由 于传感器节点体积微小，携带电量十分有限，因此一直以来，能量利用率成为影 响网络生命期的一个关键因素，网络的节能性成为了衡量传感器网络性能的重要 指标。与处理和传感过程相比，通信过程消耗了传感器节点的绝大部分能量。其 中，节点标识的能耗开销显得比较突出。因此研究如何减少节点标识的能量消耗， 对于降低节点能耗、延长传感器网络的生命期有羞十分重要的意义。 本章首先介绍传感器网络的体系结构和网络特点，随后介绍无线传感器网络 中的节能技术以及标识分配机制。最后给出本论文的研究内容和组织结构。 1 ，1 无线传感器网络概述 无线传感器网络【l j 综合了传感器、无线通信、嵌入式系统和分布式信息处理 等技术，能够协作地监测、感知和采集两络监莉区域内的各种环境和监测对象的 信息口j 。通过对所获取信息的处理和传送，传感器网络可以将监测数据传输到汇 聚节点和最终用户【3 】。无线传感器网络与a dh o c 飘络( 4 l 有着掘似之处，但存在 较大区别。首先，无线传感器网络的节点规模较大【5 】【6 】；其次，由于环境干扰和 节点故障等因素的影响，传感器节点更易出现故障，从而使得传感器网络的拓扑 结构呈现高度的动态性【7 】。与目前常用的固定网络相比，传感器网络具有节点资 源受限、节点可快速部署、以数据为中心路由等特点【8 】【9 1 。与传统的监控系统相 比，无线传惑器网络具有自组织、功耗小、可扩展性强、在恶劣和特殊的环境下 具有通信能力等优点【1 0 1 ，因此，无线传感器网络有着十分广阔的应用前景】【l 2 1 。 传感器节点散布在监测区域内，每个节点都可以采集数据，并通过单跳或多 跳路由的无线通信方式把数据传送到汇聚节点【1 3 】【1 4 】。汇聚节点直接与互联网相 连，通过互联网或卫星实现任务管理节点( 用户) 与传感器节点之闯钓楣互通 掣刈 【1 6 】。与目前常见的无线局域网【1 7 】和a dh o c 【4 】等无线网络相比，无线传感器网络 具有以下特点i 博j 1 1 9 】： ( 1 ) 节点电源能量有限 传感器节点由电池供电，而电池的容量有限，因此传感器节点容易由于电源 的原因失效i z 引。由于在许多应用场景中，无法给节点电池充电或更换电池，所以 第一章绪论 如果节点电池能量耗尽，那么这个节点在网络中就失去了作用，可将其看作死亡 节点【2 。因此一直以来，能量利用率成为影响网络生命期的关键因素。在传感 器网络中，相关的协议、算法和技术的设计和使用，都应该以节点能量受限为前 提、以节省能耗为设计目标1 2 2 1 。 ( 2 ) 计算、存储等硬件资源以及通信能力有限 传感器节点一般体积较小，主要由电源、传感器、处理器、存储器和收发通 信单元等部分组成【2 0 】【2 3 】，如图1 1 所示。 图1 1 传感器节点结构 传感器节点具有嵌入式的处理器和存储器等器件，由于这些器件的限制，与 普通的计算机相比，传感器节点的计算能力和存储空间十分有限，这就决定了传 感器网络的相关算法和协议层次的设计不能过于复杂【2 2 j 。 传感器节点的通信覆盖范围一般只有几十到几百米，节点之间的通信容易受 到干扰，从而导致通信失败【2 0 1 。由于传感器网络较多受到自然环境等因素的影响， 传感器节点可能会长时间地脱离网络。因此，如何利用有限的节点通信能力，确 保高质量地完成感知和数据传输等任务，成为无线传感器网络设计中的重要目标 【2 2 】 o ( 3 ) 动态网络拓扑 当传感器网络部署完毕，管理者一般很少再干预其节点运行情况。一个节点 可能由于物理环境的影响或者因为电源能量耗尽等故障而退出网络运行；相应 地，也可能由于工作需要而使新的传感器节点加入到网络中。因此，传感器网络 的拓扑结构呈现高度的动态性【2 l 。所以传感器网络的相关协议和算法必须具有较 好的容错性、健壮性和自适应性【2 4 1 。 ( 4 ) 自组织、多跳路由 与传统的固定网络不同，传感器网络一般没有严格的控制中心【l2 1 ，网络的部 署无需依赖于任何预设的网络设施。节点可以随时加入或离开网络，单个节点的 故障不能影响整个网络的运行，具有较强的抗毁性【i6 1 。节点协调各自的行为，节 点启动后就可以快速、自动地组成一个独立的网络，以完成监测、传感数据等任 务【2 2 】。 2 第一章绪论 由于节点通信范围有限，因此只能与其邻居直接通信。如果希望与节点射频 覆盖范围之外的传感器节点通信，则需要通过中间节点进行路由【1 8 j 。与固定网络 有专用的网关和路由器来实现网络多跳路由不同，无线传感器网络中没有专门的 路由设备，多跳路由通过普通的传感器节点完成【2 2 1 。因此每个节点既是信息的发 起者，也是信息的转发者。 ( 5 ) 传感器节点数量较大 在一些应用场景中m 】，传感器节点可以分布在范围很广的地理区域，这样对 于节点的维护就变得十分困难甚至不可维护。因此，为了保证网络的容错性和健 壮性，在这类应用中往往会在监测区域内密集地部署数量巨大的传感器节点，利 用节点间的高度连接性来保证整个网络系统的抗毁性，提高传感器网络的容错能 力【1 3 】。 ( 6 ) 节点没有统一的标识 由于全局地址在通信中的能量消耗较大，因此在传感器网络中并不采用传统 的t c p i p 协议框架对每个节点分配全局唯一的地址标识【2 引。每个节点只知道与其 邻近节点的位置和标识，节点间的通信具有较强的协作性【2 引。 ( 7 ) 以数据为中心 在传感器网络中，观察者感兴趣的是传感器产生的数据而不是网络硬件本 身，因此传感器网络是一种以数据为中心的网络【27 1 。 在无线传感器网络中，能量消耗是网络设计的核心问题，各种节能机制涉及 了网络协议栈的各层，每一层都可以根据自身特点和功能设计不同的节能策略 1 2 8 。物理层的节能技术主要是采用合理的调制方式以及考虑降低输出功率【3 2 】， 此外，调制方式的选择对于节点能耗也有很大影响【3 2 1 。由于传感器节点的制作成 本较低，因此使用高调制等级的无线收发器会大大增加制造成本。当传输数据减 少时，可以通过降低调制等级和传输速度来减少传感器节点的能量消耗【叫。 m a c 层协议【3 4 】【3 5 】主要负责解决媒体访问和差错控制、无线信道的使用控制 和减少节点通信冲突等问题。近年来，对于m a c 层协议的研究取得了许多的成 果【3 6 】，但在控制能量损耗以及如何合理地进行节点间信息交换等问题上，有待进 一步的研究。 相对数据采集和数据处理模块，传感器节点在数据传输中所消耗的能量更大 1 2 4 】【3 7 1 。而数据传输涉及网络路由协议，因此路由算法执行效率的高低，直接决 定了传感器节点收发控制性数据与有效采集数据的比率，从而影响到整个传感器 网络的生存时间【3 8 】。传感器网络节点数量多，所以节点全局统一地址将会带来大 量的负荷，因此不可能像传统的固定网络那样构造一个全球统一的地址方案【3 9 1 。 此外，由于节点能量受限且大都处于静止状态，因此使得传感器网络不能采用传 第一章绪论 统的基于i p 的路由协议，而且a dh o c 网络中现有的路由协议也不完全适用【4 0 4 4 1 。 为传感器网络设计的路由协议可以分为平面型路由协议和分层型路由协议 【2 8 】 4 5 1 【4 胡。在路由过程中，传感器节点可以进行数据融合【4 孔，使得中间节点不是 简单地转发所收到的数据。由于同一区域内的节点发送的数据具有很大的冗余 性，因此如果中间节点对这些数据进行数据融合，只转发有用的信息，将可以有 效地降低整个网络的数据传送能量消耗【4 7 】。 此外，在传感器网络中，还应考虑采用自适应的跨层优化协议【4 8 】【4 9 j 。这是 因为传统的分层协议设计方法虽然简化了设计，使互联网稳定、兼容性好，但在 无线传感器网络中，却带来了灵活性差、效率低等问题【2 2 1 。因此可以引入跨层优 化协议，在能量受限的情况下，满足应用的高吞吐量、低延迟等要求【4 8 】。在跨层 设计中，需要考虑网络中各层协议的相互联系，如协议的自适应性就要求各层相 互协作来完成。网络中的各种变化时间跨度各不相同【3 3 】，这就需要在不同的层自 适应地处理与之相应时间跨度的网络变化。对于网络的能耗问题，也需要各层统 一考虑。如在物理层降低信息传输速率可以降低能耗，但会对上层应用产生影响： 在一些应用场景中，最优的路由方式也有可能因为很快耗尽某些节点的能量而不 能被采用【4 剐。因此，在跨层协议的设计中，需要在能量、应用需求的约束下，对 各层进行统一的优化【2 2 j 【4 引。 1 2 无线传感器网络中的标识分配机制 1 2 1 标识分配机制的研究意义 由于全局地址在通信中的能耗负载较大，因此在无线传感器网络中并不采用 传统的t c p i p 协议框架对每个传感器节点分配全局唯一的地址标识1 25 | 。而且由于 传统的i p 路由和a dh o c 网络中现有的路由协议也不完全适用于传感器网络，因 此，研究人员提出了采用诸如定向扩散( d i r e c t e dd i 蜀m s i o np a r a d i g m ) 4 6 】等基于查询 的路由机制来代替传统网络中的路由机制进行路由。在这类应用中有一个基本假 设，就是每个传感器节点都使用局部唯一的地址标识1 4 6 】【50 1 。因此在无线传感器 网络中，高效的地址标识分配算法是提高节点通信效率的重要基础【5 1 1 。 一直以来，能量利用率都是影响传感器网络生命期的一个关键因素。与处理 和传感过程相比，通信过程消耗了传感器节点的绝大部分能量【2 4 1 。而相对于通过 数据融合技术降低数据载荷而言，数据传输中节点标识的能耗开销显得比较突出 【5 2 1 。因此，在无线传感器网络中，设计和实现高效的地址标识分配算法、研究如 何减少节点标识及其分配过程中的能量消耗有着十分重要的意义： 4 第一章绪论 ( 1 ) 由于传感器节点一般采用电池供电，而电池容量有限，因此节省能量是 传感器网络设计中的重要目标【2 2 】。与处理和传感过程相比，通信过程消耗了节点 的绝大部分能量【2 4 1 。而作为在通信过程中区分传感器节点的节点标识，是许多其 它算法实现的基础条件，在通信过程中的能量消耗显得比较突出【5 2 1 。因此，在保 证节点可区分的情况下，尽量减少标识能量消耗，对于节省网络能耗、延长传感 器网络的生存时间而言，具有十分重要的意义。 ( 2 ) 传感器节点在地址标识分配过程中相互影响、彼此冲突，地址分配算法 需要在地址冲突率、冲突处理所引起的额外开销等各方面进行权衡，才能在满足 节点地址互不冲突的前提下取得高效合理的地址分配结果。这些特性与其他对等 网络中的分布式资源分配算法相近【5 3 】【5 4 】。因此，若将标识看作资源，将传感器 节点看作是资源的竞争者，则高效的标识分配算法思想同样可以用于解决网络中 其它的分布式资源竞争问题【5 5 】。 ( 3 ) 另外，基于传感器网络跨层设计的思想【4 引，对于标识分配的问题，也可 以针对各层统一考虑。例如，在进行传感器节点标识分配的时候，考虑路由协议 对标识分配的影响，使得在有效的标识分配基础之上，可以设计更加高效的路由 算法。同时可以将一些路径信息与节点标识相结合，使得根据节点标识可以选择 合适的路径将信息发送到收集节点，以提高数据传输的效率。 1 2 2 传感器网络标识分配机制的技术难点 ( 1 ) 节点间的标识选择相互影响 在传感器网络的一些应用场景中，传感器节点规模较大，因此集中式的标识 分配算法的能耗负载较重【2 2 】。而在传感器网络的分布式标识分配算法中，存在着 节点间对标识的选择相互影响的情况，如果处理不好，容易造成节点的标识冲突 问题在整个网络中蔓延，有可能导致传感器网络一直处于节点标识冲突和反复调 整冲突标识的情况。 如图1 2 所示，传感器节点c 和节点e 是彼此两跳范围外的邻居节点，因此 可以基于地址空间复用的思想【5 6 】复用地址y 。同理，节点d 、f 可以复用地址z 。 而节点a 由于是b 的一跳范围内的邻居节点，因此不能使用相同的地址，否则 将发生地址冲突。如图所示，当传感器节点a 已选择地址x 后，节点b 若再选 择x 则会因与节点a 选择相同地址而产生冲突。这时节点b 需要调整自己的地 址选择策略，为了避免与节点a 发生冲突而选择x 以外的节点地址。但节点b 对地址的重新选择仍有可能导致与其邻居节点的地址冲突。如图所示，若节点b 选择地址y ，则虽然与节点a 不再产生冲突，但却仍可能与其邻居节点e 选取 相同的地址。如果分配机制选择让节点e 重新调整地址以避免与节点b 的地址 第一章绪论 冲突，则仍有可能使其与节点e 的其它邻居节点选择相同地址( 如，节点e 选择 地址z ) 。最坏情况下，有可能反复出现这种地址冲突和调整的情况，从而导致 不必要的节点地址调整消耗。 所以设计地址标识分配算法的一个技术难点是如何在节点分布式选择的前 提下，使传感器网络节点通过尽量少的地址调整而达到彼此地址互不冲突的平衡 状态。 图1 2 传感器节点地址分配冲突 ( 2 )如何降低标识分配过程中的通信消耗 传感器节点在地址标识分配过程中为了避免地址冲突，需要获取冲突域内节 点的地址信息。因此，目前许多地址分配算法在分配地址时存在着大量的通信， 增加了分配过程中的能量消耗【5 0 1 【5 2 】。 此外，不同的初始化地址选取和地址冲突处理方式也对通信能耗有较大影 响。这是因为，初始化地址选择策略决定了节点初始地址的冲突概率。如在c s c h u 唱e r s 等人的研究1 5 2 儿5 6 】中，节点都是随机地选取初始节点地址，因此其冲突率 随着网络规模和节点密度的增加而有明显增大。这样，当冲突率变高时，节点间 需要协同调整地址的次数就比较多，从而增加了在此过程中所引起的通信开销。 而当进行冲突处理时，如果反复出现地址调整的现象，也会增加处理过程中的能 量消耗。因此，在进行地址分配时，应根据传感器网络的应用特点，选择合适的 初始地址分配和节点地址冲突处理方式，减少分配过程中的通信消耗。 ( 3 )需要考虑网络规模、节点密度和节点地址长度等多个因素对分配算法 能耗的影响 在传感器网络的节点地址分配中，不同的网络规模和节点密度意味着节点冲 突域内邻居数的不同，为了降低节点能耗、避免节点与其邻近节点发生地址冲突， 节点所分配的地址长度应随着不同的网络规模和节点密度而有所变化p 卜5 9 】。此 外，各种地址分配方式具有不同的地址冲突概率，当冲突发生时所采取的处理方 式也各不相同。因此，需要针对这些因素对地址分配算法能耗的影响进行分析， 设计出高效的传感器网络节点地址分配算法。所以，在地址分配算法的设计和实 6 第一章绪论 现过程中，需要根据具体应用场景的特点，基于不同的节点规模、地址冲突处理 技术和可变地址长度等因素对地址分配算法能耗的影响，研究如何实现高效的地 址分配算法。 1 3 本文研究内容和研究思路 相对于通过数据融合技术降低数据载荷而言，数据传输中节点标识的能耗开 销显得比较突出【5 2 】。因此，在无线传感器网络中，设计和实现高效的地址标识分 配算法、研究如何减少节点标识及其分配过程中的能量消耗对于降低节点能耗、 延长传感器网络的生命期有着十分重要的意义。 目前，传感器网络中有很多的标识分配机制研究的是如何针对传感器节点进 行m a c 地址分配【5 0 1 【5 l 】【5 6 1 。这是因为利用m a c 地址除了可以完成标识分配区分 节点的功能之外，对于m a c 地址的有效设计还直接关系到传感器节点发送接收 消息的效率。而在传感器网络中，相较于节点的数据处理过程，数据的传送才是 能量消耗的关键。研究表明，传送1 b i t 的数据相当于执行1 0 0 1 0 0 0 条指令【6 0 1 。 因此，在m a c 地址的分配中，研究如何合理有效地减少m a c 地址长度以及在 地址分配过程中的能量消耗，具有十分重要的意义【5 2 】【5 6 1 。基于上述原因，本文 主要针对传感器节点m a c 地址分配进行标识分配机制的研究。 在传感器网络的节点地址分配中，不同的节点规模、地址冲突处理技术和可 变地址长度等因素对地址分配算法能耗有较大的影响【5 2 】【5 6 】【57 1 。因此，需要针对 这些因素对地址分配算法能耗的影响进行分析，设计出高效的传感器网络节点地 址分配算法。 本文基于不同的节点规模、地址冲突处理技术和可变地址长度等因素对地址 分配算法能耗的影响，研究如何实现高效的地址分配算法。我们将研究如下几个 问题： ( 1 ) 如何降低地址分配过程中的通信能耗 当前，基于地址空间复用技术【5 6 】的m a c 地址分配算法在分配过程中为了避 免产生冲突，仍需进行大量的通信，增加了节点的能量消耗。针对这个问题，提 出一种基于静态博弈模型【6 l 】的m a c 地址分配算法s ( m a ca d d r e s s a s s i g n m e n tb a s e do ns t a _ t i cg 锄em o d e l ) 。 m a a s 在采用地址复用技术的基础上，引入博弈模型【6 2 j 来解决m a c 地址分 配问题。m a a s 将每个传感器节点看作博弈模型中的一个决策者，每个决策者 的利益就是分配到与其两跳范围内邻居不产生冲突的m a c 地址。模型的平衡状 态即是指每个决策者的利益都得到满足，各节点分配到局部唯一的m a c 地址。 7 第一章绪论 因此，m a a s 算法可通过使博弈模型达到纳什平衡【6 3 】来解决传感器网络中的 m a c 地址分配问题。在进行地址分配时，利用博弈模型中每个决策者根据其邻 居节点信息可独立地进行决策的特性，m a a s 避免节点间发送大量的交互信息， 降低了地址分配算法的通信消耗。最后，通过仿真实验模拟验证其性能。 ( 2 ) 考虑节点数据传输频率对地址分配的影响 在传感器网络的一些应用场景中【2 2 1 ，存在着某些节点( 如簇头节点) ，其参 与数据传输的频率要大于一般节点，因此它们的能耗也较一般节点的要大【l4 1 。本 文称这些节点为传输频繁节点，而将一般节点称为非传输频繁节点。可以看出， 将同样长度的m a c 地址分配给传输频繁节点所引起的能量消耗，要大于分配给 非传输频繁节点所引起的能量消耗。因此，在地址分配过程中应将地址长度较小 的m a c 地址分配给传输频繁节点，从而达到合理地分配地址资源、节省节点能 量、延长网络生命期的目的。 针对传感器网络中m a c 地址分配未考虑节点传输频率从而增加了传输能耗 的问题，基于合作博弈模型【6 驯，提出一种适用于传感器网络的m a c 地址分配算 法c m a a ( c 0 0 p e r a t i v em a c a d d r e s sa s s i g 衄e n t ) 。c m a a 将数据传输频繁节 点与其数据传输频率较低的邻居节点组成联盟( c o a l i t i o n ) 5j 进行地址分配。节点 的s h a p l e y 值1 6 6 j 与其数据传输频率成正比，从而提高了传输频繁节点在联盟内部 的利益比率，使其所分配到的地址长度小于其它节点，节省数据传输中的能量消 耗。最后，通过仿真实验验证算法的性能。 ( 3 ) 在地址分配中，除了节点个体利益，还应考虑网络的共同效益 在一些应用场景中，无线传感器网络一般由汇聚节点( s i n kn o d e ) 和普通节点 组成【7 】【2 2 1 。汇聚节点负责将收集到的监测区域内的信息发送给观察者，完成监测 任务。普通节点负责收集布置区域内监测对象的信息，并将该信息发送到汇聚节 点。在这样的应用场景中，靠近汇聚点的传感器节点，由于其转发信息较多，它 的能量负载也要比一般节点的负载大。所以越靠近汇聚点的节点，其能量消耗越 快 1 4 】。因此容易造成这些节点过早失效，使得汇聚节点无法与外围节点通讯导致 网络性能下降【l4 1 。而外围节点由于转发的载荷较少，所以剩余能量较多，从而导 致了传感器网络节点的能量消耗分布不均，网络利用率较低的情况1 7 儿1 4 】。因此， 在进行m a c 地址分配时，应从网络整体出发，充分考虑传感器网络应用场景的 特点，根据节点在数据传输过程中能量消耗的情况，对其进行地址分配，从而达 到节省节点能耗，延长网络生命期的目的。 针对上述问题，提出一种能量有效的m a c 地址分配算法一一 e m a a ( e n e r g y e m c i e n tm a ca d d r e s sa s s i g m e n t ) 。在地址分配模型中，e m a a 将所有节点的共同利益看作传感器网络的整体利益，并引入社会福利函数【67 j 来解 第一章绪论 决传感器网络中的m a c 地址分配问题。眦a 将每个传感器节点看作是福利经 济学【6 8 】中的一个个体，节点的效益函数看作是个人福利函数，并定义传感器网络 的整体效益函数为社会福利函数。算法将节点能量消耗作为个人福利对社会福利 函数影响的权值，这样，当社会福利函数得到求解时，地址分配模型也就取得能 量有效的分配结果。因此，通过对社会福利函数的求解，可以使得整个传感器网 络的地址分配更加合理，从而达到降低能量消耗、延长网络生命期的目的。 ( 4 ) 分析节点规模、地址冲突处理技术等因素对节点地址分配能耗的影响 目前，传感器网络中的地址分配算法在避免地址冲突的同时，通过采取地址 复用、m a c 地址长度可变等技术来降低m a c 地址在传输中的能耗，但这些方 法并没有针对地址分配过程中影响能量消耗的因素进行评估。因此为了比较分析 不同分配算法的性能表现，需要基于传感器节点工作能耗分布特点和数据传输能 耗模型【6 9 】【7 0 】，建立传感器网络m a c 地址分配能量评估模型，对影响地址分配算 法能耗的因素进行分析评估。 基于传感器节点工作能耗分布特点和数据传输能耗模型7 0 1 ，本文建立传感器 网络m a c 地址分配能量评估模型。模型对不同地址分配方法和地址冲突处理方 式下的网络和节点能耗进行理论计算，并分析节点密度、地址冲突率和地址长度 等因素对节点能耗和网络运行的影响。通过理论计算，推导出不同地址分配方法 和地址冲突处理方式下无线传感器网络节点m a c 地址的能量消耗公式，根据能 耗公式对不同地址分配算法的能耗进行评估，分析节点规模、地址冲突处理技术 和可变地址长度等因素对地址分配能耗的影响，并通过模拟实验验证理论分析结 果。 1 4 本文的组织结构 本文共分七章，各章节的内容安排如下： 第一章是绪论。首先介绍传感器网络的体系结构、网络特点和节能技术。然 后介绍传感器网络中标识分配机制的研究意义和技术难点。最后给出本论文的研 究目的、研究内容和全文的组织结构。 第二章介绍无线传感器网络中节点标识分配机制的研究现状；随后简要介绍 博弈模型和社会福利函数的基本概念，最后介绍地址分配算法的能量评估模型。 第三章首先介绍地址复用技术，然后给出基于静态博弈模型的地址分配算法 的具体设计细节，包括网络模型和假设条件、地址资源计算和冲突处理以及算法 描述。接着给出算法的性能分析，然后通过模拟实验对地址分配算法进行了性能 比较。 第四章首先对传感器网络中的数据传输机制和能耗特点进行分析，然后介绍 第一章绪论 基于合作博弈的地址分配模型，接下来给出基于模型的地址分配算法的具体设计 细节，包括网络模型和假设条件、算法思想和算法描述。接着给出算法的性能分 析，然后通过模拟实验对算法进行了性能比较。 第五章首先介绍关于社会福利函数的基本概念，然后给出基于福利函数的地 址分配算法的具体设计细节，包括网络模型和假设条件、算法思想以及算法描述。 接着给出算法的性能分析，然后通过模拟实验对算法进行性能比较。 第六章基于传感器节点工作能耗分布特点和数据传输能耗模型给出地址分 配算法的能量评估模型，并对影响能耗的因素进行分析。通过理论计算，推导出 不同地址分配方法和地址冲突处理方式下无线传感器网络节点m a c 地址的能量 消耗公式，并根据能耗公式对不同地址分配算法的能耗进行评估，分析节点规模、 地址冲突处理技术和可变地址长度等因素对地址分配能耗的影响，然后给出模拟 实验验证理论分析结果。 第七章是结束语，总结本文的主要工作、贡献和创新点，并展望了下一步的 研究工作。 l o 第二章传感器网络标识分配机制的相关：j ：作 第二章传感器网络标识分配机制的相关工作 节能一直以来都是衡量传感器网络的重要指标。与处理和传感过程相比，通 信过程消耗了传感器节点的绝大部分能量，而其中节点地址的能耗开销显得比较 突出。因此，研究如何减少地址标识及其分配过程中的能量消耗，对于降低节点 能耗、延长网络生命期而言，具有十分重要的意义。在传感器网络的地址分配过 程中，为了避免节点地址冲突、降低标识能耗，传感器节点所分配的地址标识长 度应随着不同的网络规模和节点密度而有所变化。此外，各种地址分配方式具有 不同的地址冲突概率，当冲突发生时所采取的处理方式也各不相同。因此，需要 针对这些因素对地址分配算法能耗的影响进行分析，从而设计出高效的传感器网 络地址标识分配机制。 本章首先介绍传感器网络地址分配算法的研究意义，随后介绍相关的研究工 作，并讨论地址标识分配的技术难点以及引入博弈模型的可行性和优势，接下来 介绍地址分配算法的能量评估模型，最后是本章小结。 2 1 研究现状 目前，随着移动自组网络研究的不断深入，针对a dh o c 等网络提出了许多 的地址分配策略【7 1 7 3 1 。但由于网络自身的特点，这些方法并不完全适用于传感器 网络，因此需要针对传感器网络的应用需求和限制条件，设计适用于传感器节点 的高效的地址分配算法。当前，针对传感器网络的地址分配算法已经有了许多研 究成果，本文基于这些方法所采用技术的不同特点，对它们进行了如下分类并加 以介绍： ( 1 ) 全局地址分配 e l m o u s t a p h a 等人提出了一种分布式的全局唯一标识分配算法【7 4 】，算法将所 有传感器节点组织成树型结构，利用该结构计算网络规模等信息，然后通过对相 关信息的计算，再对每个传感器节点分配全局唯一的地址标识。算法主要分为三 个阶段： a ) 第一阶段：通过建立树型结构，算法为每个节点分配一个暂时的长 地址标识。其中，孩子节点的标识由其父亲节点分配并保证不与其它孩子 节点冲突，并且为了保证节点间的标识互不冲突，孩子节点的临时标识要 长于父亲节点。 b ) 第二阶段：基于之前分配的临时标识，各传感器节点根据树型结构计算 第二章传感器网络标识分配机制的相关工作 其所在子树的大小，并将此信息发送给其父亲节点。这样，当子树的信息 由叶子节点发送到根节点后，根节点就可以根据该信息对传感器网络中的 所有节点分配一个全局唯一的地址标识。 c ) 第三阶段：当最终的地址标识计算好后，由父亲节点分配发送给其孩子 节点，这里的最终标识是全局统一长度的。 从上面的分析可以看出，该全局唯一标识分配算法通过建立节点的树型结构计算 网络规模信息，并基于该信息进行地址标识的分配，保证了节点间较低的冲突概 率。但同时由于在树型结构的建立以及节点临时标识和最终地址标识的分配过程 中存在大量的通信，因此该算法具有较大的通信消耗。 ( 2 ) 基于层次型结构的地址分配 无线传感器网络中的一种常见的节点组织结构形式，就是基于分簇 ( c l u s t e r - b a s e d ) 0 7 5 j 的网络结构。目前，针对这种网络组织结构的特点，提出了一些 层次型的地址分配算法： a ) a l i 等人基于分簇的传感器网络提出了一种分布式的标识分配算法【7 6 】。 该算法保证一个簇内的节点具有互不相同的标识，簇与簇之间的通信由簇 头负责，并且保证簇头标识互不相同。这样，非成员的一跳和两跳范围内 的邻居节点就具有不同的地址标识。在算法中，整个传感器网络被划分为 多个层次，层次的多少与网络节点规模相关。簇内节点的局部标识与所在 簇头节点标识相加，形成簇间通信的节点标识。因此，网络的全局标识可 以由簇内局部标识加上其所在的所有层次头节点的标识形成。但该算法所 节点规模影响较大，当节点数较大、网络层次较多时，节点标识的长度较 大，并且该算法只适用于基于簇结构的路由方式。 b ) h k j u n g 等人【”j 提出了一种s t r u c t m e - b a s e d 的标识分配算法。算法基于 层次型结构进行地址标识分配，主要分为p a r e n tg r o u p i n g 和c h i l d r e n g r o u p i n g 两个阶段。在p a r e n tg r o u p i n g 阶段，汇聚节点或头节点收集一跳 范围内邻居节点的信息形成一个组，并给组内的节点顺序地分配一个组内 唯一的标识。然后重复此过程，使其一跳邻居节点继续收集两跳范围内的 邻居节点信息并分配节点标识。在c 1 1 i l d r e ng r o u p i n g 阶段，汇聚节点或头 节点，通过指定已在其组内的节点成为子组的汇集节点来扩展构造新的组， 并完成节点信息收集和全局标识的分配。最后，由各头节点向汇集节点报 告标识分配的结果。 c ) 在无线传感器网络中，最优的簇头节点数目应为所有传感器节点数目的 6 【7 8 】中。基于这个结论，m a l i 等人【7 9 】提出了一种节点地址标识的分配算 法。算法认为最优的簇成员数应为1 6 【7 引，因此，算法以4 b i t 为单位对每个 第二章传感器网络标识分配机制的相关：工作 层次内的节点进行标识分配，层次号每加1 节点的标识长度就增加4 b i t 。当 簇内节点数多于1 6 时就以扩展2 b i t 层号的方式进行地址扩展。算法定义效 率为数据包中的数据载荷长度与整个数据包长度的比值，而该文献的实验 表明，其所提出算法的效率( 6 0 3 7 ) 比全局唯一地址分配算法的效率( 3 3 5 ) 有了较大提高。 d ) t h t r o n g 等人【8 0 】基于b r u i j ng r a p h 川提出了一种层次型的节点地址分 配算法。算法基于b r u i j ng r a p h 结构对网络进行分层并组织传感器节点，同 层内的节点标识长度相同，标识的长度随层次的增加而变大。利用b r u 硝n g r a p h 结构的特点，算法具有很好的容错性和可扩展性，并基于该结构实现 了一个简单的路由算法。但该算法在形成b m i j ng r a p h 结构时需要进行一定 量的通信，并且对于如何处理地理位置与逻辑结构的关系问题也没有进行 深入地讨论。 ( 3 ) 局部唯一地址分配 目前，利用地址空间复用思想的m a c 地址分配算法已经出现了一些相关的 研究成果： a ) s c h u r g e r s 等人【 】基于地址空间复用的思想，提出了一种分布式的传感器 节点m a c 地址分酉乙算法。假设在传感器网络中，节点b 、c 分别为节点a 的一跳和两跳范围内邻居节点，它们与节点a 都存在通信干扰，而节点a 与d 处于互不干扰的通信区域内。由于m a c 地址主要用于标识出数据帧 在每跳传输时的发送节点和接收节点，因此只要保证节点b 、c 与节点a 的m a c 地址：1t 砷突就可以进行数据帧的传送，两节点d 与节点a 由于处 于互不干扰的通信区域内，因此可以复用同一m a c 地址而不产生冲突，这 就是传感器网络中节点的m a c 地址复用的思想。该算法利用这种地址的空 间复用，对传感器节点分配局部唯一的m a c 地址，与分配全局唯一的地址 相比，降低了节点的地址能量开销。 b ) 基于地址空间复用，c s c h u r g e r s 等人1 8 2 】提出了一种主动式( p r o a c t i v e ) 的 冲突处理机制来避免地址冲突。当网络初始化建立时，传感器节点先随机 选择一个地址，并将该地址以1 0 秒的间隔，通过h e l l 0 消息周期性地发 送广播消息进行地址声明。所有传感器节点在其邻居节点表中记录h e l l o 消息的源地址，并因此获得其两跳范围内邻居节点的地址信息。如果一个 节点发现其邻居节点与自己的地址相同发生冲突，就通知该节点重新选择 地址。该算法通过主动式的消息发送避免了节点间的地址冲突，但在这个 过程中，节点发送的消息数较多，通信消耗较大。 c ) 与p r o a c t i v e 机制不同。h b ，z h o u 等人删提出了一种反应式( r e a c t i v e ) 的 第二章传感器网络标识分配机制的相关工作 冲突处理机制来避免节点的地址冲突。r e a c t i v e 机制并不是周期性的发送消 息检测是否有邻居节点与自己的地址发生冲突，而是直到进行数据传送通 信时，才处理地址冲突的情况。因此，与p r o a c t i v e 机制相比，r e a c t i v e 标 识分配机制减少了冲突处理过程中的通信消耗。但由于在初始化标识分配 时也是采用的随机标识分配的方式，因此r e a c t i v e 机制的通信开销会随着 节点规模的增加而有明显的增大。 综上可以看出，虽然地址空间复用降低了能耗开销，但冲突处理等因素对于标识 分配算法的能耗仍有很大影响。 ( 4 ) 基于划分虚拟区的地址分配 研究表明【2 矾，传感器节点的无线通信模块存在发送、接收、空闲和睡眠四种 状态，不同状态的能量消耗程度也有所不同。其中，无线通信模块在发送状态下 的能量消耗最大，空闲状态和接收状态下的能量消耗情况相近，略少于发送状态 的能耗，睡眠状态下的能量消耗最少。因此，无线传感器网络中的相关协议和算 法，应尽量减少网络在通信过程中的能量消耗，并且利用节点工作状态能耗程度 相差较大的特点，使传感器节点在网络正常运作下尽快进而睡眠状态，并关闭通 信模块，以达到提高能量利用率，降低节点能耗，延长网络生命期的目的【27 | 。基 于这种思想，y t i a n 等人【8 4 】提出了一种基于虚拟区划分的地址分配算法。该算法 将网络分布区域划分为一系列虚拟小区，并建立节点地理位置坐标与虚拟小区间 的映射关系，通过m a c 地址在不同虚拟小区处的空间复用达到减小节点m a c 地址长度的目的通过调整传感器节点的通信半径，算法能够在保证网络不失连 通性的同时降低m a c 地址大小。 需要说明的是，上述对传感器节点标识分配算法的分类并不是严格唯一的， 某些类别里面的方法可能会用到其它类型方法中所采用的技术。由此可以看出， 传感器节点地址分配算法的设计和实现需要考虑多方面因素对算法能耗的影响。 在地址分配过程中，需要根据不同的应用环境和特点，对所采取技术和方法的优 势和所引起的额外开销进行权衡分析，才能设计和实现高效的传感器网络节点地 址标识分配算法。 2 2 博弈模型 2 2 1 静态博弈模型的基本概念 博弈论( 包括非合作博弈与合作博弈论等) 【8 5 】，也称为对策论，是研究利益冲 突情况下决策分析的科学，是系统研究决策主体的行为发生直接相互作用情7 兄下 第二章传感器网络标识分配机制的相关 ：作 的决策以及这种决策均衡的理论。博弈论概念可以用于求解存在多个行为者的行 动相互依赖情况下的均衡问题。 在社会系统中，存在许多行为主体韵行动相互依赖的例子【8 6 i ，行为主体之间 的利益要么相互冲突，要么存在合作的潜力。每个行为者的利益相互冲突，各自 进行策略选择以最大化自己的利益；也可能其中的两个或多个行为者组成联盟， 共同参与博弈进行策略选择，与其他行为者竞争。在这里，联盟与外部行为者之 间和联盟内部都存在博弈关系，联盟成员要决声如何分配联盟利益。而非合作博 弈理论在研究行为者相互作用的均衡行为时，一般假设【87 j ：( 1 ) 行为主体是完全 理性的，以最大化自己的利益为目的；( 2 ) 行为者对于决策空间和效益函数等信 息有共同的理性知识；( 3 ) 行为者之间知道博弈的规则。 传感器网络中的标识分配问题具有如下一些特点【2 2 】【5 2 】【5 6 】f 5 7 】：首先，在能量 消耗方面，传感器网络的一个重要特点就是节点能量受限，因此在分配节点标识 时每个节点要求尽量缩短标识长度，避免通信中的能量消耗；其次，节点数目较 多分配全局标识或地址代价太大，因此采取局部可区分的地址分配方式：再次， 节点间的对标识或地址的选取是相互影响的，每个节点的决策选择都受到周围邻 居节点地址标识选择策略的影响，节点间存在着一个博弈的关系，而且由于传感 器网络的自组织特性，节点应分布式地进行标识分配以减少通信消耗。另外，由 于传感器网络中节点数目巨大，传感器节点生命期较短从而导致网络拓扑变化比 较频繁，因此节点标识分配应具有较好的可扩展性和适应性。 基于上面的特性，本文引入博弈模型【8 7 】来解决传感器网络中的标识分配问 题。首先，可以将每个传感器节点看作是博弈论中的决策者【87 。，而每个决策者的 利益就是分配到合理的地址标识；其次，每个决策者具有相同的策略集，即每个 传感器节点对于标识分配具有相同的公共信息：当引入的博弈模型取得纳什平衡 刚时，各节点的标识分配达到一个平衡状态，标识分配问题就得到了求解。 在博弈论中，参与人或决策者( p l a y e r ) 【8 8 】是博弈的主体，它是指博弈中做决 策的行为者，行动( a c t i o n ) 【8 8 】是参与人的决策变量。在静态博弈中，一个策略 ( s t r a t e g y ) 是【8 9 】参与人的一个给定的可能行动。平衡( e q u i l i b r i u m ) 【9 0 】是所有参与人 的最优策略组合，平衡结果( e q u i l i b r i u mo u t c o m e ) 1 9 是指所有参与人的最优行动 的组合。 对于一个有n 个参与人的博弈来说，甩5 ，表示参与入i 的一个特定策略，则 参与人i 的策略集合为s ；h ，记n 个参与人的纯策略组合( p u r es t r a t e g y p r o 丘l e ) 【8 7 】为s = ( s 。s 。5 。) ，简称为策略组合：除i 外的其他参与人的策略组 合记为j ，= ( 而，小t + ，) 。记包含n 个参与人的集合为= 1 ，2 ，2 ，每 个参与人i 有一个纯策略集【盯j 第二章传感器网络标识分配机制的相关j ：作 s = ， ，f - 1 ，2 棚 如果参与人数n 有限，并且策略集s ，& ，s 。均为有限集，则称该博弈为有限博 弈 8 7 】。 若在博