无线Ad Hoc网络Steiner树实现协议研究*

王 璐，李爱玲

(安阳工学院计算机科学与信息工程学院，河南安阳455000)

无线Ad hoc网络是一种具有无中心、自组织、多跳路由、动态拓扑特点的特殊无线移动网络。其出现是为了满足跳出基础设施支持的移动网络，在其信号覆盖范围外仍可通讯，所以其需要多跳的通信方式。Ad hoc网络中所有结点地位平等，无中心控制点，网络结点可以通过自身的报文转发功能向外传递数据信息，所以在功能上高于普通移动终端。当两个移动终端的通讯范围超出信号覆盖范围时，它们可以通过之间的其他终端分组转发通信数据。由于每个移动终端通信覆盖外围的限制，Ad hoc网络路由需要多个移动终端组成，数据信息需多次转发才可到达目的终端［1］，这是Ad hoc网络与其他移动网络最根本区别，也是多跳特性的根本所在［2］。

无线Ad hoc网络部署灵活、可靠性强、获取信息精度高的特点使其在军事侦察、交通运输、环境监测方面应用前景广阔。而由于其多跳的特性，拓扑结构随时可能动态变化，网络中有机协作各节点间的数据传输需要随时考虑通信、能量、有限计算等问题［3］，由此Steiner树的构造方法成为适应无线 Ad hoc网络能源有限，生命周期短的最切合方案。

Steiner树是总代价最小的分布树［4］，其形状随组中成员关系的改变而改变，同时，它使连接特定图中的特定组成员所需的链路数最少，这也是充分考虑到通信代价远远高于计算代价量级的原因［5］，尽量减少网络中转次数，利用数据聚合技术，减少数据传输所需要的中间环节以增强网络的可靠性。另一方面，减少移动终端节点的使用量，也会减少产生拥塞的风险，使网络相对更加稳定。但Steiner树缺少通用的解决方案［6］，而本文利用协议声明网络为无线Ad Hoc网络的最小Steiner树问题提供了一种新的解决方案。

1 协议设计宣告方式

宣告性语言出现之前，宣告式方法首先在无线传感器网络中使用。程序通过其应用系统提供的编程接口，利用SQL语言从无线传感器网络中抽取数据，其过程类似于数据库中数据的查询。节点发现［7］、Oos 路经维护［8］、路由发现、拓扑发现［9］等很多问题都可用宣告式方法实现。而在推导式的数据库查询Datalog［10］基础之上提出的描述路由协议的NDLog语言和和描述覆盖层网络协议的OverLog语言标志着宣告式网络程序设计语言的实现。其后出现的Netlog语言，针对无线网络环境中网络节点移动性强引起的网络节点失效、网络动态性强的特点进行了挖掘，能够更好的实现对网络的动态性效果的有效支持。三者作为宣告式网络程序设计语言的代表，均为推导式数据库查询语言Natalog的扩展，为网络协议的设计者提供高层次的编程抽象。

协议的开发设计过程，是通过低层程序设计语言来直接控制网络设备，往往涉及很多的技术细节，协议设计者往往不能将精力完全集中于协议本身的功能和特性上。宣告性语言相当于为网络协议设计者提供了一个好的原型系统，使设计者只需关注协议行为，无需关心实现细节。在此基础上开发出协议，在原型系统中试验，利用试验结果反馈来修改更进协议使其符合要求。其作用类似于网络协议开发的中间件，编写的网络程序不需顾及低层具体的物理实现，只需要关心高层描述，完成其网络行为需求即可，宣告性语言为网络协议设计者摆脱各类异构设备物理层细节的束缚提供了可能。

相比而言，OverLog在NDLog的基础上增加了网络数据状态(生存周期)的描述，可称之为数据的软状态，利用它来删除过期数据。若数据生存时间超过了其生存周期，那么将被删除;若数据在超出其生存周期前被节点重新利用，它的生存周期将被重置;这针对生活中的动态网络无疑是一大进步。然而无论是NDLog还是OverLog，都是需要启发式定义的，此方面Netlog更胜一筹，语言的定义实现了形式化，经过了充分的语法语义讨论，而且Netlog主要针对无线网络设计，特别是无线Ad Hoc网络，无线网络协议编程提供了强有力的工具。本文的协议实现也在Netlog语言基础之上。

2 算法描述

求最小 Steiner树是非常困难的，它属于 NP Complete问题［11］。但最小Steiner树具有重要的应用价值，它在交通运输的规划、输油管道和航空港的安排、通讯线路的布置和计算机的设计等等现代经济与科技、军事领域中的广泛应用［12］。本文声明最小Steiner树协议也是用来快速构造一棵近似最小的Steiner树。

针对网络中的各通信节点，我们通常会选定合适的节点使目的节点间的通信代价最小。其网络模型可对应成给定的网络无向连通图G，把权值作为节点传输的代价，那么生成树各边的权值总和即树的权最小的生成树，即为图G的最小生成树MST(Minimal Spanning Tree)，也即该网络最小代价的生成树。

设图G={V，E，C}，V为节点的非空有限集合E是V中可以直接通信的节点对集合，C是节点对间传输代价的集合，其中V，E均非空。节点集合V非空子集S被称为G的Steiner节点集合。对于给定网络的连通图G和Steiner节点集合S，T是G和S上的Steiner树，当且仅当S中的所有节点都在T上。G和S上的最小Steiner树是在所有Steiner树中各边的权值总和最小的树。

构造虚拟全联通网络G'={S，E，C}，对于S中任意两点，它们在G'中的传输代价是G中两点间的最小代价路径的代价和。

构造G'上的最小生成树T'。

将T'中的边对应的G中的路径上的所有边，标记为2。由标记为2的边及其对应定点组成的图记为G″。

构造G″上的最小生成树T″。

将T″叶子节点中的非Steiner节点移除。

每个节点独立运行声明Steiner树协议，构造Steiner节点间的虚拟全联通网络，在此网络上构造最小代价生成树;然后将此树的节点与边对应原网络的节点和边，继续构造最小代价生成树，将此树上的非Steiner节点的叶子节点删除，就近似得到了最小代价Steiner树。

由于协议代码较为复杂，现仅以权值更新部分协议代码为例解释，其有18条协议规定构成:

规定主要针对各节点的相邻节点列表和虚拟节点列表执行权值及序号的修改:

(1)权值为0的节点优先于权值为1的节点链接。

(2)无权值为0节点时，权值为1的节点优先级上升，并设为默认权值。

(3)针对用于链接的广播消息，接收点遍历其邻节点列表，权值为0的修改为2。

(4)针对用于链接的广播消息，遍历其接收点的下一个接收点状态，权值为0或者大于广播消息中给定权值时，将其权值也设定为2.

(5)表内权值与链接广播消息内权值相等时广播点ID小于本地ID地址，且下一链接点表内状态为0，也将其权值设定为2。

(6)广播点ID大于本地ID地址时，消息继续转发给状态为1的节点。

(7)若广播点为新节点，无序列号，广播消息直接转发给状态为1的邻节点。将广播消息内序列号指定为其序列号插入节点序列列表。

(8)广播消息内序号若大于原表内序号，则表内序号替换为广播消息序号。

3 仿真模拟

声明Steiner树协议是在网络上分布式构造近似最小Steiner树。此处使用WSNS(Wireless Net work Event-Driven Simulator)［13］作为模拟实验平台该实验平台具有精确的节点内部结构模拟和无线媒介模拟功能。随机在360×360的平面内分布15个节点，节点的通讯半径设为80。当两节点在通讯范围之内，则随机为其分配一个链接代价，同一链接的两个节点间链接代价相同。初始网络如图1所示。网络中每个节点独立运行声明Steiner树协议，Steiner节点去构造Steiner节点间的虚拟全联通网络，在此网络上构造最小代价生成树;然后将此树的节点与边对应原网络的节点和边，继续构造最小代价生成树，将此树上的非Steiner节点的叶子节点删除，就近似得到了最小代价Steiner树，如图2所示。实验结果显示，声明Steiner协议能够快速构造一棵近似最小Steiner树。

图1 初始网络

图2 仿真平台实现构造近似Steiner树

4 小结

实验结果表明，本方法是可以快速的构造一棵近似最小Steiner树的。此原型系统符合网络协议设计需求，使得设计者可以忽略底层技术细节仅关注协议行为。同时也为无线移动网络中资源的选择利用提供了一种新的可尝试性的方法。

［1］王庆文，史浩山，程伟，等.一种基于跨层设计的Ad hoc网络按需路由协议［J］.传感技术学报，2009，22(12):1780-1783.

［2］谭学治，吴少川，贾世楼.移动Ad hoc网络分布式多跳认证授权方案［J］.电子器件，2005，28(3):672-677.

［3］李宏，于宏毅，刘婀娜.一种基于树的无线传感器网络数据收集方法［J］.电子与信息学报，2007，29(7):1633-1637.

［4］王建平，贾东耀，周贤伟.基于虚拟Steiner树的无线传感器网络组播随机路由协议研究［J］.传感技术学报，2008，21(11)1896-1899.

［5］Pottie G，Kaiser W.Wireless Sensor Networks［J］.Communications of the ACM，2000，5，43(5):51-58.

［6］闫中江，沈中，常义林，等.一种修复网络拓扑的Steiner树移动控制算法［J］.西安交通大学学报，2011，45(2):39-43.

［7］Alonso G，Kranakis E，Sawchuk C，et al.Probabilistic Protocols for Node Discovery in Ad Hoe Multi-Channel Broadcast Networks［C］//ADHOC-Now.2003:104-115.

［8］Bejerano Y，Breitbart Y，Orda A，et al.Algorithms for Computing QoS Paths with Restoration［J］.IEEE/ACM Trans.Netw，2005，13(3):648-661.

［9］Bejerano Y，Breitbart Y，Garofalakis M，et al.Physical Topology Discovery for Large Multi-Subnet Networks［C］∥Proc.IEEE Info com.2003:342-352.

［10］Ramakrishnan R，Ullman J D.A Survey of Deductive Database Sys tems［J］.J.Log.Program，1995，23(2):125-149.

［11］丁雪枫，马良，丁雪松.基于模拟植物生长算法的构造通讯网络Steiner最优树方法［J］.上海理工大学学报，2010，32(1):88-91.

［12］范容，潘雪增，傅建庆，等.基于Steiner树的层次型无线传感器网络安全组播协议［J］.传感技术学报，2011，24(4):601-608.

［13］Guillaume Chelius.Worldsens:A Fast and Accurate Developmen Framework for Sensor Network Applications［EB/OL］.http://ws net.gfo-ge.inria.fr/.