无线传感器网络上的极值区域查询处理

提出了无线传感器网络上的一种查询——极值区域查询(peak region query,简称PRQ),即用户指定查询区域的大小和形状,例如半径为R的圆形区域,然后需要查询传感器网络中的某个区域,使得区域内传感器节点数据的某种聚集值最大.定义了极值区域查询的概念,并提出一种集中式算法以求解查询结果.由于传感器节点的能量有限,为了降低查询处理过程中的能耗,提出了分布式算法EXQ(an algorithm for extreme value query processing).与集中式算法相比,EXQ不但显著降低了能耗,而且使得每个传感器的能耗更加平均,从而延长了网络的使用寿命.EXQ的基本思想是,将整个网络划分为若干相互重叠的子区域,对每个子区域通过本地数据聚集得到一个本地结果,然后对这些结果再进行全局数据聚集从而得到查询结果.从理论和实验两方面分析和比较了集中式算法和EXQ的能耗和节点负载分布.

无线传感器网络高可靠低维护地理路由协议

无线传感器网络地理路由协议要求节点根据少量本地路由信息将数据分组传输路由到目标节点。为了消除路由环,地理路由算法通常需要将网络拓扑平面化。然而现有的平面化算法要么假设节点的通信半径是一固定值,在实际应用中不适用;要么对每一条链路都进行检测是否有交叉链路,路由维护代价很高。针对以上问题,提出一种具有高可靠性和低维护成本的地理路由协议RPR(region partitioning-based routing),其基本思想是将网络划分为规则多边形区域,并在贪心路由失败时将多边形区域内的所有节点看作一个虚拟节点进行周边路由。多边形区域间通信能够降低平均路由路径长度,从而提高了路由的可靠性。基于区域划分的网络平面化策略不需要检测和删除相交链路,因此减少了路由维护开销。模拟实验结果显示,RPR协议比现有方法的平均路由路径长度更短,路由维护开销更低。

无线传感器网络分布式单向链路检测算法

针对在存在单向链路的网络中如何检测单向链路和如何利用单向链路的问题，提出了3种分布式算法。这3种算法的基本思想是通过Beacon数据包交换一部分链路信息帮助发现单向链路。实验结果显示，使用提出的分布式链路检测算法可以将路由路径的平均长度减少37．8％～39．24％，路由层平均数据发送成功率提高23．82％。模拟实验表明，提出的分布式单向链路检测算法具有很好的可扩展性。

无线传感器网络诊断工具的可视化方法研究

在开发和部署无线传感器网络应用过程中,如何对网络运行状态进行诊断是一个重要的问题.现有的诊断方法包括仿真、模拟、日志分析和跟踪程序等等.在诊断过程中,诊断工具的分析过程和网络状态的可见性对于用户判断诊断结果是否准确至关重要,而这恰恰是传统诊断工具的弱项.因此探讨了无线传感器网络诊断工具的可视化方法所面临的挑战和解决方案.在研发的可视化诊断工具TinyD2的框架内,提出了两项关键技术:1)可视化诊断工具通过实时接收网络传回的数据建立知识表示模型,实现网络特征的动态添加和删除;2)基于虚拟引力-斥力设计网络逻辑拓扑的动态生成算法,实时展示网络运行状态;通过基于真实大规模传感网系统GreenOrbs数据集的评估验证,提出的技术可以辅助用户进行无线传感器网络的故障定位和故障检测,并极大地减少了用户理解网络传回数据的复杂认知工作.

在Cache替换策略中的XPath Fragment包含算法

在基于查询的XML cache环境中,查询包含算法对于cache替换策略的性能来说是很重要的。XML查询通常用XPath表达式来表达,XPath表达式等价于树模式。本文研究了Xpath查询语言片段的包含问题,实际上我们研究了树模式的一个特殊例子,证明了一个模式包含的声音和完全的PTIME算法。我们也分析了它的时间复杂度,实验结果也证实了我们的分析。