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

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

通信学报 ›› 2017, Vol. 38 ›› Issue (3): 7-15.doi: 10.11959/j.issn.1000-436x.2017069

• 学术论文 • 下一篇

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

韩江洪^1,²,段章领¹,卫星^1,²,陆阳^1,²,张建军^1,²

¹ 合肥工业大学计算机与信息学院，安徽合肥 230009
² 安全关键工业测控技术教育部工程研究中心，安徽合肥 230009

修回日期:2017-01-04 出版日期:2017-03-01 发布日期:2017-04-13
作者简介:韩江洪（1954-），男，安徽庐江人，合肥工业大学教授、博士生导师，主要研究方向为网络与通信、嵌入式系统、无线网络等。|段章领（1990-），男，安徽颍上人，合肥工业大学博士生，主要研究方向为无线网络优化、安全关键通信协议。|卫星（1980-），男，安徽肥西人，合肥工业大学副教授、硕士生导师，主要研究方向为物联网工程、离散事件动态系统。|陆阳（1967-），男，安徽合肥人，合肥工业大学教授、博士生导师，主要研究方向为安全关键工业测控技术、离散事件控制系统理论与应用、自组织网络理论与应用、二进神经网络理论与应用。|张建军（1963-），男，浙江宁波人，合肥工业大学教授、硕士生导师，主要研究方向为汽车电子、物联网工程、计算机集成制造。
基金资助:
国家重点研发计划专项基金资助项目(2016YFC0801804);国家自然科学基金资助项目(61370088);国家国际科技合作专项基金资助项目(2014DFB10060)

Optimal base station selection based on dynamic programming for reprogramming in mine wireless network

Jiang-hong HAN^1,²,Zhang-ling DUAN¹,Xing WEI^1,²,Yang LU^1,²,Jian-jun ZHANG^1,²

¹ School of Computer and Information,Hefei University of Technology,Hefei 230009,China
² Engineering Research Center of Safety-Critical Industry Measure and Control Technology of Ministry of Education,Hefei 230009,China

Revised:2017-01-04 Online:2017-03-01 Published:2017-04-13
Supported by:
The National Key Research Development Program of China(2016YFC0801804);The National Science and Technology Cooperation Project(2014DFB10060)

摘要/Abstract

摘要：

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

关键词: 无线再编程, 基站选址, 动态规划, 矿井无线传感器网络

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.

Key words: wireless reprogramming, base station location, dynamic programming, mine wireless sensor network

中图分类号:

TP301

韩江洪,段章领,卫星,陆阳,张建军. 基于动态规划的矿井无线再编程最优基站选址算法[J]. 通信学报, 2017, 38(3): 7-15.

Jiang-hong HAN,Zhang-ling DUAN,Xing WEI,Yang LU,Jian-jun ZHANG. Optimal base station selection based on dynamic programming for reprogramming in mine wireless network[J]. Journal on Communications, 2017, 38(3): 7-15.

图/表 12

图1

图2

图3

图4

图5

表1

图6

图7

图8

图9

图10

图11

参考文献 21

[1]	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.
[2]	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.
[3]	卫星, 张芳荣, 段章领 ,等. 基于模拟煺火的无线传感节点再编程策略[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.
[4]	方效林, 高宏, 李建中 . 一种基站可移动传感器网络再编程协议[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.
[5]	王珂 . 矿井无线传感器网络节点部署关键技术的研究[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.
[6]	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.
[7]	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.
[8]	DONG C C , YU F Q . An efficient network reprogramming protocol for wireless sensor networks[J]. Computer Communications, 2015,55(10): 41-50.
[9]	GAREY M R , JOHNSON D S . Computers and intractability:a guide to the theory of NP-completeness[M]. New York: FreemanPress, 1979: 245-248.
[10]	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.
[11]	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.
[12]	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.
[13]	SHI Y , HOU Y T . Optimal base station placement in wireless sensor network[J]. ACM Transactions on Sensor Networks, 2009,5(4): 2855-2869.
[14]	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.
[15]	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.
[16]	THANIGAIVELU K , MURUGAN K . Impact of sink mobility on network performance in wireless sensor networks[C]// NETCOM. Chennai ,India, 2009: 7-11.
[17]	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.
[18]	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.
[19]	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.
[20]	张化光, 张欣, 罗艳红 . 自适应动态规划综述[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.
[21]	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.

参数	取值范围	取值依据
网络覆盖区域	4 km×5 km	参考中型矿井的规模
节点间距	300 m	参考井下AP间距
通信半径	300 m	参考井下AP通信距离
节点数目	10~200	视具体网络规模而定
可选最佳基站位置	1~200	视具体拓扑而定
最终基站位置	1	从可用基站中任选一个

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

Optimal base station selection based on dynamic programming for reprogramming in mine wireless network

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 21

相关文章 5

Metrics

推荐阅读 0

[1]	张洁,芮兰兰,郭少勇,邱雪松,丁一凡. 基于终端干扰和链路稳定性的多终端协同维护机制[J]. 通信学报, 2015, 36(7): 176-184.
[2]	张笑燕,王敏讷,杜晓峰. 云计算虚拟机部署方案的研究[J]. 通信学报, 2015, 36(3): 275-285.
[3]	张英杰,毛赐平,俎云霄,孙先佑. 基于免疫算法的TD-SCDMA网络基站选址优化[J]. 通信学报, 2014, 35(5): 44-48.
[4]	张英杰1,2，毛赐平1,2，俎云霄3，孙先佑1,2. 基于免疫算法的TD-SCDMA网络基站选址优化[J]. 通信学报, 2014, 35(5): 6-48.
[5]	朱思峰,刘芳,柴争义. 基于免疫计算的TD-SCDM A网络基站选址优化[J]. 通信学报, 2011, 32(1): 106-110.