基于超图模型和相继干扰消除的链路调度问题的研究

发布时间：2020-08-26 17:01

【摘要】：随着无线技术的快速发展和日益成熟,无线传感器网络的应用已经从军事领域步入了人们的日常生活,给我们的生活带来了翻天覆地的变化。与有线网络相比,无线网络共享信道的特性使得无线传感器网络中的数据传输通常由于不同数据之间的相互冲突而失败,因此我们不得不重新传输这些冲突的数据以便能使目的节点正确接收所需信息。这也降低了网络的吞吐量。通过适当的链路调度策略减少网络中数据的冲突是提高网络吞吐量的有效方法之一。无线网络中的链路调度按照调度目的可以简单分为最大链路调度问题(Maximum Link Scheduling Problem,MaxLSP)和最短链路调度问题(Shortest Link Scheduling Problem,SLS)。前者目标是给定一个链路集合1 2{,,...,}nL?l l l,计算最大可能的链路子集合S?L使得当集合中的链路同时调度时它们相互之间不发生冲突。后者的目标是在尽可能短的时间内调度网络中需要调度的所有链路。本文在分析现有工作的基础上,对于最短链路调度问题,我们分别利用超图模型和相继干扰消除(Successive Interference Cancellation,SIC)改进了现有的算法,通过理论和仿真,我们证明了改进后的算法与已存的算法相比在调度长度上有较好的性能;对于最大链路调度问题,利用SIC的特性,我们同样改进了已有的算法,通过理论和仿真,我们给出了改进后算法与已有算法的性能之比。本文共包含5章。在第1章中我们简单的介绍了无线传感器网络的概念、常见应用领域和本文选题的意义。在第2章中我们介绍了研究链路调度算法时经常用的模型以及在本文中所用的术语及相关定义。第3章对于最短链路调度问题,在总结已有算法的基础上,我们结合功率分配在SINR模型和超图模型下,改进了一个已有的算法。我们在这一章中给出了改进后算法正确性、调度长度、时间复杂度、与已有算法在调度长度上的近似比等证明,在这一章的最后我们给出了仿真验证。第4章,对于最短链路调度问题结合前一章中对于该问题的研究,利用SIC技术我们提出了另外一个改进后的算法,对于最大链路调度问题,通过使用SIC,我们改进了已有的算法。在这一章中,我们从理论上证明了改进后算法的正确性、有效性,并且通过仿真对该算法进行了验证。在第5章中,我们总结了本文所研究的最短链路调度和最大链路调度问题,并对于下一步将要进行的工作进行了展望。
【学位授予单位】：曲阜师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TN929.5;TP212.9
【图文】：

图 3-1 当 3， 2时， 对调度结果的影响图 3-1 为 3,4,5； 取值为 3； 取值为 2 时的仿真结果。从图 3-1（a）-3-1（c）中可以看出pcSLS 在调度长性能上比 GOW *和GOW 性能好。随着 的增加，这些算法调度完部署区域中所有链路所需要的时隙数都有所减少。同样，随着网络中链路条数的逐渐增多，pcSLS 的调度时隙数的增长幅度小于 GOW *和GOW 。若 取固定值，pcSLS 在调度长度上的性能将比 GOW *和 GOW 好。当 取0,1/ 2,1等不同值时，pcSLS 有相似的性能。

当3，4，0时，对调度结果的影响

4尹=3，}=4.P=0时何消耗

【相似文献】

相关期刊论文 前10条

1 刘文涛,张群,孙肃清;关于炼钢厂重调度问题的研究[J];冶金自动化;2004年06期

2 张居阳 ,礼欣 ,孙吉贵;基于约束的调度研究和实现[J];计算机工程与应用;2004年33期

3 刘琳;谷寒雨;席裕庚;;工件到达时间未知的动态车间滚动重调度[J];机械工程学报;2008年05期

4 黄峰;丁亚武;;人机协同模式下的手工调度技术研究[J];黑龙江科技信息;2011年35期

5 郭艳东;黄敏;王庆;;锁定初始调度的紧急工作单机重调度问题[J];东北大学学报(自然科学版);2013年05期

6 姜洋;孙伟;丁秋雷;张旭;;考虑行为主体的单机调度干扰管理模型[J];机械工程学报;2013年14期

7 李向军,王书振;网络化集成制造模式下调度问题的混合遗传算法[J];西安联合大学学报;2002年04期

8 王中杰,吴启迪,有杰;基于多目标的半导体生产线满意调度[J];控制与决策;2002年06期

9 李云峰;凌晓冬;武小悦;;调度问题中的冲突研究[J];兵工自动化;2007年06期

10 徐群岭;;基于免疫优化的公交驾驶员调度问题[J];计算机工程;2010年24期

相关会议论文 前10条

1 李建更;涂凍生;马海涛;;单机拖后时间总和问题交付期扰动时最优调度不变范围的一种求法[A];第十九届中国控制会议论文集（一）[C];2000年

2 刘海龙;黄小原;;总的未完工费用最小的多机调度问题[A];1995中国控制与决策学术年会论文集[C];1995年

3 沈吟东;曾西洋;;公共交通驾驶员调度的复杂性及解决方法[A];’2004计算机应用技术交流会议论文集[C];2004年

4 李兵;蒋慰孙;;Job shop问题的建模及调度[A];1996中国控制与决策学术年会论文集[C];1996年

5 王海星;申金升;;智能蚁群算法解决公交区域调度问题研究[A];2006年首届ICT大会信息、知识、智能及其转换理论第一次高峰论坛会议论文集[C];2006年

6 王成尧;汪定伟;;模糊加工时间的单机调度问题[A];1996中国控制与决策学术年会论文集[C];1996年

7 齐向彤;涂奉生;;双交付期E／T调度问题[A];1997年中国控制会议论文集[C];1997年

8 吴斌;方叶祥;崔志勇;;基于人工蜂群算法的越库调度问题研究[A];第25届中国控制与决策会议论文集[C];2013年

9 方涛;吴受章;;FMS的自适应调度:结构与算法研究[A];1992年中国控制与决策学术年会论文集[C];1992年

10 刘兴初;赵千川;郑大钟;;具有不同准备时间和交付期的单机E／T调度问题研究[A];1998年中国控制会议论文集[C];1998年

相关重要报纸文章 前2条

1 本报记者 贾科华;火电机组叫苦调度不合理[N];中国能源报;2012年

2 本报记者 高芳;牵住“牛鼻子” 巧解“推进难”[N];湖南经济报;2008年

相关博士学位论文 前10条

1 郭鹏;具有分段恶化效应生产过程的智能优化调度研究[D];西南交通大学;2014年

2 元野;基于图着色模型的零担物流调度优化问题研究[D];哈尔滨工业大学;2015年

3 左燕;大规模复杂生产调度问题瓶颈分解方法研究[D];上海交通大学;2007年

4 王磊;OKP企业分散式项目计划与调度优化方法研究[D];哈尔滨工业大学;2013年

5 李小林;平行机环境下批处理机调度问题研究[D];中国科学技术大学;2012年

6 金毅;模糊集合论在生产计划和调度中的应用研究[D];东南大学;1994年

7 李玉庆;动态不确定环境下航天器观测调度问题研究[D];哈尔滨工业大学;2008年

8 刘志雄;调度问题中的粒子群优化方法及其应用研究[D];武汉理工大学;2005年

9 汤健超;基于混合进化算法的若干调度问题研究[D];华南理工大学;2012年

10 江维;任务关键实时系统的可信感知调度研究[D];电子科技大学;2009年

相关硕士学位论文 前10条

1 张亮;云计算环境下的资源调度技术的研究[D];江南大学;2015年

2 冯卓鹏;重载运输卸车组织优化研究[D];西南交通大学;2015年

3 崔雪源;基于遗传模拟退火算法的航班着陆调度问题[D];华中师范大学;2015年

4 王翠;基于超图模型和相继干扰消除的链路调度问题的研究[D];曲阜师范大学;2015年

5 张勇;带拒绝和释放时间的单机批调度问题[D];山东大学;2015年

6 吴凡;基于粒子群优化算法的风电-火电机组组合调度研究[D];华北电力大学;2015年

7 赵虎;MTO模式下的制造企业稳健型调度问题研究[D];重庆理工大学;2015年

8 鲍和映;航空公司不正常航班调度研究[D];南京航空航天大学;2013年

9 羊晓飞;基于场景和模糊描述的不确定Job Shop鲁棒调度[D];山东大学;2009年

10 王建波;基于综合利益最优的集成调度优化模型应用研究[D];大连交通大学;2010年

本文编号：2805448