学位论文 > 优秀研究生学位论文题录展示

图论在计算机和无线传感器网络中的应用

作　者: 杨裔
导　师: 李廉；李皓
学　校: 兰州大学
专　业: 应用数学
关键词: 并行计算机容错适应性路由无线传感器网络网络延迟启发式算法移动物体跟踪网格计算数学网络计算环境
分类号: TN929.5;TP212.9
类　型: 博士论文
年　份: 2009年
下　载: 511次
引　用: 0次
阅　读: 论文下载

内容摘要

计算机的诞生彻底改变了人类的计算历史,它以强大,高速,精确计算能力,深入现代生活、生产以及科研的各个领域,扮演着非常重要的角色,可以说计算机的发展正在推动着整个社会的进步。本论文使用图论基础理论和建模方法对现代计算机三个主流体系结构,分别是并行计算机,无线传感器网络以及网络计算的相关热点问题进行探讨。本论文总共包括五章,三个主题,其中第二章和第三章是围绕以网格网络作为拓扑结构的并行计算机节点间容错适应性路由这个主题展开的,第四章讨论无线传感器网络中跟踪移动物体产生数据的多基站实时路由问题,第五章提出了一个基于网格技术的数学网络计算模型。前两个主题是2007年到2009年在法国巴黎第十一大学完成的内容,第三个是2005年到2007年在兰州大学完成的。论文的第二、三章主要研究网格网络中容错自适应路由问题,在该问题上结合传统模型提出了一个新的模型,及其相应的路由算法。通过在传统的容错块内部构建生成树,消息数据包可以通过这些内部的生成树被路由到容错块内部,这样就保证了只要节点与网络是保持连通的,那么消息一定可以送达到该节点,保证了网络中节点的最大化利用。容错块的构建方法简单容易实现,并且构建过程完全是自主的,可以根据网络的实时状态调整容错块的规模,当容错块中的节点恢复正常,不需要停机重启机器,容错块可以自行消失,显著提高了并行计算机的整体性能。第四章介绍了一种无线传感器网络的新应用,即无线传感器网络中跟踪移动物体时产生数据的多基站实时路由问题,该问题在文章中被证明是NP完全的,并且提出三种启发式算法来解决不同的应用需求,最短路径路由主要用来满足路由的延迟限制,最大利用率路由用来满足网络节能的要求,而最后一种激活优先路由权衡考虑延迟限制和网络节能,通过模拟实验和理论分析得出,其中激活优先算法不仅可以满足延迟限制而且能够获得较好的节能效果。可以适用于无线传感器网络中对跟踪移动物体所产生数据进行多基站路由。最后一章介绍了一种基于网格技术的数学网络计算环境,通过该环境可以集成地域上分布离散的各种数学资源,数学软件,并且提供统一的访问方式和编程语言。有效提高了数学科研工作者的工作效率,减少对各种数学资源重复学习的负担,提高了数学软件和数学服务的利用率。

全文目录

摘要  3-5
Abstract  5-9
目录  9-16
第一章引言  16-47
  1.1 并行计算机  26-38
    1.1.1 并行计算机体系结构  27-33
    1.1.2 并行计算机节点间的消息路由  33-38
  1.2 无线传感器网络  38-45
    1.2.1 路由算法  42-45
  1.3 网格计算  45-47
第二章二维网格中的自适应容错路由  47-64
  2.1 引言  47-49
  2.2 二维网格中的无故障路由  49-51
    2.2.1 二维网格的一些基本定义  49-50
    2.2.2 二维网格中的无故障路由  50-51
  2.3 二维网格中的容错自适应路由  51-60
    2.3.1 二维网格中故障块的形成  52-57
    2.3.2 二维网格中裂痕故障块的形成  57-58
    2.3.3 二维网格中的容错自适应路由  58-60
  2.4 裂痕故障块模型的可实现性  60-64
第三章多维网格中的自适应容错路由  64-79
  3.1 多维网格的无故障路由  64-67
    3.1.1 多维网格的一些基本定义  64-65
    3.1.2 多维网格的无故障路由  65-67
  3.2 多维网格的容错自适应路由  67-77
    3.2.1 多维网格中故障块的形成  67-68
    3.2.2 多维网格中裂痕故障块的形成  68-69
    3.2.3 多维网格的容错自适应路由  69-77
  3.3 裂痕故障块模型的可实现性  77-79
第四章无线传感器网络中跟踪移动目标的多基站数据路由  79-100
  4.1 引言  79-81
  4.2 相关工作  81-82
  4.3 问题定义  82-88
    4.3.1 假设  82-83
    4.3.2 定义  83-86
    4.3.3 问题的复杂度  86-88
  4.4 算法  88-92
    4.4.1 Dijkstra's最短路径路由算法  88
    4.4.2 启发式算法  88-92
  4.5 结果和分析  92-100
    4.5.1 模拟设置  92-93
    4.5.2 Metrics  93-95
    4.5.3 Tradeoff  95
    4.5.4 不同的基站数量  95-97
    4.5.5 不同的能量单位  97-100
第五章数学网络计算环境  100-115
  5.1 背景介绍  100-102
  5.2 相关工作  102-103
  5.3 CSP的体系结构  103-104
  5.4 CSP的设计与实现  104-113
    5.4.1 系统数学描述语言规范  104-106
    5.4.2 解析器的设计  106-108
    5.4.3 解释器的设计  108-110
    5.4.4 WFLM(Web Function List Management)的设计  110
    5.4.5 Mbottle的设计  110-113
  5.5 总结  113-115
参考文献  115-125
发表文章及已完成文章目录  125-128
致谢  128

图论在计算机和无线传感器网络中的应用

内容摘要

全文目录

相似论文