无线传感器网络中若干资源共享问题的研究

论文摘要

无线传感器网络是由具有一定计算及无线通信能力的传感器节点和用于收集数据的sink节点所组成的无线自组织网络系统。近年来,随着人们对无线传感器网络研究的不断深入、对其在各种应用领域的不断实践,为无线传感器网络的大规模部署提供了理论依据并积累了宝贵的经验。在无线传感器网络各种可行的网络结构中,带有多移动sink的网络结构尤其适合大规模无线传感器网络部署。在这种网络结构中,移动sink可以充当传统意义上的数据收集者对数据进行保存、处理并提供给更高级的应用。从另一方面,无线传感器网络的最终用户也可以直接访问传感器节点从而可以被看作为多个移动sink。这种情况下各个用户之间通常没有逻辑上的直接联系,它们需要共享网络所提供的数据。无论哪种情况,在多个移动sink之间提供公平性都具有重要意义。本文将围绕该主题展开讨论,对带有多sink的无线传感器网络中的若干公平性问题进行定义,并通过理论模型对这些问题进行分析进而提出解决它们的方法。本文工作将包括以下几个方面:（1）对使用圆盘形请求范围的多sink无线传感器网络,利用一种基于密集节点假设的基于流的数据流量模型对sink效用的max-min公平性问题进行讨论。在该网络模型下,sink所能够取得的最大请求范围受限于网络节点的无线数据传输带宽。因此sink与节点之间必须相互协调以使多个sink获得公平的请求范围。本文通过理论分析给出一种简单的双sink网络情况下的max-min公平请求范围表达式,并提出一种可以部署于sink及传感器节点上的分布式算法用于近似求解多sink情况下的max-min公平性问题。对算法的仿真实验证明了其有效性并揭示了网络工作于max-min公平请求时的一些问题。（2）仿真实验发现,max-min公平请求状态下网络利用率较低。而且通常情况下,公平性与效率之间存在矛盾,不能二者兼顾。该现象是否也存在于带有多移动sink的无线传感器网络中?本文将使用网络覆盖作为网络利用率的衡量指标对此进行研究。实际上,通过对双sink情况的理论分析,max-min公平请求范围仅在某些情况下可以取得最大网络覆盖;而在多sink情况下的仿真实验表明存在不同于max-min公平请求的其它请求配置可以取得更大的网络覆盖。（3）使用基于跳数的请求模型对多sink的公平性进行研究。此时,sink请求范围的离散取值使得在某些情况下max-min公平请求并不存在。因此必须使用基于字典序的max-min公平性代替通常的max-min公平性对多sink公平性问题进行研究。本文发现,基于字典序的max-min公平性问题可以利用多维多选择背包问题予以描述。除此之外,多维多选择背包问题通常所使用的全局效用优化目标恰好适合描述多sink无线传感器网络中的最大化sink效用问题。结合二者,本文提出了适合两种优化目标的统一的问题描述,该描述也可以用于多sink无线传感器网络中的其它优化问题。基于该统一描述,本文提出了用于近似求解两种优化问题的分布式算法框架。用于不同优化目标的具体算法可以很容易被纳入该算法框架从而极大简化网络的实际部署。大量的仿真实验表明所提出的算法可以取得相关优化问题较好的近似解。所重点讨论的两种优化目标对网络所产生的影响也通过仿真结果得到反映。（4）为了支持用户（sink）在无线传感器网络内自由移动,本文在假设使用基于地理位置的路由的基础上,对三种基本的sink位置更新机制进行研究:邻居更新、洪泛更新、单播更新进行研究,并推导出三种方式的控制流量及能量消耗表达式。通过分析和比较各种方式在不同网络环境下的性能,我们提出了一种自适应更新方式选择算法,使得移动sink可以根据业务数据流量、网络规模、网络密度选择高效的方式对网络节点进行位置更新。本文通过大量仿真对三种位置更新方式以及自适应选择算法的性能进行评估,并与TTDD协议进行比较,结果证明所提出的自适应选择算法能够根据不同的网络状态选择合适的更新方式完成位置更新并降低网络能耗。该机制适用于使用地理位置路由协议的网络并可以被用于前述各个网络模型中支持移动用户。本文讨论的重点将限于无线传感器网络。然而,相关问题可以被扩展到其它大规模异构网络,例如无线网状网（Wireless MeshNetworks）或覆盖网（Overlay Networks）。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第一章 绪论
• 1.1 无线传感器网络研究现状
• 1.1.1 基础服务
• 1.1.2 网络通信协议
• 1.2 无线传感器网络应用及结构演进
• 1.2.1 应用场景举例
• 1.3 论文选题背景及意义
• 1.4 论文内容提要及结构安排
• 第二章 多SINK无线传感器网络资源共享的公平性研究
• 2.1 简介
• 2.2 网络模型
• 2.3 双sink情况的理论分析
• 2.4 适用于多sink情况的算法
• 2.4.1 Max-min公平配置的贪婪算法
• 2.4.2 双sink情况的启发
• 2.4.3 分布式max-min公平算法
• 2.5 算法的仿真评估
• 2.5.1 仿真环境及参数
• 2.5.2 网络带宽利用率
• 2.5.3 请求半径
• 2.6 相关工作
• 2.7 本章结论
• 第三章 MAX-MIN公平配置下的网络利用率研究
• 3.1 简介
• 3.2 网络模型
• 3.3 网络拥塞条件
• 3.4 请求覆盖与网络利用率
• 3.5 请求覆盖的最优性分析
• 3.5.1 第一种情况
• 3.5.2 第二种情况
• 3.5.3 第三种情况
• 3.5.4 第四种情况
• 3.5.5 四种情况小节
• 3.6 多sink情况下max-min公平配置的最优性
• 3.6.1 UNFAIR算法
• 3.7 仿真研究
• 3.7.1 仿真环境及参数
• 3.7.2 请求覆盖
• 3.7.3 网络带宽利用率
• 3.8 本章结论
• 第四章 基于本地流量模型的多访问点资源分配
• 4.1 简介
• 4.1.1 本章主要贡献
• 4.2 相关工作
• 4.3 本地流量模型
• 4.4 问题描述
• 4.4.1 MMKP相关问题简介
• 4.4.2 广义MMKP描述
• 4.4.3 MNU问题的MMKP描述
• 4.4.4 MMF问题的MMKP描述
• 4.5 基于MMKP的MNU问题复杂度
• 4.6 算法设计
• 4.6.1 一种用于MMF问题的确切算法
• 4.6.2 适用于MNU和MMF问题的分布式算法
• 4.7 算法的仿真评估
• 4.7.1 确切算法的时间复杂度
• 4.7.2 分布式启发算法在大规模网络中的性能
• 4.7.3 动态网络实例
• 4.8 本章结论
• 第五章 无线传感器网络中移动SINK位置更新机制
• 5.1 简介
• 5.2 相关工作
• 5.2.1 基于地理位置的路由简介
• 5.2.2 位置更新机制
• 5.3 分析模型
• 5.4 位置更新方式
• 5.5 能量消耗与时延分析
• 5.5.1 NUPD方式下的能量消耗
• 5.5.2 FUPD方式下的能量消耗
• 5.5.3 UUPD方式下的能量消耗
• 5.5.4 NUPD方式下时延分析
• 5.6 位置服务
• 5.6.1 位置更新算法
• 5.7 算法的仿真评估
• 5.7.1 仿真模型及比较参数
• 5.7.2 网络负载和网络规模对算法的影响
• 5.7.3 sink移动速度对算法性能的影响
• 5.7.4 平均路径长度
• 5.8 本章结论
• 第六章 结束语
• 6.1 后续研究方向
• 参考文献
• 缩略语
• 致谢
• 个人简历及参加的科研项目
• 攻读学位期间发表的学术论文