无线传感器网络中分布式广播算法研究

发布时间：2017-10-17 03:32

  本文关键词：无线传感器网络中分布式广播算法研究

  更多相关文章： 全局广播 SINR 分布式 异步无线网 确定性算法

【摘要】：广播是无线传感器网络中的基本问题之一,它的效率直接决定了许多高层应用和协议(如路由发现协议)的性能。根据所要广播的消息个数不同,可以将广播问题划分为单消息广播和多消息广播。在无线传感器网络中,无线通信往往受到干扰的影响,因此干扰建模对设计高效的网络协议是非常重要的。近年来,物理干扰模型得到了广泛应用。在物理干扰模型中,干扰随着距离的增加而减小并具有全局累加性特征,符合无线传感器网络的实际情况。现实中的无线传感器网络往往是一个分布式系统,因而设计高效的分布式广播算法更加具有现实意义。以往同步通讯模型下的分布式确定性单消息广播算法为了从逻辑上将整个网络进行网格划分,需要每个节点知道自己的坐标信息。这将产生如下两个问题,第一,算法执行的正确性和精确性在很大程度上取决于网络中节点位置的定位精度;第二,为部分或全部节点配备GPS(Global Position System)设备将会带来高成本和高能耗。此外,以往异步通讯模型下的分布式多消息广播算法采用的是基于图的干扰模型而不是更加符合实际的物理干扰模型。鉴于以上原因,本文研究基于物理干扰模型的无坐标依赖的分布式广播算法的设计,主要内容如下。(1)在同步通讯模型下,设计了两个基于标准物理干扰模型的分布式确定性单消息广播算法。第一个广播算法(the Time Efficient Global Broadcast,TEGB)首先从每一层节点中选取一个极大独立集,接着将该极大独立集划分为若干子集以实现广播消息最大程度的并发传输。理论分析表明,TEGB的时间复杂度为O(Dlogn),这里n表示节点总数,D为网络的直径。与Jurdzinski等人所提出的算法DetGenBroadcast相比,TEGB在时间性能上改进了一个对数因子。为了减少广播消息的冗余传播,提出了第二个广播算法(the Tree-Based Global Broadcast,TBGB)。算法TBGB可以构造网络的单向生成树,在该生成树中,只有非叶子节点需要转发广播消息。与TEGB相比,TBGB可以大大降低广播消息的冗余传播。理论分析表明,TBGB的时间复杂度为O(DΔlogn),这里Δ为最大节点度。仿真结果验证了以上的理论分析。(2)在异步通讯模型下,设计了基于扩展物理干扰模型的分布式多消息广播算法(the Distributed Asynchronous Multiple-message Broadcast,DAMB)。基于一个预先定义的传输骨干结构,算法DAMB可以在OckDn-+?+))]1(2([logτ时间内解决多消息广播问题,这里D表示网络中汇聚(sink)节点的离心率,k表示广播消息的个数,τ表示消息在信道中的传播时延,c是一个常数。当k=n时,算法DAMB的容量下界为??))8/1((Wc,这里W表示无线信道的带宽。注意,DAMB是扩展物理干扰模型下第一个分布式异步多消息广播算法。
【关键词】：全局广播 SINR 分布式 异步无线网 确定性算法
【学位授予单位】：曲阜师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP212.9;TN929.5
【目录】：

• 摘要3-4
• Abstract4-8
• 第1章 绪论8-13
• 1.1 研究背景及意义8-9
• 1.2 国内外研究现状9-11
• 1.2.1 基于图的干扰模型下广播问题的研究进展9-10
• 1.2.2 物理干扰模型下广播问题的研究进展10-11
• 1.2.3 异步通讯模型下广播问题的研究进展11
• 1.3 论文组织结构11-13
• 第2章 广播算法设计概述13-18
• 2.1 无线传感器网络建模13-14
• 2.2 广播算法模型14-15
• 2.2.1 干扰模型14-15
• 2.2.2 功率分配模型15
• 2.3 局部广播问题与全局广播问题15
• 2.4 广播算法分类15-17
• 2.4.1 同步广播算法和异步广播算法15-16
• 2.4.2 集中式广播算法和分布式广播算法16
• 2.4.3 随机广播算法和确定性广播算法16-17
• 2.5 本章小结17-18
• 第3章 SINR模型下的分布式确定性单消息广播算法研究18-41
• 3.1 网络模型和定义18-19
• 3.2 极大独立集子协议MMIS19-22
• 3.2.1 MMIS执行环境的建立20
• 3.2.2 MMIS的构造和性能分析20-22
• 3.3 时间高效的分布式确定性单消息广播算法TEGB22-31
• 3.3.1 广播图和层次划分22-24
• 3.3.2 TEGB算法设计24-26
• 3.3.3 TEGB算法性能分析及正确性证明26-31
• 3.4 基于树的分布式确定性单消息广播算法TBGB31-35
• 3.4.1 TBGB算法设计31-33
• 3.4.2 TBGB算法性能分析及正确性证明33-35
• 3.5 仿真设计35-39
• 3.5.1 仿真环境搭建35-36
• 3.5.2 仿真结果与分析36-39
• 3.6 本章小结39-41
• 第4章 扩展物理干扰模型下分布式异步多消息广播算法研究41-48
• 4.1 网络模型及相关定义41-42
• 4.2 骨干结构构造42-43
• 4.3 DAMB算法设计43-47
• 4.3.1 传输子协议44-45
• 4.3.2 DAMB理论分析45-47
• 4.4 本章小结47-48
• 第5章 总结与展望48-50
• 参考文献50-54
• 在读期间发表的学术论文及研究成果54-55
• 致谢55

【相似文献】

中国期刊全文数据库 前10条

1 韩秀苓，，程凡，高建林，李传光;管道自适应有源噪声控制算法[J];Journal of Beijing Institute of Technology(English Edition);1995年01期

2 陶新民;徐晶;童智靖;刘玉;;不均衡数据下基于阴性免疫的过抽样新算法[J];控制与决策;2010年06期

3 赵国峰;闫亮;;用于快速流分类的关键字分解Hash算法[J];计算机工程;2010年16期

4 郭雷勇;谭洪舟;高守平;郭笑梅;;RFID系统阅读器反碰撞算法分类与研究[J];计算机技术与发展;2009年09期

5 郝水侠,李凡长;多Agent的并行思智算法[J];计算机工程与应用;2004年10期

6 刘贝家;方景龙;;基于SVDD的多示例学习算法[J];科技通报;2011年02期

7 田大东;邓伟;;基于不同惩罚系数的SMO改进算法[J];计算机应用;2008年09期

8 许敏;王士同;顾鑫;;TL-SVM:一种迁移学习算法[J];控制与决策;2014年01期

9 李雅林;张化祥;张顺;;基于近邻加权及多示例的多标记学习改进算法[J];计算机工程与应用;2013年16期

10 罗玉华,李三立;RISC多发射结构中循环优化的软件流水算法[J];计算机学报;1993年09期

中国博士学位论文全文数据库 前10条

1 吴涛;粒子群及量子行为粒子群优化算法的改进研究[D];西南交通大学;2014年

2 徐勇;分布式压缩感知的算法及其应用研究[D];中国地质大学;2015年

3 蔡先发;基于图的半监督算法及其应用研究[D];华南理工大学;2013年

4 蒋良孝;朴素贝叶斯分类器及其改进算法研究[D];中国地质大学;2009年

5 李美安;普适分布式互斥算法及应用[D];电子科技大学;2007年

6 孙岩;贝叶斯网络结构学习算法研究与应用[D];大连理工大学;2010年

7 吴伟宁;主动学习算法中采样策略研究[D];哈尔滨工业大学;2013年

8 汪庆淼;基于目标函数的模糊聚类新算法及其应用研究[D];江苏大学;2014年

9 戴朝华;搜寻者优化算法及其应用研究[D];西南交通大学;2009年

10 李小冬;核极限学习机的理论与算法及其在图像处理中的应用[D];浙江大学;2014年

中国硕士学位论文全文数据库 前10条

1 李超;基于标签传播及适合度的社团聚类算法研究[D];西南大学;2015年

2 刘晨曦;RFID定位VIRE算法的研究与改进[D];贵州师范大学;2015年

3 马睿;利用岩石光谱和改进的PC算法实现矿物的识别[D];新疆大学;2015年

4 万猛;推荐系统攻击检测算法的研究[D];电子科技大学;2014年

5 刘排;基于OMNeT++的无线传感器网络节点定位改进算法的研究[D];河北工业大学;2015年

6 陈辰;无线通信领域MIMO检测类算法的硬件加速技术研究[D];国防科学技术大学;2013年

7 韩超;场景分类与道路场景异常识别算法研究[D];北京交通大学;2016年

8 董楠;行车热点中无监督聚类算法的研究与应用[D];东北大学;2014年

9 林玉琪;基于多智能体的数据流聚类算法研究[D];福州大学;2013年

10 曹鹏;基于Spark平台的聚类算法的优化与实现[D];北京交通大学;2016年

本文编号：1046579