改进的ZigBee网络路由算法

ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用

２００９，４５（５）

９５

改进的ＺｉｇＢｅｅ网络路由算法

班艳丽，柴乔林，王芳

ＢＡＮＹａｎ－ｌｉ，ＣＨＡＩ

Ｑｉａｏ－ｌｉｎ，ＷＡＮＧ

Ｆａｎｇ

山东大学计算机科学与技术学院，济南２５０１０１

ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，ＳｈａｎｄｏｎｇＵｎｉｖｅｒｓｉｔｙ，ＪｉｎａｎＳｈａｎｄｏｎｇ２５０１０１，Ｃｈｉｎａ

Ｅ－ｍａｉｌ：ｙａｎｌｉ＿ｂａｎｌ９８５＠１６３．ｃｏｉｎ

ＢＡＮ

Ｙａｈ－Ｉｉ．ＣＲＡＩＱｉａｏ－Ｕｎ。ＷＡＮＧＦａｎｇ．ＩｍｐｒｏｖｅｄｒｏｕｔｉｎｇａｌｇｏｒｉｔｈｍｆｏｒＺｉｇＢｅｅｎｅｔｗｏｒｋｓ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄ

Ａｐｐｌｉｃａｔｉｏｎｓ，２００９，４５（５）：９５－９７．

Ａｂｓｔｒａｃｔ：Ａｉｍｉｎｇｍｕｔｉｎｇ

ａｔ

ｔｈｅｐｒｏｂｌｅｍｏｆ

ｎｅｔｗｏｒｋｓ

ＲＲＥＱ

ｉｓ

ｐａｃｋｅｔｓ

ｆｌｏｏｄｉｎｇａｔｒｏｕｔｉｎｇｄｉｓｃｏｖｅｒｙｐｈａｓｅｉｎＺｉｇＢｅｅＡＯＤＶｊｒａｌｇｏｒｉｔｈｍ，ａｌｌｉｍｐｒｏｖｅｄ

ａｌｇｏｒｉｔｈｍ

ａｌｇｏｒｉｔｈｍｆｏｒＺｉｇＢｅｅｐｒｏｐｏｓｅｄ．ＡＯＤＶｊｒ

ａｎｄ

ｔｒｅｅ

ｍｕｔｉｎｇａｌｇｏｒｉｔｈｍ

ａｒｅ

ｃｏｍｂｉｎｅｄ

ｔｏ

ｃｏｎｔｒｏｌｔｈｅｒａｎｇｅ

ａｎｄｔｈｅｄｉｒｅｃｔｉｏｎｏｆ

ｔｈｅＲＲＥＱｐａｃｋｅｔｓｉｎｔｈｉｓｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍ．Ａｔｔｈｅｓａｍｅｔｉｍｅ，ｔｈｅｒｅｓｉｄｕａｌｅｎｅｒｇｙｏｆｎｏｄｅｓｉｓａｌｓｏｃｏｎｓｉｄ－

ｅｒｅｄｔｏａｖｏｉｄｓｅｌｅｃｔｉｎｇｓｏｍｅｎｏｄｅｓｗｉｔｈｌｏｗｒｅｓｉｄｕａｌｅｎｅｒｇｙｉｎｒｏｕｔｉｎｇｓｅｌｅｃｔｉｏｎ．Ｔｈｅｓｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｓｉｎｄｉｃａｔｅｔｈａｔｔｈｅｅｎｅｒｇｙ

ｃｏｎｓｕｍｐｔｉｏｎｉｓｉｎ

ｔｈｉｓｉｍｐｒｏｖｅｄ

ｒｅｄｕｃｅｄｅｆｆｉｃｉｅｎｔｌｙ，ｔｈｅａｌｇｏｒｉｔｈｍ．

ｐｒｏｂｌｅｍ

ｏｆｕｎｂａｌａｎｃｅｂａｄｉｓｒｅｓｏｌｖｅｄａｎｄｔｈｅｌｉｆｅｔｉｍｅｏｆｔｈｅｗｈｏｌｅｎｅｔｗｏｒｋｉｓｍａｘｉｍｉｚｅｄ

Ｋｅｙｗｏｒｄｓ：ＺｉｇＢｅｅ

ｎｅｔｗｏｒｋ；ＡＯＤＶｊｒ

ａｌｇｏｒｉｔｈｍ；ｔｒｅｅｍｕｔｉｎｇａｌｇｏｒｉｔｈｍ；ｒｅｓｉｄｕａｌｅｎｅｒｇｙ；ＯＭＮＥＴ＋＋ｓｉｍｕｌａｔｉｏｎ

摘要：针对ＺｉｇＢｅｅ网络ＡＯＤＶｊｒ路由算法路由发现过程中的ＲＲＥＱ分组大量洪泛ｆ＇－＇ｌ题，提出一种改进的ＺｉｇＢｅｅ网络路由算法。改进算法中通过采用ＡＯＤｖｊｒ算法和树路由算法相结合的方式，对ＲＲＥＱ分组的传输范围和大致方向进行控制，同时改进算法中也考虑了节点的剩余能量，路由选择的时候尽量避开剩余能量较低的节点。仿真结果表明，改进算法能有效地节省网络的总体能量消耗，实现网络负载均衡，最大化网络的生存时间。

关键词：ＺｉｇＢｅｅ网络；ＡＯＤＶｊｒ算法；树路由算法；剩余能量；ＯＭＮＥＴ＋舫真

ＤＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２—８３３１．２００９．０５．０２７

文章编号：１００２—８３３１（２００９）０５—００９５－０３

文献标识码：Ａ

中图分类号：ＴＰ３９３

１引言

ＺｉｇＢｅｅ是一种低成本、低功耗、低速率的短距离无线通信新技术，该技术主要针对低速率无线传感器和控制网络而设计，它能够满足小型化、低成本设备（如温度调节装置、照明控制器、环境检测传感器等）的无线联网要求，能广泛地应用于工

２２．１

ＡＯＤＶｊｒ算法和树路由算法简述ＡＯＤＶｊｒ算法

ＡＯＤＶｊｒ是ＡＯＤＶ的简化版本，具有ＡＯＤＶ的主要功能，但

考虑到降低成本、节能、使用方便等特点，简化了ＡＯＤＶ的一些特点。

首先ＡＯＤＶｊｒ舍弃了ＡＯＤＶ中的目的节点序列号，为了保证路由无回路，ＡＯＤＶｊｒ规定只有目的节点可以对ＲＲＥＱ分组

业、家庭以及医学等需要低功耗、低成本、对数据速率和服务质量要求不高的无线通信应用场合”。

ＺｉｇＢｅｅ网络主要支持ＡＯＤＶｊｒ算法唧日树路由算法Ｍ。而

在Ｍｅｓｈ结构中一般采用ＡＯＤｖｊｒ算法。ＡＯＤＶｊｒ是在ＡＯＤＶ的基础上发展而来的，支持端到端的传输。在路由发现过程中由于ＲＲＥＱ分组大量洪泛，从而导致大量的额外能量消耗，使网络总体耗能过大。尽可能地降低ＲＲＥＱ分组开销ｆｑ，也是降低网络整体耗能的途径之一。对传统的ＡＯＤＶｊｒ算法进行了改进，在路由发现过程中采用ＡＯＤＶｊｒ和树路由算法相结合的方法，根据树路由算法的特点对ＡＯＤＶｊｒ中ＲＲＥＱ分组的传输范围和大致方向进行控制，从而减少网络控制开销，节约网络总体耗能。另外，还将考虑节点的剩余能量，从而避某些节点可能会因为业务量过大而过早耗尽电池能量，延长了网络寿命。

进行响应，即使中间节点存在到目的节点的路径也不允许回复

ＲＲＥＱ。同时ＡＯＤＶｊｒ不存在ＡＯＤＶ中的“先驱节点列表”，从而

简化了路由表结构。另外ＡＯＤＶｊｒ取消了ＨＥＬＬＯ信息的发送，

由目的节点定期向源节点发送ＫＥＥＰ－ＡＬＩＶＥ连接信息来维持路由。当源节点在一段时问内没有收到目的节点发来的

ＫＥＥｔＡＬＩＶＥ信号时，则认为此路径失效，必要时重新进行路

由发现。

２．２树路由算法

加入ＺｉｇＢｅｅ网络的节点通过ＩＥＥＥ

８０２．１５．４

ＭＡＣ层提供

的关联过程组成一颗逻辑树，当网络中的节点允许—个新节点通过它加入网络时，它们之间就形成了父子关系，每个进入网

作者简介：班艳丽（１９８５一），女，硕士研究生，研究方向为网络与分布式技术；柴乔林（１９５６一），男，教授，研究方向为计算机网络；王芳（１９８４一），女，

硕士研究生，研究方向为网络与分布式技术。

收稿日期：２００８－０８－０６

修回日期：２００８—１１－０３

万方数据　

改进的ZigBee网络路由算法

９６

２００９，４５（５）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用

络的节点都会得到父节点为其分配的一个在该网络中唯一的网络地址。文献【４—５】对网络地址分配机制均做了详细的描述。

按照文献【４—５１中的地址分配机制，图ｌ给出了Ｃｍ＝４，Ｒｍ＝３，Ｌｍ－－４的网络Ｃｓｋｉｐ地址分配的例子。节点内的数字为该节

点的地址，以下均用该节点地址来标示该节点。

图１网络节点地址分配

如果ＲＦＤ（Ｒｅｄｕｃｅｄ

Ｆｕｎｃｔｉｏｎ

Ｄｅｖｉｃｅ，精简功能设备）节点

要发送数据包到嘲络中的其他节点，则直接将该数据包转发给其父节点，由父节点进行转发。

如果—个路由器ＦＦＤ（Ｆｕｌｌ

Ｆｕｎｃｔｉｏｎ

Ｄｅ啊ｃｅ，全功能设备）

节点要转发数据包到网络地址为Ｄ的目的节点，已知该路由器节点的网络地址和深度分别为Ａ和ｄ。

首先，该路由器节点会依据下述表达式判断目的节点是否是其后裔节点：

Ａ＜Ｄ＜Ａ＋Ｃｓｋｉｐ（ｄ－１）

（１）

如果目的节点是其后裔节点，则下一跳节点地址为：

ｆＤ，如果目的节点是其子节点

肚｛Ａ＋１＋ＩＤ－（Ａ＋Ｉ）Ｊ删砌），否则

汜’

否则，如果目的节点不是其后裔节点，则下一跳节点为该

节点的父节点。

３问题的提出

虽然ＡＯＤＶｊｒ可以比树路由算法找到最优路径，但是ＡＯＤＶｊｒ算法在路由发现过程仍然会产生多余的ＲＲＥＱ分组，

这些ＲＲＥＱ分组虽然也参与路由发现过程，但对于最终找到一

条最优的路径并不起到太大作用。如图ｌ所示，节点２要发送数据给节点５５，按照树路由算法则需要经过４跳，但是如果按照ＡＯＤＶｊｒ算法，如果ＲＲＥＱ分组的跳数大于４仍然继续洪泛的话，则对最终找到最优路径起不到太大作用。

另外，如果节点２要发送数据到节点１０７，如果节点２没有到节点１０７的路由表项，则发起路由发现过程，节点２向其

所有邻居节点发送ＲＲＥＱ分组，由于节点１０７并不是节点２的

后裔节点，则节点２向其后裔节点发送的ＲＲＥＱ分组，则对于节点２寻找到节点１０７的最优路径所起的作用不大。

如果节点２要发送数据到节点９，如果节点２没有到节点９的路由表项，则发起路由发现过程，节点２向其所有邻居节点发送ＲＲＥＱ分组，考虑到节点９是节点２的后裔节点，所以节点２向其父节点发送ＲＲＥＱ分组，则对于节点２寻找到节点

万　

方数据９的最优路径所起的作用也不大。

另外，在ＺｉｇＢｅｅ网络中，距离中心协调器越近的节点，通常需要转发的数据量就越大，所消耗的能量就越大，如果这些节点耗尽自身能量，不仅自身不能与其他节点通信，还容易造成网络分割，缩短了网络寿命。

针对以上这些问题，将综合ＡＯＤＶｊｒ算法和树路由算法，适当地限制路由发现过程中的ＲＲＥＱ分组的洪泛，并对节点的剩余能量值加以考虑，提出了下面的改进算法。

４改进算法设计

改进算法利用ＡＯＤＶｊｒ和树路由算法相结合的方法，前提是所有节点在加入网络的时候形成—颗逻辑树，每个进入网络的节点都会得到父节点为其分配的一个在该网络中唯一的网络地址。

４．１节点最小剩余能量定义

在ＺｉｇＢｅｅ网络中，距离中心协调器越近的节点，通常需要转发的数据量就越大，体现在ＺｉｇＢｅｅ树形结构上，即深度越小的节点，参与转发的数据量就越大，所以节点的最小剩余能量

就应与节点深度有关，深度越小的节点就应为其预留更多的最小剩余能量值，这样才能保证网络不会因为节点的失效而造成网络分割，甚至网络瘫痪。

假设节点初始能量值为ｅｎｅｒｇｙ，对任一节点ｉ，定义节点最

小剩余能量值Ｅ。。公式如下：

‰＝｛＿×、／ｅ地斜×了ｌ＿ＸＩＸ

（３）

●

Ｕｚ

Ｔ１

其中，ｔ表示网络运行时间，ｄ表示节点ｉ的深度（因为节点深度是从０开始编号，所以公式中用深度加１表示），ＩＸ为一特定

系数（仿真试验中取值Ｉｘ＝２），ｄ的作用在于减缓Ｅ…值减小的

速度。

从公式（３）可以看出节点的最小能量值与算法执行的时间、

节点的深度均成反比，当ｔ增大到一定程度，某些被停止使用的节点可能又被继续利用，当ｔ趋近于无穷大时，可以认为Ｅ。

值趋近于零，此时可以把剩余能量值仍低于Ｅ。。的节点看成死

亡节点。并且从时间的倒数曲线我们可以看出，ｋ；。递减的幅度随着时间的增大越来越小，这样的设定符合网络节点能量的实

际睛况，开始节点能量比较充足，乜。递减的速度可以相对较快，但当节点能量普遍较低的情况下，Ｅ。，。递减的幅度就应该变慢。

在改进算法中，对每个具有路由功能的ＦＦＤ节点设置了

变量ｐｏｗｅｒ标识该节点的剩余能量。当发现节点的ｐ刚ｅｒ姐。；。

时，该节点停止转发并且发出警告信息ａｌｅｒｔ，告知源节点该路

径上有节点能量过小，很可能引起路径失效，并且设置沿途所有

节点中该路由表项失效，让源节点在必要时重新进行路由发现。

４．２改进的路由算法

从图ｌ的树形结构可以看出，如果使用树路由算法选择路由，可能存在的最长路径应是网络最大深度的２倍，即２Ｌｍ。因此改进算法中规定ＲＲＥＱ的最大传输范围为２Ｌｍ，这样当ＲＲＥＱ的传输范围超过２Ｌｍ时，节点便丢弃接收到的ＲＲＥＱ分组。

ＺｉｇＢｅｅ树路由算法可以通过表达式（１）判断目的节点是否是中问转发节点的后裔节点。因此，如果目的节点是该转发节

点的后裔节点，此时如果仍然让该转发节点的父节点转发

改进的ZigBee网络路由算法

班艳丽，柴乔林，王芳：改进的ＺｉｇＢｅｅ网络路由算法

２００９．４５（５）

９７

ＲＲＥＱ，则通过其父节点寻找最优路径的可能性是很小的。同样，如果目的节点不是该转发节点的一个后裔节点，如果仍让该转发节点的后裔节点转发ＲＲＥＱ分组的话，对寻找最优路径

也没有太大意义。因此，改进算法结合树路由的基本思想，判断

出ＲＲＥＱ分组的大致方向，从而避免ＲＲＥＱ分组沿与目的节点相反的方向洪泛，节约网络总体耗能。

改进算法在ＡＯＤＶｊｒ算法的基础上，对ＲＲＥＱ分组中增加标志位ｆｌａｇ：ｆｌａｇ－－Ｏ表示当前节点的父节点不宜转发该ＲＲＥＱ分组，ｆｌａｇ＝ｌ表示当前节点的后裔节点不宜转发该ＲＲＥＱ分组。

路由方法具体如下：

（１）如果ＲＦＤ节点要发送数据到网络中其他节点，则ＲＦＤ节点直接将数据转发给其父节点，由其父节点进行转发。

（２）当具有路由功能的ＦＦＤ节点要发送数据到网络中的其他节点时，如果源节点的路由表中没有到目的节点的路由表项，则启动路由发现过程。

（３）在路由发现阶段，当节点Ｂ作为中间转发节点收到

节点Ａ发来的ＲＲＥＱ分组时，首先节点Ｂ检测自身剩余能量ｐｏｗｅｒ值。

（４）如果ｐｏｗｅｒ＜Ｅ，。，则曰丢弃ＲＲＥＱ。

（５）否则，节点Ｂ查看ＲＲＥＱ分组里的跳数值，如果跳数

ｈｏｐｓ＞２Ｌｍ，丢弃ＲＲＥＱ。

（６）否则，节点曰查看ＲＲＥＱ分组里的ｆｌａｇ值，如果ｆｌａｇ＝Ｏ，说明Ａ的父节点不适合转发此ＲＲＥＱ分组。

如果曰是Ａ的父节点，节点曰丢弃ＲＲＥＱ；

如果曰不是Ａ的父节点，判断目的节点是否是节点曰的后裔节点，如果不是，更新ｆｌａｇ＝ｌ，节点口继续转发ＲＲＥＱ分组，并更新自身ｐｏｗｅｒ；否则曰直接转发ＲＲＥＱ，并更新自身ｐｏｗｅｒ。

（７）如果ｆｌａｇ＝ｌ，说明Ａ的后裔节点不适合转发此ＲＲＥＱ；如果节点Ｂ是节点Ａ的后裔节点，节点Ｂ丢弃ＲＲＥＱ；如果Ｂ不是Ａ的后裔节点，判断目的节点是否是曰的后裔节点，如果

Ｎ

Ｙ叵

图２中闯节点对ＲＲＥＱ处理谪程图

万　

方数据是其后裔节点，则更新ｆｌａｇ＝Ｏ，节点曰继续转发ＲＲＥＱ，并更新自身ｐｏｗｅｒ；否则Ｂ直接转发ＲＲＥＱ，并更新自身ｐｏｗｅｒ。（８）当目的节点收到ＲＲＥＱ包时，不论剩余能量多少，都发回—个ＲＲＥＰ包。

（９）源节点收到目的节点发来的ＲＲＥＱ分组时，则按照该路由发现的路径进行数据传输。

５算法分析和仿真实验结果５．１算法分析

本文的改进算法是在传统ＡＯＤｖｊｒ算法的基础之上，结合ＺｉｇＢｅｅ树路由算法并考虑到节点剩余能量，针对不同情况，对所收ＲＲＥＱ采用不同的处理方法。同时改进算法又通过公式（３）不断更新节点的最小剩余能量值，使部分被停止使用的节

点继续参与数据的转发，从而防止由于网络中路由节点过少而

出现的拥塞。改进算法过程简单，由各节点独立计算。算法的时问复杂度为Ｏ（，ｖ），可以在常量时问内结束。

５．２仿真结果分析

改进算法通过仿真实验和原ＡＯＤＶｊｒ进行了比较，重点是比较两者在传输时网络总体能耗及失效节点个数。仿真结果证明了改进算法的有效性。

仿真工具采用Ｏｍｎｅｔ＋＋３．２ｐｌ。网络覆盖面积为３００

ｍ×

５００ｍ，网络节点数目设置为１００个，节点初始能量均为１

０００Ｊ。

采用的传输信道数据传输率为２５０ＫＢ，数据包长度为１２８ｂｉｔ。

仿真实验结果如图３、４所示。设置Ｃｍ－－４，Ｒｍ＝３，Ｌｍ＝４。仿真实

验结果如图３，４所示。

ＴｉｍｅｄｓＴｉｍｅｄｓ

图３阿络总体能量消耗随

图４网络中死亡结点个数随

时问的变化曲线

时『ＢＪ的变化曲线

在图３中，曲线ｌ代表ＡＯＤＶｊｒ路由算法运行时网络的总体能量消耗，曲线２代表本文改进算法运行时网络的总体能量消耗。由于改进算法对路由发现过程中的ＲＲＥＱ分组进行了有效的控制，同时又避免把数据传送给能量较低的节点，从而节省了网络整体耗能。

在图４中，曲线ｌ表示ＡＯＤｖｊｒ路由算法运行时网络的死亡节点个数，曲线２表示本文改进算法运行时网络的死亡节点个数。初始阶段，每个节点的能量都很充足，不会产生死亡节点，随着网络运行时间的增长，有的节点频繁作为转发节点消耗很大的能量，ＡＯＤＶｊｒ路由算法没有考虑节点的剩余能量值，所以出现死亡节点的时间比改进算法要早。本文的改进算法由于避开了剩余能量低的节点，选择能量多的节点进行数据转发，所以避免了个别节点过早死亡，均衡网络的负载，最大化网络的生存时间。

６结论

针对传统的ＺｉｇＢｅｅ网络ＡＯＤＶｊｒ路由算法，提出一种改进

（下转１１６页）

改进的ZigBee网络路由算法

１１６

２００９，４５（５）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用

为了比较原始的最大流算法和提出的ＰＨ—ＭａｘＦｌｏｗ算法，特提出了客观的评价标准，更具有说服力。实验结果表明运用所提

的页面所指向的页面，以及所有指向ｒｏｏｔ集的页面，把这些网

页限制在５０个以内。由３．１提出ＰＨＩＳＴ算法得到口…’值较高的

网页为种子节点，再经过３．２ＰＨ—ＭａｘＦｌｏｗ算法处理得到所求的社区。用所提出的评价标准对发现的社区进行评价，得到原始最大流算法和提出的ＰＨ—ＭａｘＦｌｏｗ算法的对比结果，如表１和表２所示。对比结果，可以看出，使用提出的ＰＨ—ＭａｘＦｌｏｗ算法，可以发现更权威的种子节点，从而发现更大更精确的社区，并且社区的划分也比原始的最大流算法合理。

表ｌ原始最大漉算法发现Ｗｅｂ设区

出的算法可以发现更符合主题需要的Ｗｅｂ社区。参考文献：

［１】１高琰。古士文，唐珊．基于链接分析的ｗｅｂ社区发现技术的研究叨．

计算机应用研究，２００６（７）：１８３—１８５．

【２１ＫｌｅｉｎｂｅｒｇＪ．Ａｕｔｈｏｒｉｔａｔｉｖｅ

ｇｏｕｒｃｅｓ

ｉｎ

ａ

ｈｙｐｅｒｌｉｎｋｅｄ

ｏｎ

ｅｎｖｉｒｏｎｍｅｎｔ［Ｃ］／／

Ｄｉｓｃｒｅｔｅ

Ａｌｓｏ－

Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ９ｔｈＡＣＭ—ＳＩＡＭＳｙｍｐｏｓｉｕｍｒｉｔｈｍｓ．Ｓａｎ

Ｆｒａｎｃｉｓｃｏ，ＵＳＡ，Ｊａｎ２５—２７１９９８．ＵＳＡ，ＳＩＡＭ，Ｐｈｉｌａｄｅｌｐｈｉａ，

１９９８：６６８—６７７．

【３】ＫｕｍａｒＲ，ＲａｇｈａｖｆｌｎＰ，ＲａｊａｇｏｐａｌａｎＳ，ｅｔａ１．ＴｒａｗｌｉｎｇｔｈｅＷｅｂｆｈ

ｅｍｅｒｇｉｎｇｃｙｂｅｒｃｏｍｍｕｎｉｔｉｅｓ［Ｃ］／／Ｐｒｏｃｏｆｔｈｅ８ｔｈＷＷＷＩｎｔｅｒｎａ－

ｔｉｏｎａｌ

Ｃｏｎｆｅｒｅｎｃｅ。Ｔｏｒｏｎｔｏ，Ｍａｙ

１１一Ｍａｙ

１４

１９９９．Ｎｅｔｈｅｒｌａｎｄｓ，Ｅ１－

ｓｅｖｉｅｒＳｅｉＢＶ。１９９９：１４８ｌ一１４９３．

【４】Ａ８蛐Ｙ，Ｉｍａｉ

Ｈ，ＴｏｙａｄａＭ，ｅｔａ１．Ｆｉｎｄｉｎｇｎｅｉｇｈｂｏｒｃｏｍｍｕｎｉｔｉｅｓｉｎ

ｔｈｅＷｅｂｕｓｉｎｇａｎｉｎｔｅｒ－ｓｉｔｅｇｒａｐｈ［Ｊ］．ＩＥＩＣＥＴｒａｎｓａｃｔｉｏｎｓｏｎＩｎｆｏｒ－

ｍａｔｉｏｎａｎｄＳｙｓｔｅｍｓ，２００４，９：２１６３－２１７０．

【５】ＦｌａｋｅＧＷ，ＬａｗｒｅｎｃｅＳ，ＧｉｌｅｓＣＬ，ｅｔａ１．Ｓｅｌｆｏｒｇａｎｉｚａｔｉｏｎｏｆｔｈｅ

ｗｅｂａｎｄｉｄｅｎｔｉｆｉｃａｔｉｏｎｏｆ

ａｒｃｈｉｖｅ．ｏｒｇ

ｃｏｎｎｎｕｎｉｔｉｅｓ［Ｊ１．ＩＥＥＥＣｏｍｐｕｔｅｒ，２００２，３５

ｏｆ

（３）：６６－７１．

３２６

ｏ．５６

Ｉｎｔｅｒｎｅｔ舡№“攀中～

ａｒｃｎｌｖｌｓｌｓ．ｏｒｇ

【６】ＩｍａｆｕｊｉＮ，ＫｉｔｓｕｍｇａｗａＭ．Ｅｆｆｅｃｔｓ

ｍａｘｉｍｕｍｆｌｏｗ

ａｌｇｏｒｉｔｈｍ

ｏｎ

ａｒｃｈｉｖｅ．ｏｒｇ／ｗｅｂ／ｗｅｂ．ｐｈｐ

ｉｄｅｎｔｉｆｙｉｎｇｗｅｂｔｉｏｎａｌＷｏｒｋｓｈｏｐｅｄ

Ｓｔａｔｅｓ。Ｎｏｖ

ｅｏｍｍｕｎｉｔｙ［Ｃｌ／／ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＦｏｕｒｔｈＩｎｔｅｒｎａ－

ｏｎ

ＷｅｂＩｎｆｏｒｍａｔｉｏｎａｎｄＤａｔａＭａｎａｇｅｍｅｎｔ．ＵＩＩｉｔ－

２００２．Ｕｎｉｔｅｄ

Ｓｔａｔｅｓ：Ａｓｓｏｃｉａｔｉｏｎｆｏｒ

８

Ｃｏｍｐｕｔｉｎｇ

ｔｈｅ

Ｍａｃｈｉｎｅｒｙ，２００２：４３－－４８．

【７１ＡｓａｎｏＹ，ＮｉｓｈｉｚｅｋｉＴ，ＴｏｙａｄａＭ，ｅｔａ１．Ｍｉｎｉｎｇｃｏｍｍｕｎｉｔｉｅｓ

ｏｎ

６结论

首先提出ＰＨＩＴＳ算法，在一定程度上抑制了原始的ＨＩＴＳ算法所存在的“主题偏移”现象，运用ＰＨＩＴＳ算法发现权威值高的页面，即与主题关系更为密切的页面作为最大流算法的种子节点。采用提出的ＰＨ—ＭａｘＦｌｏｗ算法，将种子节点的发现过程和Ｗｅｂ社区的发现过程相分离，避免了原始最大流算法反

ｗｅｂ

ｕｓｉｎｇ

ａ嗽一ｎ删ｆ

ａｎｄｓｉｔｅ—ｏｒｉｅｎｔｅｄ

ｆｒａｍｅｗｏｒｋ［１］．ＩＥＩＣＥ

Ｔｒｉｍｓ

ＯｎＩｎｆｏｒｍａｔｉｏｎ

ａｎｄＳｙｓｔｅｍｓ。２００６，Ｅ８９－Ｄ：２６０６—２６１５．

ｃｏｎｕｌｌｕ－

【８】ＩｎｏＨ。ＫｕｄｏＭ，ＮａｋａｍｕｒａＡ．Ｐａｒｔｉｔｉｏｎｉｎｇｏｆｗｅｂｇｒａｐｈｓｂｙ

ｌａｉｔｙ

［９】９

ｔｅｐｏｌｏｇｙ［Ｃｌ／／ＰｒｏｅｏｆＷＷＷ２００５，Ｊａｐａｎ．ＡＣＭ，２００５：６６１－６６９．ＤｏｕｒｉｓｂｏｕｒｅＹ，ＧｅｒａｃｉＦ，ＰｅｌｌｅｇｒｉｎｉＭ．Ｅｘｔｒａｃｔｉｏｎａｎｄｃｌａｓｓｉｆｉｃａｔｉｏｎ

ｏｆｄｅｎｓｅｃｏｍｍｕｎｉｔｉｅｓｉｎｔｈｅＷｉｄｅ

Ｗｅｂ

Ｗｅｂ［Ｃ］ｆｆｒｈｅ１６ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＷｏｒｌｄ

Ｃｏｎｆｅｒｅｎｃｅ。Ｃａｎａｄａ，Ｍａｙ８－１２２００７．ＵｎｉｔｅｄＳｔａｔｅｓ：Ａｓ－

复检验已发现Ｗｅｂ社区中非种子节点的入度和出度的繁琐。

ｓｏｃｉａｔｉｏｎｆｏｒＣｏｍｐｕｔｉｎｇＭａｃｈｉｎｅｒｙ．２００７：４６１—４７０．

（上接９７页）

的ＺｉｇＢｅｅ路由算法，改进算法在传统ＡＯＤＶｊｒ路由算法的基础上，结合ＺｉｇＢｅｅ树路由算法，对路由发现过程中的ＲＲＥＱ分组进行控制，并且在数据传输过程中考虑节点剩余能量，并且及

【２】ＢａｍｎｔＰ，ＰｉｌｌａｉＰ，ＣｈｏｏｋＶＷＣ．Ｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ：Ａ

ｏｎ

ｓｕｒｖｅｙ

ｔｈｅ

ｓｔａｔｅ

ｏｆｔｈｅ

ａｒｔ

ａｎｄｔｈｅ８０２．１５．４ａｎｄＺｉｇＢｅｅｓｔａｎｄ－ｓｔａｒｄｓ［Ｊ１．

Ｃｏｍｐｕｔｅｒ

Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ．２００７，３０（７）：１６５５—１６９５．

ｓｉｍｐｌｉｆｉｅｄ啊．Ｍｏｂｉｌｅ

【３】ＣｈａｋｅｒｅｓＩＤ，Ｋｌｅｉｎ－Ｂｅｍｄｔ．ＡＯＤＶｊｒ，ＡＯＤＶ

时对节点最小剩余能量值既．进行调整，有效地节约了网络整体耗能，并使得网络的能量消耗达到均衡。仿真结果表明，该算

法能有效地避开能量较低的节点进行数据的传输，节省了网络的总体能量消耗，延长了网络的寿命。但该算法没有考虑节点

ＣｏｍｐｕｔｉｎｇａｎｄＣｏｍｍｕｎｉｃａｔｉｏｎＲｅｖｉｅｗ。２００２，６（３）：１００－１０１．

［４１ＫｉｍＴ，Ｋｉｌｎ

Ｄ，ＰａｒｋＮ，ｅｔａ１．Ｓｈｏｒｔｃｕｔ

Ｉｒｅ—ｅ

ｒｏｕｔｉｎｇ

ｉｎ

ＺｉｇＢｅｅ

ｎｅｔｗｏｒｋ［ＥＢ／ＯＬ］．［２００８－０２－１６１．ｈｔｔｐ：／／ｒｅｓｌ．ｉｅｕ．ａｃ．ｋｒ／一ｄａｍｉａｎｏ／ｐｒｏｃ／

ｉｓｗｐｃ２００７＿１．ｐｄｆ．

【５】ＲａｎＰｅｎｇ，ＳｅｎＭａｏ－ｈｅｎｇ，ＺｏｕＹｏｕ—ｍｉｎ．ＺｉｇＢｅｅ

ｓｔｒａｔｅｇｙ

ｍｕｔｉｎｇｓｅｌｅｃｔｉｏｎ

ｒｏｌｌ－－

运动的情况，也没能提供对不同业务的ＱｏＳ支持，这些方面正

是未来的研究方向。

ｂａｓｅｄｏｎｄａｔａｓｅｒｖｉｃｅｓ

ａｎｄｅｎｅｒｇｙ－ｂａｌａｎｃｅｄ五ｇｂｅｅ

ｔｉｎｇ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２００６ＩＥＥＥＡｓｉａ—ＰａｃｉｆｉｃＣｏｎｆｅｒｅｎｃｅ

４００－４０４．

Ｏｉｌ

ｓｅｌｒｖｉｃｅｓＣｏｍｐｕｔｉｎｇ．ＷａｓｈｉｎｇｔｏｎＤＣ：ＩＥＥＥＣｏｍｐｕｔｅｒＳｏｃｉｅｔｙ，２００６：

参考文献：

【１】１

ｚｉｓＢｃｅＤｏｃｕｍｅｎｔ０５３４７４ｒ０６［Ｓ］．Ｖｅｍｉｏｎ１．０．Ｚｉ－ｇＢｃｅＡｌｌｉａｎｃｅ，２００４

【６】耿萌．ＺｉｇＢｅｅ路由协议研究【Ｄ１．郑州：解放军信息工程大学，２００６．

万方数据　

改进的ZigBee网络路由算法

改进的ZigBee网络路由算法

作者：作者单位：刊名：英文刊名：年，卷(期)：被引用次数：

班艳丽， 柴乔林， 王芳， BAN Yan-li， CHAI Qiao-lin， WANG Fang山东大学,计算机科学与技术学院,济南,250101计算机工程与应用

COMPUTER ENGINEERING AND APPLICATIONS2009,45(5)3次

参考文献(6条)

1.Ran Peng;Sen Mao-heng;Zou You-rain Zig,Bee routing selection strategy based ondata services andenergy-balanced zigbee routing 2006

2.Kim T;Kim D;Park N Shortcut tro-e routing in ZigBee network 20083.Chakeres I D;Klein-Berodt AODVjr,AODV simplified 2002(03)4.耿萌 ZigBee路由协议研究 2006

5.Baront P;Pillai P;Chook V W C Wireless sensor networks:A survey on the state of the art and the802.15.4 and ZigBee stand-stards[外文期刊] 2007(07)

6.ZigBee Document 053474r06 Version 1.0.Zi-gBee Alliance 2004

引证文献(4条)

1.吴凡.胡斌杰 数据融合算法在ZigBee网络中的应用研究[期刊论文]-计算机技术与发展 2011(2)2.李予东.黄宏光.向西西 基于能量均衡的ZigBee路由算法优化[期刊论文]-计算机工程与设计 2011(2)3.彭友.杨恢先.满莎 蚁群优化和能量管理的ZigBee网络路由[期刊论文]-计算机应用 2011(2)4.彭友.杨恢先.满莎 蚁群优化和能量管理的ZigBee网络路由[期刊论文]-计算机应用 2011(2)

本文链接：http:///Periodical_jsjgcyyy200905027.aspx