第２６卷第５期２００９年５月
计算机应用研究
Ａｐｐ“ｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒ８
Ｖ０１．２６Ｎｏ．５
Ｍａｖ２００９
一种新的无线传感器网络拓扑发现算法
申军，齐望东
（解放军理工大学指挥自动化学院计算机系，南京２１０００７）
摘要：ＧＢＧＤ是一种面向攻击的隐蔽性较强的拓扑发现算法，通过分析发现，该算法对实际网络进行了过于理想化的假设，导致无法在实际中应用。在ＧＢＧＤ算法工作模式的基础上，对实际网络提出了合理假设，设计实现了一种新的网络拓扑发现算法，通过对报文向基站汇聚过程中每一跳转发时延进行分析得出节点在路由树中的层次关系，进而推算出网络的拓扑。仿真实验结果表明，该算法能准确推断出网络的拓扑，并在报文存在丢失较多的情况下具有较好的鲁棒性。由Ｍｉｃａ２节点组成的原型系统实验结果表明，该算法能够较好地应用于实际网络。
关键词：无线传感器网络；拓扑发现；基站；ＧＢＧＤ中图分类号：７ｎ）３９３
文献标志码：Ａ
文章编号：１００ｌ一３６９５（２００９）０５—１８６８－０３
Ｔｏｐｏｌｏｇ）ｒｄｉｓｃｏＶｅｒｙａｌｇｏｒｉｔｈｍｆｏｒｗｉｒｅｌｅｓｓ
ＳＨＥＮ
．
ｓｅｎｓｏｒ
ｎｅｔｗｏｒｋｓ
Ｊｕｎ，Ｑ１ｗ蚰ｇ－ｄｏｎｇ
（巩Ｐ１．旷ｃｏ唧蹴ｒ，触拓ｌ如矿ｃｏＭ，Ⅻ村Ａｎ幻，删洳，ＰＬＡ‰妇Ｈ妙矿ｓｃ诂ｒⅫ＆扎矾，ｌＤ如夥．肫硒增２ｌ０００ｒ７，蕊ｆＭ）
Ａｂ吼ｒａｃｔ：ＧＢＧＤｉｓｒｉｔｈｍｃｏｕｌｄ
ｎｏｔ
ａｎ
ａｔｔａｃｋｏｒｉｅｎｔｅｄｔｏｐｏｌｏｇｙｄｉｓｃｏｖｅｒｙａｌｇｏｒｉｔｈｍｗｉｔｈｈｉｇｈ
ｃｏＴｌｆｉｄｅｎｔｉａｌｉｔｙ．Ｈｏｗｅｖｅｒ，ｆｏｕｎｄ
ｐａｐｅｒ
ｔｈｔｔｈｉｓａ１９０－
ｔｏｐｏｌｏｇ）ｒｄｉｓ．
ｂｅａｐｐｌｉｅｄｉｎａｃｔｕａｌｎｅｔｗｏｒｋｄｕｅｔｏｉｔｓ
ｏｎ
ｕｎｒｅａｌｉｓｔｉｃ硒ｓｕｍｐｔｉｏｎ８
ｏｆｒｅａｌｓｉｔｕａｔｉｏｎｓ．Ｔｈｉｓ
ｐｍｐｏｓｅｄｒｅａｓｏｎａｂｌｅ
ａ
硒ｓｕｍｐＩｉｏｎｓｏｆａｃｔｕａｌｎｅｍｏｒｋｂａｓｅｄ
ｃｏｖｅｒｙ
ｔｈｅｗｏｒｋｐａｔｔｅｍｏｆＧＢＧＤ，ｆｎｈｅ瑚ｏｒｅ，ｄ船ｉ印ｅｄａｎｄｉｍｐｌｅｍｅｎｔｅｄ
ｎｅｗ
ａｌｇｏｒｉｔｈｍ．Ｂｙａｎａｌｙｚｉｎｇｔｈｅｆｏｎｖａｒｄｉｎｇｄｅｌａｙｏｆｅｖｅｒｙｈｏｐｄｕｒｉｎｇｍｅｓｓａｇｅｃｏｎｖｅｒｇｅｎｃｅｐｒｏｃｅｓｓｆｍｍｎｏｄｅｓｔｏｂａｓｅｓｔａ—
ｔｉｏｎ，ｉｔｃｏｕｌｄｇｅｔｔｈｅｌｅｖｅｌｓｏｆｔｈｅｎｏｄｅｓｉｎｔ量ｌｅｔｏｐｏｌｏｇｙ眦ｅｈ口ｍｗｈｉｃｈｃｏｕｌｄｆｉｎａｌｌｙｄｅｄｕｃｅｔｈｅｔｏｐｏｌｏｇ）ｒｏｆｔ｝ｌｅｓｕｎｒｅｉｌｌａｎｃｅ
舱ｔｗ０Ａ．Ａｎａｌｙｓｉｓａｎｄｓｉｍｕｌａｔｉｏｎｓｓｈｏｗ山ａｔ，ｔｈｉｓ
ｇｅｓｌｏＢｔｄｕｒｉＩｌｇｔｒａｎｓｒｒＩｉｓｓｉｏｎ．Ｋｅｙ
ａ如ｒｉｔｈｍｃ粕ｇｅｔｍｅｔｏｐｏｌｏ籽ｏｆｔｈｅｎｅｔｗｏｒｋｅ）疆Ｉｃｔｌｙ
ｅｖｅｎ
ｗｈｅｎ
ｍ粕ｙｍｅｓ鼢・
ｗｏｒｄｓ：ＷＳＮｓ（试ｒｅｌｅ８ｓ驼ｎｓｏｒｎｅｔｗｏｒｋ）；ｔ叩０１０９ｙｄｉｓｃｏｖｅｒｙ；ｂａ∞８ｔａｔｉｏｎ；ＧＢＧＤ
０引言
无线传感器网络（ｗｓＮｓ）是由大量随机分布的，集计算、通信、传感器技术三为一体的廉价微型节点组成的分布式系统。它集合了传感器技术、嵌入式计算、分布式信息处理技术和无线通信技术，能够协作地实时感知环境信息。
无线传感器网络节点廉价、微型的特点使其在军事侦察领域中有着重要的应用前景，已经出现的应用系统如狙击手定位系统、ＶｉｇｉｌＮｅｔ无线传感器侦察网络系统、ＡⅡｎｅ
ｉｎｔｌｌｅ
１
无线传感器网络的拓扑发现算法
根据面向的应用不同，无线传感器网络的拓扑发现算法可
分为以下两种：
ａ）面向网络管理的拓扑发现算法¨。Ｊ。它在于发现网络中节点的活动性、节点间的链路状态、节点的剩余能量等信息，进而为最大限度地延长整个网络系统的寿命提供条件。
ｂ）面向攻击的拓扑发现算法ＨｊＪ。利用无线传感器网络应用中数据整体上向基站汇总的趋势特征为基础，采用被动监
ｓａｎｄ无
听目标刚络通信报文的方式来分析目标网络的拓扑。
ＴｒａｍｃａｎａｌｙｓｉｓＨｏ中，攻击者通过监听通信流量和数据转
线传感器侦察网络等。如何发现并对敌方布设的侦察网络进行攻击在现实中具有重大的意义。目前针对无线传感器网络的攻击方法有很多种，如虚假路由攻击、汇聚节点攻击、虫洞攻击等。不管是何种攻击方式，攻击对象与攻击的效果是密切相关的。对基站及数据转发的中间节点的攻击显然比对目标网络边缘节点的攻击更加有效。
本文以发现敌方传感器网络的拓扑为目的，在目标网络布设区域布置多个监听节点形成监听网络对目标网络的通信过程进行监听，通过对报文向基站发送过程中转发时的时延来完成对目标网络拓扑的分析。
收稿日期：２００８．０８．１５；修回日期：２００８．１０．１７
发路径来推断出目标网络的拓扑信息。越接近基站，需要转发的报文越多，因此网络的通信流量越大，如图ｌ所示。攻击者根据报文多跳地向基站汇聚的特点，沿着数据汇聚的方向追踪基站的位置，但由于无线传感器网络往往数量较大，从数据的源节点到基站的过程中转发的次数较多，采用移动追踪报文的转发路径是不切实际的；另一方面，一个攻击者只能获得网络的局部信息，仅仅依靠这些信息来推断网络的拓扑是不够的。文献［５］中提出的ＧＢＧＤ算法通过布设大量监听节点协作地对目标网络进行监听，如图２所示。在目标网络的覆盖区域内
基金项目：军内预研基金资助项目（４ｌｌｏｌ０４０４０２）
作者简介：审军（１９８３．）。男，贵州惠水人，硕士研究生，主要研究方向为无线传感器网络等（ａｂＩｌ—ｓｊｃｏｒ＠ｙａｌｌ∞．咖．ｃｎ）；齐望东（１９６８．），男，教
授，博导，主要研究方向为无线传感网络、计算机网络等．
万方数据
第５期申军，等：一种新的无线传感器网络拓扑发现算法
布设一定数量的监听节点组成监听网络。通过较多的监听节点被动地监听目标区域的通信情况，依据路由建立过程中路由建立报文转发及数据汇报过程中报文｛胥路由树向基站汇聚的特点，集中地对目标网络进行分析。这种方式能够较大范围地对目标网络的通信情况进行监听，因而能更好地对目标网络的拓扑进行刻画。
图ｌ
ＷＳＮｓ通信流量示意图
图２隐蔽监听ＷＳＮ不意图
ＧＢＧＤ算法无法直接应用于实际中，因为ＧＢＧＤ算法的前提假设无法在实际中成立。这些假设主要有：
ａ）通信报文中携带有发送节点的地址。对无线网络扩散树路由协议及数据汇报过程进行分析发现，这两种通信过程中的消息报头中并不携带发送节点地址。
ｂ）通信信道没有错误发生，即所有的监听记录报文均能可靠地进行传送。在无线传感器网络开放无线通信环境下，发生报文错误与报文丢失是很常见的。因此ＧＢＧＤ算法中依赖于能监听到目标嗍络的所有通信报文的假设无法成立。
ｃ）监听节点能够接收到监听范围内目标网络节点的所有通信报文。
本文提出一种新的基于报文发送时间分析的网络拓扑发现算法，该算法利用报文向基站转发的时间先后关系推断报文到达基站的路径。由于不依赖于ＧＢＧＤ算法的假设，它能应用于现实环境中。
２拓扑发现算法描述
２．１
无线传感器网络报文发送模式
无线传感器网络工作时报文的传递模式主要有两种：ａ）洪泛（ｎ００ｄｉｌｌｇ）的报文传递模式。在这种模式中，基站
向其邻居节点广播某个报文；收到这个报文的节点将报文以同样的方式广播出去，一直到网络中所有的节点都收到这个报文为止。这种模式广泛运用于无线传感器网络的众多协议过程中，如路由建立、时问同步过程采取的就是这种模式。
ｂ）节点到基站之间的报文传递，即通过路由树多跳地将报文发送到目的地。节点采样数据之后向基站汇报的过程多采用这种模式，在文中简称为数据转发模式。
在实际应用中，报文并不直接携带发送节点的地址，且洪泛过程采用广播发送方式发送报文，因此无法直接利用洪泛过程来对目标网络的拓扑作出判断。但是在转发模式中的报头中携带有目的地址信息，因此可利用目的地址及报文转发的时间先后关系推断出目标网络节点在数据报文向基站转发过程的传输路径上的先后关系。在此作几个假设：
假设ｌ监听节点能够解读报头信息，进而获得报文的类型及报文的目的地址。只要目标网络采用的不是链路层的加密方式，就能获得目标网络报文的报头信息，进而获得报文的目的地址。
万
方数据假设２报文在向基站汇报的过程中，中间节点不改变报文的内容，由此监听节点可以惟一地区别一个报文。
假设３监听节点的监听半径是以节点为中心的半径Ｒ的圆形。２．２相关定义
在介绍具体的拓扑发现算法之前作如下定义：
定义ｌ
如果节点Ａ是节点Ｂ在数据向基站转发路径中
的下一跳节点，则称节点Ａ是节点Ｂ的父亲节点，节点Ｂ是节点Ａ的子节点。
定义２对于报文向基站转发路径中的相邻两个节点Ａ和Ｂ．若Ａ为Ｂ的父节点，记节点Ｂ发出的报文为Ｍ。，节点Ａ
收到肘。后转发的报文为鸩，称％为帆的后继报文。对于膨。和％，假设数据报文在转发过程中内容不变，因此膨，和
鸩具有相同的报文类型、长度及内容，只是报文的目的地址不相同；同时Ｍ．被监听到的时间在鸩被监听到的时间之后的
一定范围内。２．３算法描述
在报文由源节点向基站汇报的过程中，如果节点Ａ接收到来自于其子节点Ｂ的报文并立即转发出去，则可以观察到节点Ｂ和节点Ａ发送报文的时间间隔，并由此推断出这两个节点在路由树中的父子关系。算法的基本思想正是通过获得报文的目的地址及报文发送的时间推算报文在向基站发送过程中所经过的路径；最后依据基站一定是该报文转发的终点且越靠近基站的监听节点所监听到的通信流量越大的事实推断出基站的位置。详细算法流程如图３所示。
录
束，得到多条路径，根据监测岍蜘通信流鼠刿断鏊站位置
图３算法流程
３算法性能分析
算法是以目标网络的通信记录为输入完成对目标网络拓扑的分析，本文在Ｍｉｃａ２平台上实现了算法，并用ＴｉｎｙＯｓ自带的仿真工具ＴＤｓｓＩＭ对算法的性能进行仿真。理想的情况下，如果监听节点能获得其监听范围内所有的报文，则根据报文的先后关系就可恢复出多条完整的路径。但是在实际网络中，存
在报文丢失、同一个报文被多个监听节点监听到等情况的出
・１８７０・计算机应用研究
第２６卷
现，则可能推测出错误的路径。因此，设定一个评价指标，称为正确路径百分比：
Ｐｃ＝正确判断的路径跳敦／目标网络的实际跳数
构造一个有４０个节点的目标网络，节点的通信半径为ｌＯｍ。如图４所示，网络中基站在（Ｏ，Ｏ）处，有三个数据源（菱形表示），网络采用扩散树路由协议形成的拓扑用点线表示；圆形为监听节点所在位置，监听节点的监听半径为目标节点通信半径的两倍。
３．１
与ＧＢＧＤ算法的比较
图５为本文算法与ＧＢＧＤ算法在不同的报文丢失率情况
下能正确判断率的对比图。从图５中可以看出，在相同的报文丢失率下，本文算法的正确判断率略低于ＧＢＧＤ算法，这是由于ＧＢＧＤ算法假设报文中能获得源地址与目的地址，只要能监听到某个报文，则能肯定地判断出该报文的发送者与接收者；而本文算法是假设在只能获得目的地址的情况下，通过连续转发的时延来判断两个节点间的父子关系，因此需要监听到报文的连续两次转发才能作出正确的判断。故在同等的报文丢失情况下，本文算法性能略低于ＧＢＧＤ。但是在实际的网络中，通过观察知道报文一般不会同时带有目的地址及源地址，因此ＧＢＧＤ算法无法应用于真实的网络中。
静堡餐最甓
倒
Ｘ
报文丢失羁％
图４目标网络拓扑图
图５目标网络拓扑图
３．２报文丢失率对算法性能的影响
在实际情况中，监听网络能完全监听到目标网络的报文通信的可能性很小。如果报文丢失，则可能导致算法得出错误的结果；但是如果监听节点能多次地监听到数据从源节点经过同一条路径向基站发送的过程，则可以通过数据的冗余性获得正确的结果。笔者考察ｊ，在不同报文从源节点到基站发送的轮数的情况下，报文丢失率对Ｐｃ影响，如图６所示。
从图６中可以看出，随着监听网络对目标网络数据转发报文经过同一条路径向基站转发次数的增多，算法能正确推测出目标网络节点路径跳数的百分比越高。另一方面，考察不同丢失率下要达到对目标网络转发路径的正确率达到８０％以上所需的对报文沿同一条路径转发的次数。如图７所示，在报文丢失率达到６０％时，算法只需要监听到５次转发过程便可以推算出提出报文转发的路径，这也从另一方面说明算法对实际情况的适应性较好。
静堡
掇坯辑蒹州嚣
毫
茸
Ｏ１０２０
３０加５０６０７０∞ｌＯ
２０
３０
４０
５０
６０
７０∞９０
报文丢失率
报文丢失率，％
图７报文丢失率与图６报文丢失率与算法性能关系图
监听轮数关系图
万
方数据３．３监听节点覆盖范围对算法影响
监听网络对目标网络的监听覆盖范围与算法的性能有着密切的关系。覆盖范围越高则监听网络所能获得的目标网络通信信息越丰富，算法获得的目标网络拓扑越细致。而覆盖范围与监听节点数目、节点监听半径及节点的分布情况有关。由于传感器网络大都采用随机抛散的方式布设，即使是同等数目的节点也会形成不同的覆盖范围。笔者对于特定的监听节点数及监听半径随机地选取几种拓扑，考察它们的影响。图８为随机随取的几种拓扑所得结果的平均值。
图８为算法在不同的监听节点数和不同的监听半径下所
正确判断数据转发过程的正确率。其中，口为监听节点与目标节点之比。从图８中可以看出，在监听节点数目一定的情况下监听半径越大判断正确率越高；而在监听半径一定时，监听节点越多，正确率越高。
１００９０母８０
静７０
｛｜茎嚣
蚓４０
３０２０ｌ
１．５
２
２．５
３
３．５
监测半径与目标节点通信半径比
图８监听覆盖率与算法性能关系图
本文以发现目标网络拓扑为目的，采用多个监听节点组成网络对目标网络的通信行为进行监听，利用数据向基站转发过程中报文转发的先后关系推测出目标网络数据转发过程中报
文经过的路径，再进一步获得目标网络的关键节点甚至是基站的位置，算法在Ｍｉｃａ２平台上得以实现。经实验证明该算法能较好地运用于实际中。
本文中仍假定能获知报文的目的地址，如果目标网络采用链路层加密则难以获知报文的目的地址。在下一步的工作中，将考虑在无法获得报文目的地址的情况下通过目标网络通信流量来对目标网络的拓扑进行分析。参考文献：
［１］ｃＥＯＲＧＥＦＦＩ．Ａｄｉｓｔ曲ｕｔｅｄ
ｔｏｐｏｌｏｇｙ
ｄｉ∞ｏｖｅｒｙ山谢ｔｌＩｍ
ｆｏｒ
ｗｉｒｅｌ嘲
鸵ｎ蚰ｒ
ｎｅｔｗｏｒｋｓ【Ｄ］．ｎ毗ｈ：ｕｎｉｖ啪ｉｔｙ
ｏｆ
ｗｅｇｔｅｍＡｕｓｔｒａｌｉａ，２００４．［２］
ＤＥＢ
Ｂ，ＢＨＡＴＮＡＧＡＲ
ｓ，ＮＡＴＨ
Ｂ．Ａ
ｔｏｐ０１０９ｙｄｉ眈ｏｖｅｒｙ
ａｌ鲥ｔｈｍ
ｆｏｒ鸵ｎ８叮ｎｅｔｗｏｒｋＢ埘ｍ印ｐＩｉｃａｌｉｏ鹏ｔｏｎｅｔｗｏｄ【ｍａＩｌａｇｅｍｅｎｔ［Ｃ】／／
Ｐｒｏｃ０ｆ
ＩＥＥＥ
ＣＡＳ
Ｗｏｒｋｓｈｏｐ彻Ｗｉｒｅｌｅ昭Ｃｏｍｍｕｎｉｃａｔｉ蚰ｓ鲫ｄＮｅｔ—
ｗｏｒｋｉＩｌｇ．２００２．
［３】藏传真，范玉顺．面向监控和管理的无线传感器网络拓扑发现算
法［Ｊ］．计算机应用研究，２００６，２３（４）：２３０一２３３．
［４］ＤＥＮＧＪｉｎｇ，ＨＡＮＲ，ＭＩｓＨＲＡｓ．Ｄｅｃｏ玎℃Ｉａｔｉｎｇ
ｗｉｒｅｌｅ鹪ｓ蜘８０ｒ
ｎｅｔ－
ｗｏｒｋｔ瑁伍ｃｔｏ
ｉｌｌｌＩｉｂｉｔ
ｔ髓佑ｃ删蛳ｉｓａｔｔａｃｋ８［Ｊ］．Ｅｌｓ酬ｅｒＰｅｒｖａｓ№
ａｎｄＭｏｂｉｌｅ
ＣｏｍｐｕｔｉｎｇＪｏｕｍａＩ：Ｓｐ∞ｉａｌｌｓｓｕｅ
ｏｎ
Ｓ∞ｕｒｉｔｙ
ｉｎ
Ｗｉ怕Ｉｅ∞ＭｏｂｉＩｅＣｏｍｐｕｔＩｎｇＳｙｓｔｅｍｓ，２００６，２（２）：１５９—１８６．［５】李楠，宋金玉，季晓君．ＧＢＧＤ：一种隐蔽的拓扑发现算法［ｃ］／／中
国计算机大会论文集．２００ｒ７：２６４．
４结束语
一种新的无线传感器网络拓扑发现算法
作者：作者单位：刊名：英文刊名：年，卷(期)：
申军， 齐望东， SHEN Jun， QI Wang-dong
解放军理工大学,指挥自动化学院,计算机系,南京,210007计算机应用研究
APPLICATION RESEARCH OF COMPUTERS2009,26(5)
参考文献(5条)
1. 李楠;宋金玉;季晓君 GBGD:一种隐蔽的拓扑发现算法 2007
2. DENG Jing;HAN R;MISHRA S Decorrelating wireless sensor network traffic to inhibit traffic analysisattacks 2006(02)
3. 藏传真;范玉顺 面向监控和管理的无线传感器网络拓扑发现算法[期刊论文]-计算机应用研究 2006(04)4. DEB B;BHATNAGAR S;NATH B A topology discovery algorithm for sensor networks with applications tonetwork management 2002
5. GEORGEFF I A distributed topology discovery algorithm for wireless sensor networks 2004
本文链接：http://d.g.wanfangdata.com.cn/Periodical_jsjyyyj200905076.aspx
第２６卷第５期２００９年５月
计算机应用研究
Ａｐｐ“ｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒ８
Ｖ０１．２６Ｎｏ．５
Ｍａｖ２００９
一种新的无线传感器网络拓扑发现算法
申军，齐望东
（解放军理工大学指挥自动化学院计算机系，南京２１０００７）
摘要：ＧＢＧＤ是一种面向攻击的隐蔽性较强的拓扑发现算法，通过分析发现，该算法对实际网络进行了过于理想化的假设，导致无法在实际中应用。在ＧＢＧＤ算法工作模式的基础上，对实际网络提出了合理假设，设计实现了一种新的网络拓扑发现算法，通过对报文向基站汇聚过程中每一跳转发时延进行分析得出节点在路由树中的层次关系，进而推算出网络的拓扑。仿真实验结果表明，该算法能准确推断出网络的拓扑，并在报文存在丢失较多的情况下具有较好的鲁棒性。由Ｍｉｃａ２节点组成的原型系统实验结果表明，该算法能够较好地应用于实际网络。
关键词：无线传感器网络；拓扑发现；基站；ＧＢＧＤ中图分类号：７ｎ）３９３
文献标志码：Ａ
文章编号：１００ｌ一３６９５（２００９）０５—１８６８－０３
Ｔｏｐｏｌｏｇ）ｒｄｉｓｃｏＶｅｒｙａｌｇｏｒｉｔｈｍｆｏｒｗｉｒｅｌｅｓｓ
ＳＨＥＮ
．
ｓｅｎｓｏｒ
ｎｅｔｗｏｒｋｓ
Ｊｕｎ，Ｑ１ｗ蚰ｇ－ｄｏｎｇ
（巩Ｐ１．旷ｃｏ唧蹴ｒ，触拓ｌ如矿ｃｏＭ，Ⅻ村Ａｎ幻，删洳，ＰＬＡ‰妇Ｈ妙矿ｓｃ诂ｒⅫ＆扎矾，ｌＤ如夥．肫硒增２ｌ０００ｒ７，蕊ｆＭ）
Ａｂ吼ｒａｃｔ：ＧＢＧＤｉｓｒｉｔｈｍｃｏｕｌｄ
ｎｏｔ
ａｎ
ａｔｔａｃｋｏｒｉｅｎｔｅｄｔｏｐｏｌｏｇｙｄｉｓｃｏｖｅｒｙａｌｇｏｒｉｔｈｍｗｉｔｈｈｉｇｈ
ｃｏＴｌｆｉｄｅｎｔｉａｌｉｔｙ．Ｈｏｗｅｖｅｒ，ｆｏｕｎｄ
ｐａｐｅｒ
ｔｈｔｔｈｉｓａ１９０－
ｔｏｐｏｌｏｇ）ｒｄｉｓ．
ｂｅａｐｐｌｉｅｄｉｎａｃｔｕａｌｎｅｔｗｏｒｋｄｕｅｔｏｉｔｓ
ｏｎ
ｕｎｒｅａｌｉｓｔｉｃ硒ｓｕｍｐｔｉｏｎ８
ｏｆｒｅａｌｓｉｔｕａｔｉｏｎｓ．Ｔｈｉｓ
ｐｍｐｏｓｅｄｒｅａｓｏｎａｂｌｅ
ａ
硒ｓｕｍｐＩｉｏｎｓｏｆａｃｔｕａｌｎｅｍｏｒｋｂａｓｅｄ
ｃｏｖｅｒｙ
ｔｈｅｗｏｒｋｐａｔｔｅｍｏｆＧＢＧＤ，ｆｎｈｅ瑚ｏｒｅ，ｄ船ｉ印ｅｄａｎｄｉｍｐｌｅｍｅｎｔｅｄ
ｎｅｗ
ａｌｇｏｒｉｔｈｍ．Ｂｙａｎａｌｙｚｉｎｇｔｈｅｆｏｎｖａｒｄｉｎｇｄｅｌａｙｏｆｅｖｅｒｙｈｏｐｄｕｒｉｎｇｍｅｓｓａｇｅｃｏｎｖｅｒｇｅｎｃｅｐｒｏｃｅｓｓｆｍｍｎｏｄｅｓｔｏｂａｓｅｓｔａ—
ｔｉｏｎ，ｉｔｃｏｕｌｄｇｅｔｔｈｅｌｅｖｅｌｓｏｆｔｈｅｎｏｄｅｓｉｎｔ量ｌｅｔｏｐｏｌｏｇｙ眦ｅｈ口ｍｗｈｉｃｈｃｏｕｌｄｆｉｎａｌｌｙｄｅｄｕｃｅｔｈｅｔｏｐｏｌｏｇ）ｒｏｆｔ｝ｌｅｓｕｎｒｅｉｌｌａｎｃｅ
舱ｔｗ０Ａ．Ａｎａｌｙｓｉｓａｎｄｓｉｍｕｌａｔｉｏｎｓｓｈｏｗ山ａｔ，ｔｈｉｓ
ｇｅｓｌｏＢｔｄｕｒｉＩｌｇｔｒａｎｓｒｒＩｉｓｓｉｏｎ．Ｋｅｙ
ａ如ｒｉｔｈｍｃ粕ｇｅｔｍｅｔｏｐｏｌｏ籽ｏｆｔｈｅｎｅｔｗｏｒｋｅ）疆Ｉｃｔｌｙ
ｅｖｅｎ
ｗｈｅｎ
ｍ粕ｙｍｅｓ鼢・
ｗｏｒｄｓ：ＷＳＮｓ（试ｒｅｌｅ８ｓ驼ｎｓｏｒｎｅｔｗｏｒｋ）；ｔ叩０１０９ｙｄｉｓｃｏｖｅｒｙ；ｂａ∞８ｔａｔｉｏｎ；ＧＢＧＤ
０引言
无线传感器网络（ｗｓＮｓ）是由大量随机分布的，集计算、通信、传感器技术三为一体的廉价微型节点组成的分布式系统。它集合了传感器技术、嵌入式计算、分布式信息处理技术和无线通信技术，能够协作地实时感知环境信息。
无线传感器网络节点廉价、微型的特点使其在军事侦察领域中有着重要的应用前景，已经出现的应用系统如狙击手定位系统、ＶｉｇｉｌＮｅｔ无线传感器侦察网络系统、ＡⅡｎｅ
ｉｎｔｌｌｅ
１
无线传感器网络的拓扑发现算法
根据面向的应用不同，无线传感器网络的拓扑发现算法可
分为以下两种：
ａ）面向网络管理的拓扑发现算法¨。Ｊ。它在于发现网络中节点的活动性、节点间的链路状态、节点的剩余能量等信息，进而为最大限度地延长整个网络系统的寿命提供条件。
ｂ）面向攻击的拓扑发现算法ＨｊＪ。利用无线传感器网络应用中数据整体上向基站汇总的趋势特征为基础，采用被动监
ｓａｎｄ无
听目标刚络通信报文的方式来分析目标网络的拓扑。
ＴｒａｍｃａｎａｌｙｓｉｓＨｏ中，攻击者通过监听通信流量和数据转
线传感器侦察网络等。如何发现并对敌方布设的侦察网络进行攻击在现实中具有重大的意义。目前针对无线传感器网络的攻击方法有很多种，如虚假路由攻击、汇聚节点攻击、虫洞攻击等。不管是何种攻击方式，攻击对象与攻击的效果是密切相关的。对基站及数据转发的中间节点的攻击显然比对目标网络边缘节点的攻击更加有效。
本文以发现敌方传感器网络的拓扑为目的，在目标网络布设区域布置多个监听节点形成监听网络对目标网络的通信过程进行监听，通过对报文向基站发送过程中转发时的时延来完成对目标网络拓扑的分析。
收稿日期：２００８．０８．１５；修回日期：２００８．１０．１７
发路径来推断出目标网络的拓扑信息。越接近基站，需要转发的报文越多，因此网络的通信流量越大，如图ｌ所示。攻击者根据报文多跳地向基站汇聚的特点，沿着数据汇聚的方向追踪基站的位置，但由于无线传感器网络往往数量较大，从数据的源节点到基站的过程中转发的次数较多，采用移动追踪报文的转发路径是不切实际的；另一方面，一个攻击者只能获得网络的局部信息，仅仅依靠这些信息来推断网络的拓扑是不够的。文献［５］中提出的ＧＢＧＤ算法通过布设大量监听节点协作地对目标网络进行监听，如图２所示。在目标网络的覆盖区域内
基金项目：军内预研基金资助项目（４ｌｌｏｌ０４０４０２）
作者简介：审军（１９８３．）。男，贵州惠水人，硕士研究生，主要研究方向为无线传感器网络等（ａｂＩｌ—ｓｊｃｏｒ＠ｙａｌｌ∞．咖．ｃｎ）；齐望东（１９６８．），男，教
授，博导，主要研究方向为无线传感网络、计算机网络等．
万方数据
第５期申军，等：一种新的无线传感器网络拓扑发现算法
布设一定数量的监听节点组成监听网络。通过较多的监听节点被动地监听目标区域的通信情况，依据路由建立过程中路由建立报文转发及数据汇报过程中报文｛胥路由树向基站汇聚的特点，集中地对目标网络进行分析。这种方式能够较大范围地对目标网络的通信情况进行监听，因而能更好地对目标网络的拓扑进行刻画。
图ｌ
ＷＳＮｓ通信流量示意图
图２隐蔽监听ＷＳＮ不意图
ＧＢＧＤ算法无法直接应用于实际中，因为ＧＢＧＤ算法的前提假设无法在实际中成立。这些假设主要有：
ａ）通信报文中携带有发送节点的地址。对无线网络扩散树路由协议及数据汇报过程进行分析发现，这两种通信过程中的消息报头中并不携带发送节点地址。
ｂ）通信信道没有错误发生，即所有的监听记录报文均能可靠地进行传送。在无线传感器网络开放无线通信环境下，发生报文错误与报文丢失是很常见的。因此ＧＢＧＤ算法中依赖于能监听到目标嗍络的所有通信报文的假设无法成立。
ｃ）监听节点能够接收到监听范围内目标网络节点的所有通信报文。
本文提出一种新的基于报文发送时间分析的网络拓扑发现算法，该算法利用报文向基站转发的时间先后关系推断报文到达基站的路径。由于不依赖于ＧＢＧＤ算法的假设，它能应用于现实环境中。
２拓扑发现算法描述
２．１
无线传感器网络报文发送模式
无线传感器网络工作时报文的传递模式主要有两种：ａ）洪泛（ｎ００ｄｉｌｌｇ）的报文传递模式。在这种模式中，基站
向其邻居节点广播某个报文；收到这个报文的节点将报文以同样的方式广播出去，一直到网络中所有的节点都收到这个报文为止。这种模式广泛运用于无线传感器网络的众多协议过程中，如路由建立、时问同步过程采取的就是这种模式。
ｂ）节点到基站之间的报文传递，即通过路由树多跳地将报文发送到目的地。节点采样数据之后向基站汇报的过程多采用这种模式，在文中简称为数据转发模式。
在实际应用中，报文并不直接携带发送节点的地址，且洪泛过程采用广播发送方式发送报文，因此无法直接利用洪泛过程来对目标网络的拓扑作出判断。但是在转发模式中的报头中携带有目的地址信息，因此可利用目的地址及报文转发的时间先后关系推断出目标网络节点在数据报文向基站转发过程的传输路径上的先后关系。在此作几个假设：
假设ｌ监听节点能够解读报头信息，进而获得报文的类型及报文的目的地址。只要目标网络采用的不是链路层的加密方式，就能获得目标网络报文的报头信息，进而获得报文的目的地址。
万
方数据假设２报文在向基站汇报的过程中，中间节点不改变报文的内容，由此监听节点可以惟一地区别一个报文。
假设３监听节点的监听半径是以节点为中心的半径Ｒ的圆形。２．２相关定义
在介绍具体的拓扑发现算法之前作如下定义：
定义ｌ
如果节点Ａ是节点Ｂ在数据向基站转发路径中
的下一跳节点，则称节点Ａ是节点Ｂ的父亲节点，节点Ｂ是节点Ａ的子节点。
定义２对于报文向基站转发路径中的相邻两个节点Ａ和Ｂ．若Ａ为Ｂ的父节点，记节点Ｂ发出的报文为Ｍ。，节点Ａ
收到肘。后转发的报文为鸩，称％为帆的后继报文。对于膨。和％，假设数据报文在转发过程中内容不变，因此膨，和
鸩具有相同的报文类型、长度及内容，只是报文的目的地址不相同；同时Ｍ．被监听到的时间在鸩被监听到的时间之后的
一定范围内。２．３算法描述
在报文由源节点向基站汇报的过程中，如果节点Ａ接收到来自于其子节点Ｂ的报文并立即转发出去，则可以观察到节点Ｂ和节点Ａ发送报文的时间间隔，并由此推断出这两个节点在路由树中的父子关系。算法的基本思想正是通过获得报文的目的地址及报文发送的时间推算报文在向基站发送过程中所经过的路径；最后依据基站一定是该报文转发的终点且越靠近基站的监听节点所监听到的通信流量越大的事实推断出基站的位置。详细算法流程如图３所示。
录
束，得到多条路径，根据监测岍蜘通信流鼠刿断鏊站位置
图３算法流程
３算法性能分析
算法是以目标网络的通信记录为输入完成对目标网络拓扑的分析，本文在Ｍｉｃａ２平台上实现了算法，并用ＴｉｎｙＯｓ自带的仿真工具ＴＤｓｓＩＭ对算法的性能进行仿真。理想的情况下，如果监听节点能获得其监听范围内所有的报文，则根据报文的先后关系就可恢复出多条完整的路径。但是在实际网络中，存
在报文丢失、同一个报文被多个监听节点监听到等情况的出
・１８７０・计算机应用研究
第２６卷
现，则可能推测出错误的路径。因此，设定一个评价指标，称为正确路径百分比：
Ｐｃ＝正确判断的路径跳敦／目标网络的实际跳数
构造一个有４０个节点的目标网络，节点的通信半径为ｌＯｍ。如图４所示，网络中基站在（Ｏ，Ｏ）处，有三个数据源（菱形表示），网络采用扩散树路由协议形成的拓扑用点线表示；圆形为监听节点所在位置，监听节点的监听半径为目标节点通信半径的两倍。
３．１
与ＧＢＧＤ算法的比较
图５为本文算法与ＧＢＧＤ算法在不同的报文丢失率情况
下能正确判断率的对比图。从图５中可以看出，在相同的报文丢失率下，本文算法的正确判断率略低于ＧＢＧＤ算法，这是由于ＧＢＧＤ算法假设报文中能获得源地址与目的地址，只要能监听到某个报文，则能肯定地判断出该报文的发送者与接收者；而本文算法是假设在只能获得目的地址的情况下，通过连续转发的时延来判断两个节点间的父子关系，因此需要监听到报文的连续两次转发才能作出正确的判断。故在同等的报文丢失情况下，本文算法性能略低于ＧＢＧＤ。但是在实际的网络中，通过观察知道报文一般不会同时带有目的地址及源地址，因此ＧＢＧＤ算法无法应用于真实的网络中。
静堡餐最甓
倒
Ｘ
报文丢失羁％
图４目标网络拓扑图
图５目标网络拓扑图
３．２报文丢失率对算法性能的影响
在实际情况中，监听网络能完全监听到目标网络的报文通信的可能性很小。如果报文丢失，则可能导致算法得出错误的结果；但是如果监听节点能多次地监听到数据从源节点经过同一条路径向基站发送的过程，则可以通过数据的冗余性获得正确的结果。笔者考察ｊ，在不同报文从源节点到基站发送的轮数的情况下，报文丢失率对Ｐｃ影响，如图６所示。
从图６中可以看出，随着监听网络对目标网络数据转发报文经过同一条路径向基站转发次数的增多，算法能正确推测出目标网络节点路径跳数的百分比越高。另一方面，考察不同丢失率下要达到对目标网络转发路径的正确率达到８０％以上所需的对报文沿同一条路径转发的次数。如图７所示，在报文丢失率达到６０％时，算法只需要监听到５次转发过程便可以推算出提出报文转发的路径，这也从另一方面说明算法对实际情况的适应性较好。
静堡
掇坯辑蒹州嚣
毫
茸
Ｏ１０２０
３０加５０６０７０∞ｌＯ
２０
３０
４０
５０
６０
７０∞９０
报文丢失率
报文丢失率，％
图７报文丢失率与图６报文丢失率与算法性能关系图
监听轮数关系图
万
方数据３．３监听节点覆盖范围对算法影响
监听网络对目标网络的监听覆盖范围与算法的性能有着密切的关系。覆盖范围越高则监听网络所能获得的目标网络通信信息越丰富，算法获得的目标网络拓扑越细致。而覆盖范围与监听节点数目、节点监听半径及节点的分布情况有关。由于传感器网络大都采用随机抛散的方式布设，即使是同等数目的节点也会形成不同的覆盖范围。笔者对于特定的监听节点数及监听半径随机地选取几种拓扑，考察它们的影响。图８为随机随取的几种拓扑所得结果的平均值。
图８为算法在不同的监听节点数和不同的监听半径下所
正确判断数据转发过程的正确率。其中，口为监听节点与目标节点之比。从图８中可以看出，在监听节点数目一定的情况下监听半径越大判断正确率越高；而在监听半径一定时，监听节点越多，正确率越高。
１００９０母８０
静７０
｛｜茎嚣
蚓４０
３０２０ｌ
１．５
２
２．５
３
３．５
监测半径与目标节点通信半径比
图８监听覆盖率与算法性能关系图
本文以发现目标网络拓扑为目的，采用多个监听节点组成网络对目标网络的通信行为进行监听，利用数据向基站转发过程中报文转发的先后关系推测出目标网络数据转发过程中报
文经过的路径，再进一步获得目标网络的关键节点甚至是基站的位置，算法在Ｍｉｃａ２平台上得以实现。经实验证明该算法能较好地运用于实际中。
本文中仍假定能获知报文的目的地址，如果目标网络采用链路层加密则难以获知报文的目的地址。在下一步的工作中，将考虑在无法获得报文目的地址的情况下通过目标网络通信流量来对目标网络的拓扑进行分析。参考文献：
［１］ｃＥＯＲＧＥＦＦＩ．Ａｄｉｓｔ曲ｕｔｅｄ
ｔｏｐｏｌｏｇｙ
ｄｉ∞ｏｖｅｒｙ山谢ｔｌＩｍ
ｆｏｒ
ｗｉｒｅｌ嘲
鸵ｎ蚰ｒ
ｎｅｔｗｏｒｋｓ【Ｄ］．ｎ毗ｈ：ｕｎｉｖ啪ｉｔｙ
ｏｆ
ｗｅｇｔｅｍＡｕｓｔｒａｌｉａ，２００４．［２］
ＤＥＢ
Ｂ，ＢＨＡＴＮＡＧＡＲ
ｓ，ＮＡＴＨ
Ｂ．Ａ
ｔｏｐ０１０９ｙｄｉ眈ｏｖｅｒｙ
ａｌ鲥ｔｈｍ
ｆｏｒ鸵ｎ８叮ｎｅｔｗｏｒｋＢ埘ｍ印ｐＩｉｃａｌｉｏ鹏ｔｏｎｅｔｗｏｄ【ｍａＩｌａｇｅｍｅｎｔ［Ｃ】／／
Ｐｒｏｃ０ｆ
ＩＥＥＥ
ＣＡＳ
Ｗｏｒｋｓｈｏｐ彻Ｗｉｒｅｌｅ昭Ｃｏｍｍｕｎｉｃａｔｉ蚰ｓ鲫ｄＮｅｔ—
ｗｏｒｋｉＩｌｇ．２００２．
［３】藏传真，范玉顺．面向监控和管理的无线传感器网络拓扑发现算
法［Ｊ］．计算机应用研究，２００６，２３（４）：２３０一２３３．
［４］ＤＥＮＧＪｉｎｇ，ＨＡＮＲ，ＭＩｓＨＲＡｓ．Ｄｅｃｏ玎℃Ｉａｔｉｎｇ
ｗｉｒｅｌｅ鹪ｓ蜘８０ｒ
ｎｅｔ－
ｗｏｒｋｔ瑁伍ｃｔｏ
ｉｌｌｌＩｉｂｉｔ
ｔ髓佑ｃ删蛳ｉｓａｔｔａｃｋ８［Ｊ］．Ｅｌｓ酬ｅｒＰｅｒｖａｓ№
ａｎｄＭｏｂｉｌｅ
ＣｏｍｐｕｔｉｎｇＪｏｕｍａＩ：Ｓｐ∞ｉａｌｌｓｓｕｅ
ｏｎ
Ｓ∞ｕｒｉｔｙ
ｉｎ
Ｗｉ怕Ｉｅ∞ＭｏｂｉＩｅＣｏｍｐｕｔＩｎｇＳｙｓｔｅｍｓ，２００６，２（２）：１５９—１８６．［５】李楠，宋金玉，季晓君．ＧＢＧＤ：一种隐蔽的拓扑发现算法［ｃ］／／中
国计算机大会论文集．２００ｒ７：２６４．
４结束语
一种新的无线传感器网络拓扑发现算法
作者：作者单位：刊名：英文刊名：年，卷(期)：
申军， 齐望东， SHEN Jun， QI Wang-dong
解放军理工大学,指挥自动化学院,计算机系,南京,210007计算机应用研究
APPLICATION RESEARCH OF COMPUTERS2009,26(5)
参考文献(5条)
1. 李楠;宋金玉;季晓君 GBGD:一种隐蔽的拓扑发现算法 2007
2. DENG Jing;HAN R;MISHRA S Decorrelating wireless sensor network traffic to inhibit traffic analysisattacks 2006(02)
3. 藏传真;范玉顺 面向监控和管理的无线传感器网络拓扑发现算法[期刊论文]-计算机应用研究 2006(04)4. DEB B;BHATNAGAR S;NATH B A topology discovery algorithm for sensor networks with applications tonetwork management 2002
5. GEORGEFF I A distributed topology discovery algorithm for wireless sensor networks 2004
本文链接：http://d.g.wanfangdata.com.cn/Periodical_jsjyyyj200905076.aspx