室内无线传感器网络中转发节点的最优放置问题研究
Optimal Relay Placement for Indoor Sensor Networks
无线传感器网络已经被非常广泛的使用在了各种不同的环境下,为多种多样的有用的应用设施提供技术支持.无线传感器网络的一个典型的特征就是用低能耗和低价格的无线传感器节点来实现尽可能稠密的部署,也就是说使覆盖范围尽可能的大.对于许多传感器网络来说,应用的健壮性就是依靠合理的部署转发节点来确保无线信号的覆盖率来实现的.为了保证拥有对感知的数据在无线传感器节点和终端之间有高效率的通信质量,在确保一定覆盖范围的同时还要保证节点之间的连通性性.有时为了获取这种互联性,仅仅凭借无线传感器节点本身是不够的,还需要加入一个辅助的节点,用来专门转发无线传感器节点之间的信息,这种节点成为转发节点.这些转发节点的加入使得整个网络在减少能量消耗的同时也延长了系统的寿命.因为转发节点的重要性,所以我们需要决定以何种合适的方式布置这些无线传感器节点和转发节点.这篇文章考虑了一个重要的问题,在室内环境下,转发节点的最优放置问题.解决这个问题对于这样一个无线传感器网络的管理来讲是有重大意义的.现在,很多算法已经被大家提出以确保无线感知范围的全覆盖和网络的连通性.这些现存的算法被应用于室内环境中时非常困难的,原因在于室内的环境和室外相比,情况是相当复杂的.因为在室内环境时,无线电信号会非常严重的被室内的障碍物造成衰减,例如,室内的墙壁、桌子、书架等等.研究的主要内容是对于一个给定的环境来说,一个无线传感器网络如何实现最优的传递节点的布置方式的问题.这个问题非常具有现实意义.研究问题的目标是使用最小数量的转发节点,同时使已经被布置到环境中的无线传感器节点能够尽可能多的与至少一个转发节点进行通信,并与此同时保证转发节点的连通性.也就是说,我们希望环境中的无线传感器节点的感应收集到的消息能够尽可能多的有转发节点进行转发,从而能够被其他需要这些消息的节点收集到.通过这种方式,对于任意的无线传感器节点的部署方式,都应该满足大多数的无线传感器节点都至少能够与一个转发节点进行通信.与此同时保证各个转发节点之间的连通性也是非常重要的,连通性使得这些转发节点之间能够相互通信,这是确保被感知的消息能够成功在网络中进行传播的必要途径.我们第一次从理论上系统的证明了室内的中继节点放置问题是NP难的问题.之后,我们又提出了对于一个室内环境下已经部署好的中继节点,如何预测它的无线电波的覆盖范围.在这里,我们一共考虑了两种可实践的场景:第一种是有线连接的中继节点场景:第二种是无线连接的中继节点场景.顾名思义,第一种场景中,中继传感器节点通过有线介质相互连接,从而达到可以连通的目标.第二种场景中,中继传感器节点互相在彼此的无线电波覆盖范围内,所以可以通过无线电波与其他中继节点进行通信,从而达到预期的连通目标.我们在文章中提出一个效率很高的启发式贪心算法,这个算法以确保预期的信号覆盖质量的前提下计算出部署这些中继无线传感器节点的放置位置.
- 作者：
- 薛粹瑶
- 学位授予单位：
- 上海交通大学
- 专业名称：
- 计算机应用技术
- 授予学位：
- 硕士
- 学位年度：
- 2013年
- 导师姓名：
- 李明禄
- 中图分类号：
- TP212.9；TN929.5
- 关键词：
- 传感器网络；转发节点；室内环境；最优放置；近似算法
- Sensor networks；relays；indoor environment；optimal placement；approximation algorithms