无人机骨干网分布式组网及接入选择算法
|
摘要
用无人机充当空中基站并组成骨干网为地面用户提供通信服务,在临时大型活动、抗震救灾、应急通信等方面有广阔应用前景.在无人机骨干网研究中有两个重要问题:一是如何对无人机集群进行合理部署,使其能够在对地面用户进行覆盖的同时维持骨干网的连通性;二是如何引导用户进行合适的接入选择,该选择既能使用户接入无人机骨干网后满足通信需求,又能最大化网络的负载均衡和接入成功率.为此,该文提出无人机骨干网分布式组网以及接入选择算法.部署算法通过感知地面用户,在虚拟力牵引下实现按需覆盖并维持稳定的双连接拓扑结构,同时还能记录无人机的最终位置和运动轨迹;接入选择算法分别侧重于信干噪比和无人机接入度数(负载数),提出三种无人机网络接入选择算法:最大信干噪比接入、满足信干噪比的随机接入以及满足信干噪比的最小度数接入,旨在最大化网络负载均衡和接入成功率.该算法在仿真实验中得到了验证,在双连接、按需覆盖之上更提高了网络整体性能.部署算法适用于用户和无人机聚集或分散、动态用户以及障碍等场景,且静态部署时间平均不超过300s;三种接入选择方法都收获了不小于78%的接入公平性以及92%以上的接入成功率,其中最小度数接入方法以额外的交互代价换取了86%以上的接入公平性和95%以上的接入率.
The flexible and intelligent flying nature of unmanned aerial vehicle(UAV)makes it able to act as flying base stations and construct airborne networks,to provide multi-hop communication service for user equipments(UEs)on the ground,which is promising during temporary activities,such as the earthquake relief and emergency military communications.There are two crucial problems in UAV airborne networks:(1)how can UAVs autonomously move to the desired locations to fulfill on-demand coverage for UEs on the ground while maintaining connectivity of UAV airborne networks;(2)how to guide UEs to make proper access selection,which can satisfy the communication requirement of UEs after accessing while maximizing the load balancing and successful rate of communication access.However,the deployment in terms of on-demand coverage and connectivity and access selection of UEs towards access fairness have not been well studied.To this end,we come up with a distributed deployment and access selection algorithm for UAVairborne networks in this paper.Given limited number of UAVs,the deployment algorithm uses virtual forces to drag UAVs to realize on-demand coverage while maintaining the stable bi-connected topology by sensing the UEs on the ground,when information of only 1-hop UAVs and sensed UEs is used.The attractive forces are used for gathering and covering and the repulsive forces are used for autonomous move and collision avoidance of UAVs.The stop condition is that all UAVs are bi-connected and the coverage outage proportion is restricted below a predefined threshold.At the meantime it can record not only the final positions of UAVs but also the motion tracks of them.Our access selection algorithm puts different emphasis on the signal to interference and noise ratio(SINR)and the degree(load number)of each UAV,proposing three access selection methods:access in maximum SINR,random access based on SINR requirement and minimum degree access based on SINR requirement,which aims at maximizing the load balancing and successful rate of access of the whole network at the same time.Simulations further validate our proposed algorithm that it improves the performance of the network based on bi-connect topology and on-demand coverage.Firstly,our deployment algorithm can be applied in multiple scenarios where there are UEs distributed randomly or in cluster,initial UAVs departing dispersedly or from a base,dynamic UEs and obstacles.Moreover,note that the static deployment time achieved is no more than 300 seconds on average.Secondly,the three access selection methods make great harvest in access fairness and successful ratio of access which are no less than 78%and 92%respectively,among which the minimum degree access reaps at least 86%access fairness and 95% ratio of access with extra interaction cost.Last but not least,it turns out that our algorithms are applicable to different interference models and we find the increase of complexity of the interference model will decrease the access fairness of the whole network.
The flexible and intelligent flying nature of unmanned aerial vehicle(UAV)makes it able to act as flying base stations and construct airborne networks,to provide multi-hop communication service for user equipments(UEs)on the ground,which is promising during temporary activities,such as the earthquake relief and emergency military communications.There are two crucial problems in UAV airborne networks:(1)how can UAVs autonomously move to the desired locations to fulfill on-demand coverage for UEs on the ground while maintaining connectivity of UAV airborne networks;(2)how to guide UEs to make proper access selection,which can satisfy the communication requirement of UEs after accessing while maximizing the load balancing and successful rate of communication access.However,the deployment in terms of on-demand coverage and connectivity and access selection of UEs towards access fairness have not been well studied.To this end,we come up with a distributed deployment and access selection algorithm for UAVairborne networks in this paper.Given limited number of UAVs,the deployment algorithm uses virtual forces to drag UAVs to realize on-demand coverage while maintaining the stable bi-connected topology by sensing the UEs on the ground,when information of only 1-hop UAVs and sensed UEs is used.The attractive forces are used for gathering and covering and the repulsive forces are used for autonomous move and collision avoidance of UAVs.The stop condition is that all UAVs are bi-connected and the coverage outage proportion is restricted below a predefined threshold.At the meantime it can record not only the final positions of UAVs but also the motion tracks of them.Our access selection algorithm puts different emphasis on the signal to interference and noise ratio(SINR)and the degree(load number)of each UAV,proposing three access selection methods:access in maximum SINR,random access based on SINR requirement and minimum degree access based on SINR requirement,which aims at maximizing the load balancing and successful rate of access of the whole network at the same time.Simulations further validate our proposed algorithm that it improves the performance of the network based on bi-connect topology and on-demand coverage.Firstly,our deployment algorithm can be applied in multiple scenarios where there are UEs distributed randomly or in cluster,initial UAVs departing dispersedly or from a base,dynamic UEs and obstacles.Moreover,note that the static deployment time achieved is no more than 300 seconds on average.Secondly,the three access selection methods make great harvest in access fairness and successful ratio of access which are no less than 78%and 92%respectively,among which the minimum degree access reaps at least 86%access fairness and 95% ratio of access with extra interaction cost.Last but not least,it turns out that our algorithms are applicable to different interference models and we find the increase of complexity of the interference model will decrease the access fairness of the whole network.
引文
[1]Ullah H,McClean S,et al.An optimal UAV deployment algorithm for bridging communication//Proceedings of the15th International Conference on ITS Telecommunication.Warsaw,Poland,2017:1-7
[2]Kwon J,Hailes S.Scheduling UAVs to bridge communication in delay-tolerant networks using real-time scheduling analysis techniques//Proceedings of the IEEE/SICE International Symposium on System Integration.Tokyo,Japan,2014:363-369
[3]Liu Hai,Chu Xiao-Wen,et al.Simple movement control algorithm for bi-connectivity in robotic sensor networks.IEEE Journal on Selected Areas in Communication,2010,28(7):994-1005
[4]Mozaffari M,Saad W,et al.Efficient deployment of multiple unmanned aerial vehicles for optimal wireless coverage.IEEECommunication Letters,2016,20(8):1647-1650
[5]Semnani S H,Basir O A.Semi-flocking algorithm for motion control of mobile sensors in large-scale surveillance systems.IEEE Transactions on Cybernetics,2015,45(1):129-137
[6]Zorbas D,Razafindralambo T,Guerriero F,et al.Energy efficient mobile target tracking using flying drones.Procedia Computer Science,2013,19:80-87
[7]Mozaffari M,Saad W,et al.Optimal transport theory for power-efficient deployment of unmanned aerial vehicles//Proceedings of the IEEE International Conference on Communication.Kuala Lumper,Malaysia,2016:1-6
[8]Orfanus D,de Freitas E P,Eliassen F.Self-organization as a supporting paradigm for military UAV relay networks.IEEECommunication Letters,2016,20(4):804-807
[9]Che Nan,Li Zhi-Jun,Jiang Shou-Xu.Relay deployment algorithm in heterogeneous wireless networks.Chinese Journal of Computers,2016,39(5):905-918(in Chinese)(车楠,李治军,姜守旭.异构无线网络中Relay节点部署算法.计算机学报,2016,39(5):905-918)
[10]Das S,Liu H,Nayak A,Stojmenovic I.A localized algorithm for bi-connectivity of connected mobile robots.Telecommunication System,2009,40(3-4):129-140
[11]Liu H,Wan P J,Jia X.On optimal placement of relay nodes for reliable connectivity in wireless sensor networks.Journal of Combinatorial Optimization,2006,11:249-260
[12]Zhang Long,Zhou Fan,Bai Chun-Hong,Xu Hai-Tao.Analytical model for predictable contact in intermittently connected cognitive radio ad hoc networks.International Journal of Distributed Sensor Networks,2016,12(7):1-12
[13]Zhang Long,Zhou Xian-Wei.Joint cross-layer optimized routing and dynamic power allocation in deep space information networks under predictable contacts.IET Communications,2013,7(5):417-429
[14]Zhang Long,Zhuo Fan,Xu Hai-Tao.A cross-layer optimization framework for congestion and power control in cognitive radio ad hoc networks under predictable contact.EURASIPJournal on Wireless Communications and Networking,2018,(1):57-79
[15]Boufares N,Khoufi I,Minet P,et al.Three dimensional mobile wireless sensor networks redeployment based on virtual forces//Proceedings of the Wireless Communications and Mobile Computing Conference.Valencia,Spain,2017:1628-1633
[16]Zhao Hai-Tao,Mao Ling-Chu,Wei Ji-Bo.A simple motion control algorithm for autonomous robotic sensor networks.Computer Networks,2018,135:190-200
[17]Zhao Hai-Tao,Wei Ji-Bo,Huang Sheng-Chun,et al.Regular topology formation based on artificial forces for distributed mobile robotic networks.IEEE Transactions on Mobile Computing,2018,DOI:10.1109/TMC.2018.2873015
[18]Tan Li,Yang Chao-Yu,Tang Xiao-Jiang,Jiao Yao-Yao.Atarget tracking algorithm based on path virtual force//Proceedings of the IEEE International Conference on Computational Science and Engineering(CSE)and IEEEInternational Conference on Embedded and Ubiquitous Computing(EUC).Guangzhou,China,2017:512-517
[19]Zhao Hai-Tao,Liu Hai,Leung Yiu-Wing,Chu Xiao-Wen.Self-adaptive collective motion of swarm robots.IEEETransactions on Automation Science and Engineering,2018,15(4):1533-1545
[20]Hanjin L,Dongwook K,Byungchun C,et al.Adaptive hysteresis using mobility correlation for last handover.IEEECommunication Letters,2008,12(2):152-154
[21]Roy S D,Reddy S R V.Signal strength ratio based vertical handoff decision algorithms in integrated heterogeneous networks.Wireless Personal Communications,2014,77(4):2565-2585
[22]Ahuja K,Singh B,Khanna R.Network selection algorithm based on link quality parameters for heterogeneous wireless networks.Optik,2014,125(14):3657-3662
[23]Sheng Jie,Tang Liang-Rui,Hao Jian-Hong.Hybrid load balancing algorithm based on service transformation and admission control in heterogeneous wireless networks.Acta Electronica Sinica,2013,41(2):321-328(in Chinese)(盛洁,唐良瑞,郝建红.异构无线网络中基于业务转移和接入控制的混合负载均衡.电子学报,2013,41(2):321-328)
[24]Gerasimenko M,et al.Characterizing performance of load-aware network selection in multi-radio(WiFi/LTE)heterogeneous networks//Proceedings of the IEEE GLOBECOM Workshops.Atlanta,USA,2013:397-402
[25]Ma D,Ma M.Proactive load balancing with admission control for heterogeneous overlay networks.Wireless Communication&Mobile Computing,2013,13(18):1671-1680
[26]Chen H,Cheng C,et al.Guard-channel-based incremental and dynamic optimization on call admission control for next-generation QoS-aware heterogeneous systems.IEEETransactions on Vehicular Technology,2008,57(5):3064-3082
[27]Miao J,Hu Z,et al.Joint power and bandwidth allocation algorithm with QoS support in heterogeneous wireless networks.IEEE Communication Letters,2012,16(4):479-481
[28]Al-Hourani A,Kandeepan S,Lardner S.Optimal LAPaltitude for maximum coverage.IEEE Wireless Communication Letters,2014,3(6):569-572
[2]Kwon J,Hailes S.Scheduling UAVs to bridge communication in delay-tolerant networks using real-time scheduling analysis techniques//Proceedings of the IEEE/SICE International Symposium on System Integration.Tokyo,Japan,2014:363-369
[3]Liu Hai,Chu Xiao-Wen,et al.Simple movement control algorithm for bi-connectivity in robotic sensor networks.IEEE Journal on Selected Areas in Communication,2010,28(7):994-1005
[4]Mozaffari M,Saad W,et al.Efficient deployment of multiple unmanned aerial vehicles for optimal wireless coverage.IEEECommunication Letters,2016,20(8):1647-1650
[5]Semnani S H,Basir O A.Semi-flocking algorithm for motion control of mobile sensors in large-scale surveillance systems.IEEE Transactions on Cybernetics,2015,45(1):129-137
[6]Zorbas D,Razafindralambo T,Guerriero F,et al.Energy efficient mobile target tracking using flying drones.Procedia Computer Science,2013,19:80-87
[7]Mozaffari M,Saad W,et al.Optimal transport theory for power-efficient deployment of unmanned aerial vehicles//Proceedings of the IEEE International Conference on Communication.Kuala Lumper,Malaysia,2016:1-6
[8]Orfanus D,de Freitas E P,Eliassen F.Self-organization as a supporting paradigm for military UAV relay networks.IEEECommunication Letters,2016,20(4):804-807
[9]Che Nan,Li Zhi-Jun,Jiang Shou-Xu.Relay deployment algorithm in heterogeneous wireless networks.Chinese Journal of Computers,2016,39(5):905-918(in Chinese)(车楠,李治军,姜守旭.异构无线网络中Relay节点部署算法.计算机学报,2016,39(5):905-918)
[10]Das S,Liu H,Nayak A,Stojmenovic I.A localized algorithm for bi-connectivity of connected mobile robots.Telecommunication System,2009,40(3-4):129-140
[11]Liu H,Wan P J,Jia X.On optimal placement of relay nodes for reliable connectivity in wireless sensor networks.Journal of Combinatorial Optimization,2006,11:249-260
[12]Zhang Long,Zhou Fan,Bai Chun-Hong,Xu Hai-Tao.Analytical model for predictable contact in intermittently connected cognitive radio ad hoc networks.International Journal of Distributed Sensor Networks,2016,12(7):1-12
[13]Zhang Long,Zhou Xian-Wei.Joint cross-layer optimized routing and dynamic power allocation in deep space information networks under predictable contacts.IET Communications,2013,7(5):417-429
[14]Zhang Long,Zhuo Fan,Xu Hai-Tao.A cross-layer optimization framework for congestion and power control in cognitive radio ad hoc networks under predictable contact.EURASIPJournal on Wireless Communications and Networking,2018,(1):57-79
[15]Boufares N,Khoufi I,Minet P,et al.Three dimensional mobile wireless sensor networks redeployment based on virtual forces//Proceedings of the Wireless Communications and Mobile Computing Conference.Valencia,Spain,2017:1628-1633
[16]Zhao Hai-Tao,Mao Ling-Chu,Wei Ji-Bo.A simple motion control algorithm for autonomous robotic sensor networks.Computer Networks,2018,135:190-200
[17]Zhao Hai-Tao,Wei Ji-Bo,Huang Sheng-Chun,et al.Regular topology formation based on artificial forces for distributed mobile robotic networks.IEEE Transactions on Mobile Computing,2018,DOI:10.1109/TMC.2018.2873015
[18]Tan Li,Yang Chao-Yu,Tang Xiao-Jiang,Jiao Yao-Yao.Atarget tracking algorithm based on path virtual force//Proceedings of the IEEE International Conference on Computational Science and Engineering(CSE)and IEEEInternational Conference on Embedded and Ubiquitous Computing(EUC).Guangzhou,China,2017:512-517
[19]Zhao Hai-Tao,Liu Hai,Leung Yiu-Wing,Chu Xiao-Wen.Self-adaptive collective motion of swarm robots.IEEETransactions on Automation Science and Engineering,2018,15(4):1533-1545
[20]Hanjin L,Dongwook K,Byungchun C,et al.Adaptive hysteresis using mobility correlation for last handover.IEEECommunication Letters,2008,12(2):152-154
[21]Roy S D,Reddy S R V.Signal strength ratio based vertical handoff decision algorithms in integrated heterogeneous networks.Wireless Personal Communications,2014,77(4):2565-2585
[22]Ahuja K,Singh B,Khanna R.Network selection algorithm based on link quality parameters for heterogeneous wireless networks.Optik,2014,125(14):3657-3662
[23]Sheng Jie,Tang Liang-Rui,Hao Jian-Hong.Hybrid load balancing algorithm based on service transformation and admission control in heterogeneous wireless networks.Acta Electronica Sinica,2013,41(2):321-328(in Chinese)(盛洁,唐良瑞,郝建红.异构无线网络中基于业务转移和接入控制的混合负载均衡.电子学报,2013,41(2):321-328)
[24]Gerasimenko M,et al.Characterizing performance of load-aware network selection in multi-radio(WiFi/LTE)heterogeneous networks//Proceedings of the IEEE GLOBECOM Workshops.Atlanta,USA,2013:397-402
[25]Ma D,Ma M.Proactive load balancing with admission control for heterogeneous overlay networks.Wireless Communication&Mobile Computing,2013,13(18):1671-1680
[26]Chen H,Cheng C,et al.Guard-channel-based incremental and dynamic optimization on call admission control for next-generation QoS-aware heterogeneous systems.IEEETransactions on Vehicular Technology,2008,57(5):3064-3082
[27]Miao J,Hu Z,et al.Joint power and bandwidth allocation algorithm with QoS support in heterogeneous wireless networks.IEEE Communication Letters,2012,16(4):479-481
[28]Al-Hourani A,Kandeepan S,Lardner S.Optimal LAPaltitude for maximum coverage.IEEE Wireless Communication Letters,2014,3(6):569-572