无线可充电传感器网络高效在线充电算法
|
摘要
在无线可充电传感器网络中,传感器节点的电池寿命是决定整个传感器网络生命周期的重要因素之一,而移动充电车可有效地为传感器节点提供电量补给。在动态请求(On-Demand)的无线可充电传感器网络中,研究充电车移动耗能和充电周期内总电量两个约束条件下的充电传感器数量最大化问题。针对该问题建立非线性整型数学模型,并提出一个基于贪心策略的在线算法。该算法在每个充电周期内,充电车依次选择距离最近的传感器节点进行充电。基于聚类思想,提出另一个在线算法。该在线聚类算法利用解决旅行商问题的最小生成树算法,使得充电车在每一个类中的充电路径构成一条回路的同时,减少移动耗能。实验结果表明,在线贪心算法、在线聚类算法得出的充电传感器数量分别占充电请求总数的67%与76%。
In wireless rechargeable sensor networks(WRSNs),battery capacity of sensor node is one of the dominate factors which affects the lifetime of WRSNs.Mobile charging vehicle can effectively supply electricity for sensor nodes.This paper tried to maximize the number of charged sensors in the on-demand WRSNs,with constraints of the moving energy consumption of the mobile charger and total amount of energy supply in the charging cycle.We established a nonlinear integer mathematical model and proposed an online algorithm based on greedy strategy.Charging vehicles selected the nearest sensor nodes to charge in the charging period.Based on clustering thought,another online algorithm was proposed in this study.The online clustering algorithm used an MST algorithm which was initially used to solve the traveling salesman problem,so as to make the charging path of the charging vehicle in each class form a circuit and reduce the mobile energy consumption.The experimental results show that the number of charging sensors obtained by online greedy algorithm and online clustering algorithm account for 67% and 76% of the total number of charging requests respectively.
In wireless rechargeable sensor networks(WRSNs),battery capacity of sensor node is one of the dominate factors which affects the lifetime of WRSNs.Mobile charging vehicle can effectively supply electricity for sensor nodes.This paper tried to maximize the number of charged sensors in the on-demand WRSNs,with constraints of the moving energy consumption of the mobile charger and total amount of energy supply in the charging cycle.We established a nonlinear integer mathematical model and proposed an online algorithm based on greedy strategy.Charging vehicles selected the nearest sensor nodes to charge in the charging period.Based on clustering thought,another online algorithm was proposed in this study.The online clustering algorithm used an MST algorithm which was initially used to solve the traveling salesman problem,so as to make the charging path of the charging vehicle in each class form a circuit and reduce the mobile energy consumption.The experimental results show that the number of charging sensors obtained by online greedy algorithm and online clustering algorithm account for 67% and 76% of the total number of charging requests respectively.
引文
[1]Wang C,Yang Y,Li J.Stochastic mobile energy replenishment and adaptive sensor activation for perpetual wireless rechargeable sensor networks[C]//Wireless Communications and Networking Conference(WCNC),2013 IEEE.IEEE,2013:974-979.
[2]Xie L,Shi Y,Hou Y T,et al.On traveling path and related problems for a mobile station in a rechargeable sensor network[C]//Proceedings of the fourteenth ACM international symposium on Mobile ad hoc networking and computing.ACM,2013:109-118.
[3]Watfa M K,Al Hassanieh H,Selman S.Multi-hop wireless energy transfer in WSNs[J].IEEE communications letters,2011,15(12):1275-1277.
[4]Xie L,Shi Y,Hou Y T,et al.Making sensor networks immortal:An energy-renewal approach with wireless power transfer[J].IEEE/ACM Transactions on networking,2012,20(6):1748-1761.
[5]Angelopoulos C M,Nikoletseas S,Raptis T P.Efficient wireless recharging in sensor networks[C]//Distributed Computing in Sensor Systems(DCOSS),2013 IEEE International Conference on.IEEE,2013:298-300.
[6]Li Z,Peng Y,Zhang W,et al.J-RoC:A joint routing and charging scheme to prolong sensor network lifetime[C]//Network Protocols(ICNP),2011 19th IEEE International Conference on.IEEE,2011:373-382.
[7]Zhao M,Li J,Yang Y.Joint mobile energy replenishment and data gathering in wireless rechargeable sensor networks[C]//Proceedings of the 23rd International Teletraffic Congress.International Teletraffic Congress,2011:238-245.
[8]Shi Y,Xie L,Hou Y T,et al.On renewable sensor networks with wireless energy transfer[C]//INFOCOM,2011Proceedings IEEE.IEEE,2011:1350-1358.
[9]Fu L,Cheng P,Gu Y,et al.Minimizing charging delay in wireless rechargeable sensor networks[C]//INFOCOM,2013 Proceedings IEEE.IEEE,2013:2922-2930.
[10]Xu W,Liang W,Lin X,et al.Towards perpetual sensor networks via deploying multiple mobile wireless chargers[C]//Parallel Processing(ICPP),2014 43rd International Conference on.IEEE,2014:80-89.
[11]Zhan S,Wu J,Qu L,et al.Efficient Scheduling Strategy for Mobile Charger in Wireless Rechargeable Sensor Networks[C]//Parallel and Distributed Computing,Applications and Technologies(PDCAT),2016 17th International Conference on.IEEE,2016:36-39.
[12]Ren X,Liang W,Xu W.Maximizing charging throughput in rechargeable sensor networks[C]//Computer Communication and Networks(ICCCN),2014 23rd International Conference on.IEEE,2014:1-8.
[13]Liang W,Xu Z,Xu W,et al.Approximation algorithms for charging reward maximization in rechargeable sensor networks via a mobile charger[J].IEEE/ACM Transactions on Networking,2017,25(5):3161-3174.
[14]He L,Kong L,Gu Y,et al.Evaluating the on-demand mobile charging in wireless sensor networks[J].IEEE Transactions on Mobile Computing,2015,14(9):1861-1875.
[15]Golden B L,Levy L,Vohra R.The orienteering problem[J].Naval research logistics,1987,34(3):307-318.
[16]Bharath-Kumar K,Jaffe J.Routing to multiple destinations in computer networks[J].IEEE Transactions on communications,1983,31(3):343-351.
[17]Dijkstra E.A note on two problems in connection with graphs[J].Numberical Mathematic,1959(1):269-27.
[18]刘朝霞.改进的Prim算法在求解旅行商问题中的应用[J].阴山学刊(自然科学版),2015,29(1):8-10,19.
[19]李萍,王春红,王文霞,等.最小生成树算法在旅行商问题中的应用[J].电脑开发与应用,2012,25(1):62-63.
[2]Xie L,Shi Y,Hou Y T,et al.On traveling path and related problems for a mobile station in a rechargeable sensor network[C]//Proceedings of the fourteenth ACM international symposium on Mobile ad hoc networking and computing.ACM,2013:109-118.
[3]Watfa M K,Al Hassanieh H,Selman S.Multi-hop wireless energy transfer in WSNs[J].IEEE communications letters,2011,15(12):1275-1277.
[4]Xie L,Shi Y,Hou Y T,et al.Making sensor networks immortal:An energy-renewal approach with wireless power transfer[J].IEEE/ACM Transactions on networking,2012,20(6):1748-1761.
[5]Angelopoulos C M,Nikoletseas S,Raptis T P.Efficient wireless recharging in sensor networks[C]//Distributed Computing in Sensor Systems(DCOSS),2013 IEEE International Conference on.IEEE,2013:298-300.
[6]Li Z,Peng Y,Zhang W,et al.J-RoC:A joint routing and charging scheme to prolong sensor network lifetime[C]//Network Protocols(ICNP),2011 19th IEEE International Conference on.IEEE,2011:373-382.
[7]Zhao M,Li J,Yang Y.Joint mobile energy replenishment and data gathering in wireless rechargeable sensor networks[C]//Proceedings of the 23rd International Teletraffic Congress.International Teletraffic Congress,2011:238-245.
[8]Shi Y,Xie L,Hou Y T,et al.On renewable sensor networks with wireless energy transfer[C]//INFOCOM,2011Proceedings IEEE.IEEE,2011:1350-1358.
[9]Fu L,Cheng P,Gu Y,et al.Minimizing charging delay in wireless rechargeable sensor networks[C]//INFOCOM,2013 Proceedings IEEE.IEEE,2013:2922-2930.
[10]Xu W,Liang W,Lin X,et al.Towards perpetual sensor networks via deploying multiple mobile wireless chargers[C]//Parallel Processing(ICPP),2014 43rd International Conference on.IEEE,2014:80-89.
[11]Zhan S,Wu J,Qu L,et al.Efficient Scheduling Strategy for Mobile Charger in Wireless Rechargeable Sensor Networks[C]//Parallel and Distributed Computing,Applications and Technologies(PDCAT),2016 17th International Conference on.IEEE,2016:36-39.
[12]Ren X,Liang W,Xu W.Maximizing charging throughput in rechargeable sensor networks[C]//Computer Communication and Networks(ICCCN),2014 23rd International Conference on.IEEE,2014:1-8.
[13]Liang W,Xu Z,Xu W,et al.Approximation algorithms for charging reward maximization in rechargeable sensor networks via a mobile charger[J].IEEE/ACM Transactions on Networking,2017,25(5):3161-3174.
[14]He L,Kong L,Gu Y,et al.Evaluating the on-demand mobile charging in wireless sensor networks[J].IEEE Transactions on Mobile Computing,2015,14(9):1861-1875.
[15]Golden B L,Levy L,Vohra R.The orienteering problem[J].Naval research logistics,1987,34(3):307-318.
[16]Bharath-Kumar K,Jaffe J.Routing to multiple destinations in computer networks[J].IEEE Transactions on communications,1983,31(3):343-351.
[17]Dijkstra E.A note on two problems in connection with graphs[J].Numberical Mathematic,1959(1):269-27.
[18]刘朝霞.改进的Prim算法在求解旅行商问题中的应用[J].阴山学刊(自然科学版),2015,29(1):8-10,19.
[19]李萍,王春红,王文霞,等.最小生成树算法在旅行商问题中的应用[J].电脑开发与应用,2012,25(1):62-63.