基于动态规划的矿井无线再编程最优基站选址算法

韩江洪; 段章领; 卫星; 陆阳; 张建军

doi:10.11959/j.issn.1000-436x.2017069

您当前的位置：

首页 >

文章列表页 >

基于动态规划的矿井无线再编程最优基站选址算法

学术论文 | 更新时间：2024-06-05

- 基于动态规划的矿井无线再编程最优基站选址算法
- Optimal base station selection based on dynamic programming for reprogramming in mine wireless network
- 通信学报 2017年38卷第3期页码：7-15
- 作者机构：
  
  1. 合肥工业大学计算机与信息学院，安徽合肥 230009
  2. 安全关键工业测控技术教育部工程研究中心，安徽合肥 230009
- 作者简介：
  
  [ "韩江洪（1954-），男，安徽庐江人，合肥工业大学教授、博士生导师，主要研究方向为网络与通信、嵌入式系统、无线网络等。" ]
  [ "段章领（1990-），男，安徽颍上人，合肥工业大学博士生，主要研究方向为无线网络优化、安全关键通信协议。" ]
  [ "卫星（1980-），男，安徽肥西人，合肥工业大学副教授、硕士生导师，主要研究方向为物联网工程、离散事件动态系统。" ]
  [ "陆阳（1967-），男，安徽合肥人，合肥工业大学教授、博士生导师，主要研究方向为安全关键工业测控技术、离散事件控制系统理论与应用、自组织网络理论与应用、二进神经网络理论与应用。" ]
  [ "张建军（1963-），男，浙江宁波人，合肥工业大学教授、硕士生导师，主要研究方向为汽车电子、物联网工程、计算机集成制造。" ]
- 基金信息：
  
  国家重点研发计划专项基金资助项目(2016YFC0801804);国家国际科技合作专项基金资助项目(2014DFB10060)
- DOI：10.11959/j.issn.1000-436x.2017069
  中图分类号： TP301
- 网络出版日期：2017-03，
  
  纸质出版日期：2017-03-15
- 稿件说明：
移动端阅览
韩江洪, 段章领, 卫星, 等. 基于动态规划的矿井无线再编程最优基站选址算法[J]. 通信学报, 2017,38(3):7-15.

Jiang-hong HAN, Zhang-ling DUAN, Xing WEI, et al. Optimal base station selection based on dynamic programming for reprogramming in mine wireless network[J]. Journal on communications, 2017, 38(3): 7-15.
韩江洪, 段章领, 卫星, 等. 基于动态规划的矿井无线再编程最优基站选址算法[J]. 通信学报, 2017,38(3):7-15. DOI： 10.11959/j.issn.1000-436x.2017069.

Jiang-hong HAN, Zhang-ling DUAN, Xing WEI, et al. Optimal base station selection based on dynamic programming for reprogramming in mine wireless network[J]. Journal on communications, 2017, 38(3): 7-15. DOI： 10.11959/j.issn.1000-436x.2017069.

摘要

广泛应用于安全关键系统的大规模无线网络需动态更新节点程序，采用无线再编程方式进行程序更新，具有高效性及灵活性。研究在节点均匀分布的矿井无线传感器网络环境下，如何选取最优的基站使整个网络再编程代价最小。首先由网络节点程序更新的接力覆盖过程推导出基站选址模型，其次将其转化为求解连通简单图任意节点不循环最长最短通路的最小值问题，最后给出基于动态规划的最优算法，包括最优子结构和重叠子问题。数值结果表明，与其他最优算法相比，该算法在网络复杂度急剧增大时仍保持平稳的时间消耗。

Abstract

The nodes of large-scale wireless network which widely used in safety-critical systems often update new code

the way of wireless reprogramming is efficiency and flexibility.The problem of selecting the optimal base station when nodes uniformly distributed in mine wireless network environment and all other nodes were reprogrammed efficiency.Firstly

the model of base station selecting was established by covering process of reprogramming.Then the problem was transformed into solving the minimum of longest non-cyclic path between node and base station in undirected circulant graph.Finally

the optimal algorithm based on dynamic programming which included optimal substructure and overlapping subproblems was proposed.Numerical analysis and experimental results show that the time consumption of proposed algorithm is more stable than other optimal algorithm when the complexity of network is increased sharply.

关键词

Keywords

references

NANDU P , SHEKOKAR N . An enhanced authentication mechanism to secure re-programming in WSN [C ] // International Conference on Advanced Computing Technologies and Applications . Mumbai,INDIA , 2015 : 397 - 406 .

SHIM K A,KYUNG-AH . (SDRP)-D-2:Secure implementations of distributed reprogramming protocol for wireless sensor networks [J ] . Ad Hoc Networks , 2014 , 19 ( 8 ): 1 - 8 .

卫星 , 张芳荣 , 段章领 , 等 . 基于模拟煺火的无线传感节点再编程策略 [J ] . 仪器仪表学报 , 2015 , 36 ( 3 ): 538 - 544 .

WEI X , ZHANG F R , DUAN Z L , et al . Simulated annealing based reprogramming scheme of wireless sensor nodes [J ] . Chinese Journal of Scientific Instrument , 2015 , 36 ( 3 ): 538 - 544 .

方效林 , 高宏 , 李建中 . 一种基站可移动传感器网络再编程协议 [J ] . 电子学报 , 2013 , 41 ( 5 ): 1007 - 1011 .

FANG X L , GAO H , LI J Z . MovPro:data dissemination for reprogramming in wireless sensor network with mobile sink [J ] . Acta Electronica Sinica , 2013 , 41 ( 5 ): 1007 - 1011 .

王珂 . 矿井无线传感器网络节点部署关键技术的研究 [D ] . 中国矿业大学 , 2011 : 49 - 62 .

WANG K . Research on key technologies of mine wireless sensor networks node deployment [D ] . China University of Mining and Technology , 2011 : 49 - 62 .

PRADIP D , LIU Y H , SAJAL K D . Energy-efficient reprogramming of a swarm of mobile sensors [J ] . IEEE Transaction on Mobile Computing , 2010 , 9 ( 5 ): 703 - 718 .

SEUNGKU K , DOO S E . Dynamic transmission power control for wireless sensor network reprogramming [C ] // The 17th Asia-Pacific Conference on Communications (APCC) . 2011 : 145 - 150 .

DONG C C , YU F Q . An efficient network reprogramming protocol for wireless sensor networks [J ] . Computer Communications , 2015 , 55 ( 10 ): 41 - 50 .

GAREY M R , JOHNSON D S . Computers and intractability:a guide to the theory of NP-completeness [M ] . New York : FreemanPress , 1979 : 245 - 248 .

J LUO , J P HUBAUX . Joint mobility and routing for lifetime elongation in wireless sensor networks [C ] // The 24th Annual Joint Conference on Computer and Communications Societies (INFOCOM) . 2005 : 1735 - 1746 .

WANG J , URRIZA P , HAN Y , et al . Weighted centroidlocalization algorithm:theoretical analysis and distributed implementation [J ] . IEEE Transaction on Wireless Communication , 2011 , 10 ( 10 ): 3403 - 3413 .

HOU Y T , SHI Y , SHERALI H D . Optimal base station selection for anycast routing in wireless sensor networks [J ] . IEEE Transactions on Vehicular Technology , 2006 , 55 ( 3 ): 813 - 821 .

SHI Y , HOU Y T . Optimal base station placement in wireless sensor network [J ] . ACM Transactions on Sensor Networks , 2009 , 5 ( 4 ): 2855 - 2869 .

JIAN P P , LIN C Y , HOU T . Optimal base-station locationsin twotiered wireless sensor networks [J ] . IEEE Transactions on Mobile Computing , 2005 , 4 ( 5 ): 458 - 473 .

LIANG W , LUO J , XU X . Prolonging network lifetime via a controlled mobile sink in wireless sensor networks [C ] // GLOCOM . Miami Florida,USA , 2010 : 1 - 6 .

THANIGAIVELU K , MURUGAN K . Impact of sink mobility on network performance in wireless sensor networks [C ] // NETCOM . Chennai ,India , 2009 : 7 - 11 .

SLAMA I , JOUABER B.ZEGHLACHE D . Energy efficient scheme for large scale wireless sensor networks with multiple sinks [C ] // WCNC . Las Vegas,NV,USA , 2008 : 2367 - 2372 .

PAUL B , MATIN M A . Optimal geometrical sink location estimation for two-tiered wireless sensor networks [J ] . IET Wireless Sensor Systems , 2011 , 1 ( 2 ): 74 - 84 .

YAN J , YU K G . Base station placement for wireless sensor network positioning system via lexicographical stratified programming [J ] . KSII Transactions on Internet and Information Systems , 2015 , 9 ( 11 ): 4453 - 4468 .

张化光 , 张欣 , 罗艳红 . 自适应动态规划综述 [J ] . 自动化学报 , 2013 , 39 ( 4 ): 304 - 310 .

ZHANG H G , ZHANG X , LUO Y H . An overview of research on adaptive dynamic programming [J ] . Acta Automatica Sinica , 2013 , 39 ( 4 ): 304 - 310 .

THOMAS H , CORMEN C E L , RONALD L R . 算法导论 [M ] . 北京 : 机械工业出版社 , 2007 : 386 - 390 .

THOMAS H , CORMEN C E L , RONALD L R . Introduction to algorithms [M ] . Beijing : China Machine PressPress , 2007 : 386 - 390 .

浏览量

1320

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

面向大规模图数据的关键词覆盖最优路径规划方法

基于免疫算法的TD-SCDMA网络基站选址优化