Table of Contents for Issue 10 of 2023 | Special Topic: Mobile Ad Hoc Networks
Improved LAR Routing Method Based on Distance Threshold Correction in 6G Drone Self-Organizing Networks
A Geographical Routing Algorithm for Drone-Assisted Surface Self-Organizing Networks Based on Location Prediction
“Mobile Self-Organization” Special Topic · 03
Q-Learning UANET Routing Protocol Based on Link Quality and Node Load Estimation
Wang Bingyan1, Zheng Xiangping2,3, Jia Wenjie1, Li Dapeng1
(1. School of Communication and Information Engineering, Nanjing University of Posts and Telecommunications, Jiangsu Nanjing 210003;
2. Jiangsu Yongfeng Machinery Co., Ltd., Jiangsu Nanjing 210094;
3. School of Computer Science and Engineering, Chongqing University of Technology, Chongqing 400054)
Abstract To address the issues of frequent topological changes in Unmanned Aerial Vehicle Ad Hoc Networks (UANET) and the poor stability of traditional routing protocols leading to link breaks and service loss under high load, this paper proposes a Q-learning UANET routing protocol based on link quality and node load estimation. This protocol builds on the Optimized Link State Routing (OLSR) protocol and utilizes the Q-learning algorithm, where hop count, link quality, and node load serve as reward functions for routing decisions, using a weighted comprehensive evaluation index as the routing decision criterion. Experimental results indicate that the improved protocol is more suitable for high-dynamic and high-load network environments in drone self-organizing networks.
Keywords UAV Ad Hoc Network; Routing Protocol; OLSR; Q-Learning
doi:10.3969/j.issn.1006-1010.20230825-0001
Classification Number: TN929.5 Document Identifier Code: A
Article Number: 1006-1010(2023)10-0017-07
Citation Format: Wang Bingyan, Zheng Xiangping, Jia Wenjie, et al. Q-Learning UANET Routing Protocol Based on Link Quality and Node Load Estimation[J]. Mobile Communications, 2023, 47(10): 17-23.
WANG Bingyan, ZHENG Xiangping, JIA Wenjie, et al. Q-Learning UANET Routing Protocol Based on Link Quality and Node Load Estimation[J]. Mobile Communications, 2023, 47(10): 17-23.
0 Introduction
Mobile Ad Hoc Networks (MANET) are self-organizing, decentralized, multi-hop wireless networks. Unlike traditional centrally controlled wireless networks, MANETs do not rely on any central infrastructure, allowing for low-cost and rapid network deployment, as well as ease of expansion and maintenance, and have gained widespread application in recent years[1-2]. Unmanned Aerial Vehicles Ad Hoc Networks (UANET) are an extension of MANET in the UAV domain, characterized by high dynamics, long links, limited resources, and frequent data exchanges, which bring diversity and flexibility to task execution but also pose significant challenges for routing protocol design[3-5].
Currently, the OLSR (Optimized Link State Routing) protocol is a widely used proactive routing protocol[6]. Compared to passive routing protocols represented by AODV (Ad hoc On-Demand Distance Vector Routing), OLSR nodes periodically exchange routing metric information to update the routing table. When sending traffic, they can directly query the established routes. In contrast, passive routing protocols only establish routes when traffic is sent, so in high real-time requirement UAV network scenarios, OLSR has advantages[7].
In OLSR, nodes complete link probing and neighbor discovery by broadcasting Hello packets and share network topology information through Topology Control (TC) packets. At the same time, the Multi-Point Relay (MPR) technique reduces routing maintenance overhead[8-10]. However, the traditional OLSR protocol only uses hop count as the routing decision criterion, making the selection standard too singular and difficult to adapt to real UANET scenarios.
To address the frequent changes in network topology, Wang Xudong et al.[11] proposed a speed-weighted SW-OLSR protocol based on location information, which estimates a link quality value (ETX) to assist routing decisions. Zhou Changjia et al.[12] proposed a UAV-OLSR protocol suitable for UANET, dynamically adjusting the sending period of control information by sensing neighbor changes during Hello message intervals and topology changes during TC message intervals, while optimizing the MPR mechanism based on node energy assessments; Yao Yukun et al.[13] proposed incorporating link stability and link existence time as indicators when selecting MPR node sets, making the selected MPR node sets more stable and reasonable, while dynamically adjusting the TC message sending interval using the Q-learning algorithm, which reduces routing control overhead to some extent. In fact, the above improved protocols optimize OLSR for mobile topologies but lack consideration of node load. Wang Jing et al.[14] used cross-layer protocol design theory to perceive node load, link delivery rate, and link availability, inferring link quality based on this information, further optimizing routing selection to ensure network load balancing and effectively improving protocol reliability. However, this protocol incurs significant control overhead, making it difficult to apply to energy-limited UANETs.
To address the issue of single routing selection criteria in OLSR, this paper proposes a Q-learning OLSR protocol based on link quality and node load estimation (UQL-OLSR) in UANET scenarios. The main content includes: 1) defining link quality and node load parameters for high dynamic and high throughput network scenarios, and providing corresponding estimation methods; 2) based on the Q-learning algorithm, designing a reward function for routing decisions that incorporates hop count, link quality, and node load, and providing methods for updating the Q-value table and routing table during routing establishment to guide routing decisions under multiple factors. The protocol has been implemented in a network simulation environment, and experimental results show that the optimized protocol is more suitable for high dynamic and high load environments in UANET.
1 System Model and Problem Analysis
1.1 System Model
This paper establishes a model for routing selection and establishment process of the OLSR protocol in UANET scenarios using the Q-learning algorithm. Q-learning is a model-free reinforcement learning (RL) algorithm based on value functions[15], which can distribute learning tasks to each network node and dynamically update routing tables through periodic interactions with neighboring nodes. This means that nodes in the network can continuously improve routing decisions based on their interaction experiences to enhance network performance and reliability. This method helps optimize data transmission, making the network work more efficiently.
Figure 1 illustrates the basic model of Q-learning, based on the Markov Decision Process (MDP) theory. In MDP, the agent operates in an environment composed of states (State), actions (Action), and rewards (Reward). Assuming the state of the agent at time t is St, after receiving the reward value Rt based on the feedback of the last action, the agent executes the optimal action At and enters state St+1. The agent continuously performs these operations, where the actions bring rewards that influence subsequent action decisions to achieve the optimal decision in a specific environment[16].
The Q-learning algorithm evaluates the value of state-action pairs using Q-values, with the following update rule:
where Q(st, at) is the value function of the state-action pair (s, a), representing the expected reward of taking action a in state s, α∈(0, 1) is the learning rate that controls the speed of learning, and γ∈(0, 1) is the discount factor that controls the importance of long-term rewards.
To enable nodes in the network to autonomously learn and timely perceive topology and node states, the Q-learning algorithm is combined with the OLSR protocol, defining the agent as the nodes in the network and the learning environment as the entire UANET.
Define the triplet (A, S, R) as follows:
1) Actions (A): Nodes perceive neighbor and topology changes, adding or updating local routing table entries, selecting a node from a one-hop neighbor set N={N1, N2,…,Nn} as the next hop for the corresponding destination.
2) States (S): Local routing information and state statistics of nodes, including hop count, node geographical location (x, y), data reception rate R, etc., reflecting the current situation of nodes to guide routing decisions.
3) Rewards (R): The immediate feedback value from the entire network to the nodes, which can be mapped to rewards R based on network performance requirements, such as hop count, delay, load, energy consumption, etc., enabling nodes to adapt to dynamic network environments.
During the routing establishment process, each node in the network maintains a Q-value table, where the columns represent the destination node IDs passing through the node, and the rows represent the one-hop neighbor node IDs of the node, used to record the expected cumulative reward value of selecting a certain neighbor node as the next hop for a specified destination. The neighbor with the highest Q-value is chosen as the next hop node. The specific format of the Q-value table is shown in Table 1.
Based on this routing strategy, referring to formula (1), for destination node D, the source node S evaluates the quality of neighbor node N as the next hop, and the corresponding Q-value update formula becomes:
where α is the learning rate, γ is the discount factor, and Ns is the one-hop neighbor set of source node S.
As a model-free algorithm, the complexity of Q-learning can be expressed as O(SAH), where S represents the size of the state space, A represents the size of the action space, and H represents the step length taken in each execution[17]. The size of S is influenced by the network scale; as the number of nodes increases, the number of state parameters that need to be counted also increases. The size of A is related to the size of the one-hop neighbor set of network nodes; specifically, the more neighbor nodes available for selection, the larger the action space. Since each action execution only adds or updates one row of routing table entries, the step length H can be considered as 1. In summary, the complexity of routing establishment through Q-learning is influenced by the network scale and node density; setting a reasonable total number of nodes and topology can significantly reduce the complexity of the algorithm.
1.2 Problem Analysis
The traditional OLSR protocol only uses hop count and the Dijkstra algorithm to calculate paths and generate routes. The routing selection criterion is too singular, making it difficult to adapt to the rapid changes in network topology, leading to issues such as link breaks and untimely routing updates[18]. In addition, in scenarios with heavy traffic, the load on MPR nodes increases, raising the likelihood of congestion and further degrading network performance[19]. Therefore:
1) Considering the mobility of UAV nodes: When formulating routing forwarding strategies, selecting higher quality and more stable next-hop nodes can extend path lifetime, reduce link breaks, and improve routing quality and data transmission reliability.
2) Considering data congestion issues under high load: During routing selection, choosing forwarding nodes with lower load and higher availability can reduce the occurrence of such problems and lower network latency[20].
Considering these two issues while also retaining hop count considerations, we define hop count factor HF, link quality factor QF, and node availability factor LF, which together constitute the immediate reward R for nodes in Q-learning (the design of the reward function is detailed in section 2.1), used to guide routing decisions under multiple influencing factors.
2.2 Routing Scheme Design
(1) Routing Establishment Process
During the routing establishment process, each node periodically broadcasts Hello packets to probe neighboring nodes. To determine which nodes’ broadcast messages to forward, nodes maintain a local MPR_S (MPR Selector) set. After adding the information from the MPR_S set to the TC packet, nodes flood the TC packet across the network to interact with the network topology, which is processed and forwarded by MPR nodes. Referring to the definition of the Q table in section 1.1, nodes in the network maintain a Q-value table through interaction of Hello and TC packets. When updating routes, they select the neighbor node with the highest Q-value as the next hop. The diagram of UAV nodes maintaining the Q table is shown in Figure 2.
To calculate the Q-value from the current node to the corresponding destination node, the node first collects and calculates local routing and state measurement information, then adds this information to the Hello packets and periodically shares this data with neighboring nodes. MPR nodes receiving the measurement information from neighbors will add this information to the TC packets and broadcast them across the network. In the initial phase, each node’s Q table is set to 0. When a node receives TC packets sent by neighboring nodes, it maintains a local topology table, extracts relevant information such as destination address Dt, previous hop address Pt, node geographical location, reception rate, etc., and calculates the reward value R according to formula (11), then takes Dt as the destination node Di for the Q-value parameter and Pt as the neighbor node Ni, updating the local Q-value table according to formula (2). This process updates the Q-value for the current node with the nodes in the MPR_S set as the destination and the previous hop node as neighbors. Once the update is complete, if the current node is an MPR node, it sets the previous hop address as itself and forwards the TC packet to the entire network in a single-hop broadcast manner. Similarly, other TC packets received from neighboring nodes are processed in the same way, and after a period of algorithm convergence, the Q-values for all other destination nodes in the network are updated.
The routing establishment process of the UQL-OLSR protocol is shown in Figure 3.
(2) Routing Maintenance Process
During the routing establishment process, to address scenarios of nodes joining and leaving the network in high dynamic environments, the effective time of nodes in the Q-value table is defined. Within this effective time, if a node’s Q-value has not been updated, the system will consider the destination node as offline and clear the corresponding row of data. At the same time, it is necessary to set the time-to-live (TTL) for TC packets according to the network scale, reducing control information redundancy while ensuring that the entire network can perceive topology information.
Since the Q-learning algorithm requires a certain amount of time to converge, the updated routing can only gradually approach the optimal as the Q-values for all nodes converge. However, during routing table updates, Q-values may deviate significantly from steady-state values. To quickly achieve Q-value convergence, especially in highly dynamic networks, it is necessary to moderately reduce the sending intervals for Hello and TC packets to promote rapid Q-value updates. Additionally, to reduce competition and collisions of control information in the network, during experiments, the sending delay of control information is set to γT, where γ is a random number between [0,1], and T is the sending interval for control packets, staggering the sending times of control information for each node to ensure more uniform message transmission in the network, maintaining a relatively constant rate of control information reception and bandwidth usage during the routing establishment process.
3 Simulation and Analysis
This paper uses a network simulation platform to simulate and validate the UQL-OLSR protocol, comparing it with the integrated standard version of the OLSR protocol and the speed-weighted OLSR protocol based on location information from literature [11]. The following simulation experiments were designed:
1) Estimate the routing establishment time of the UQL-OLSR protocol by obtaining the convergence time of the maximum Q-value in the local Q table of the source node;
2) Verify the impact of the frequency of network topology changes on delay and packet delivery rate under consistent node throughput;
3) Validate the effect of changes in node throughput on delay and packet delivery rate under consistent network topology changes.
In the experiment, the weights for minimum hop count, link stability, and node availability were set to 0.3, 0.4, and 0.3, respectively, with a scenario size of 2 km×2 km; nodes adopted a random movement pattern (Random WayPoint). The overall experimental simulation parameters are shown in Table 2.
3.1 Routing Establishment Time Analysis
As mentioned in section 2.2, only when the Q-values of the nodes converge can the updated routing gradually approach the optimal routing. Therefore, to evaluate the performance of the UQL-OLSR protocol, it is necessary to ensure that the Q-values maintained by the nodes reach a converged state during the transmission of business data. During routing selection, nodes choose the neighbor with the highest Q-value as the next hop node; thus, the convergence time of the maximum Q-value can be used to estimate the convergence time of the learning process and the routing establishment time.
Set the maximum moving speed of nodes in the scenario to 5 m/s, with 5 end-to-end business paths, sending rates of 4 kbps, and randomly select one end-to-end business path in the experimental scenario. The convergence process of the source node’s Qmax value over simulation time is shown in Figure 4.
During the initial phase of the simulation, Qmax increases rapidly, and as time progresses, the increase rate gradually slows, stabilizing around 20 s. This indicates that during the operation of the protocol, the source node learns about the minimum hop count, network topology changes, and link availability information from the network, which ultimately reflects in the Q-value size. As nodes move and the network load changes, Qmax may also fluctuate slightly, but not as dramatically as during the initial routing establishment phase. It can be concluded that under the simulation parameters configured in Table 2, the routing establishment time is around 20 s; therefore, to avoid errors, the transmission of business data should be set to start after 20 s of network operation.
3.2 Performance Analysis
To test the impact of the intensity of network topology movement on protocol performance, the sending rates of business source nodes were set consistently at 4 kbps. The changes in end-to-end delay and packet delivery rate when the maximum speed of UAVs ranges from 0 to 25 m/s are shown in Figures 5 and 6. It can be observed that as the node speed increases, the end-to-end delay gradually increases, and the packet delivery rate gradually decreases. When UAVs move at lower speeds, the changes in topology are minimal, and the end-to-end delay and packet delivery rates of the three protocols remain similar. When the maximum speed of UAVs rises to 25 m/s, the SW-OLSR protocol, by introducing speed-weighted ETX and node location information, and the UQL-OLSR protocol, by adding evaluations of link quality and node load and the Q-learning reward mechanism, achieved a 9.8% and 13.5% reduction in delay, respectively, and a 46.2% and 51.8% improvement in packet delivery rate, respectively. Both optimized OLSR protocols consider the impact of topology changes on data transmission, enabling the selection of more stable next-hop nodes and reducing link breaks in the network.
Simultaneously, to test the impact of node throughput on protocol performance, the maximum moving speed of nodes was uniformly set to 5 m/s. In the scenario, 5 end-to-end business paths were randomly added, and the changes in end-to-end delay and packet delivery rate were recorded under business rates ranging from 100 kbps to 500 kbps. As shown in Figures 7 and 8, as the business rate increases, the load on the nodes in the network increases, leading to higher end-to-end delays and lower packet delivery rates. Again, when the sending rate is low, there is no significant difference in end-to-end delay and packet delivery rates among the three protocols. However, when the sending rate is relatively high at 500 kbps, the SW-OLSR protocol, which considers the movement of UAV nodes, improved delay and packet delivery rates by 17.0% and 21.2%, respectively, while the UQL-OLSR protocol, which also considers the load levels of neighboring nodes and prioritizes selecting next-hop neighbors with lower loads, further optimized delay and packet delivery rates by 7.4% and 12.1%, respectively, in scenarios with high business rates.
4 Conclusion
The traditional OLSR protocol only uses hop count as the decision criterion for updating routes, which cannot adapt to the high dynamics and high loads present in today’s UAV Ad Hoc networks. To address this issue, this paper designs the UQL-OLSR protocol based on the Q-learning framework, incorporating hop count, link quality, and node load as routing metrics. During its operation, nodes exchange routing metric information through broadcasting Hello and TC packets, and network nodes achieve dynamic routing updates by maintaining a Q-value table. Experimental results show that the UQL-OLSR protocol has significant advantages over the OLSR protocol in terms of average end-to-end delay and packet delivery rate, making it more suitable for scenarios with high-speed node movement and frequent data exchanges in UAV Ad Hoc networks.
References: (Scroll down to browse)
[1] Wu Yuan. Analysis and Research of Routing Protocols in Mobile Ad Hoc Networks[J]. Microcontroller and Embedded System Applications, 2014, 14(01): 16-19.
[2] Zhang Degan, Ge Hui, Liu Xiaohuan, et al. A New Adaptive Routing Algorithm Based on Q-Learning Strategy for Mobile IoT[J]. Acta Electronica Sinica, 2018, 46(10): 2325-2332.
[3] Sun Chen, Mo Guomei, Shu Jian. A Review of Routing Research in UAV Ad Hoc Networks Based on Reinforcement Learning[J]. Application Research of Computers, 2023, 40(07): 1937-1946.
[4] Liu J, Ren F, Miao L, et al. A-ADHOC: An adaptive real-time distributed MAC protocol for Vehicular Ad Hoc Networks[J]. Mobile Networks and Applications, 2011, 16: 576-585.
[5] Maxa J, Mahmoud B S M, Larrieu N. Survey on UAANET Routing Protocols and Network Security Challenges[J]. Ad Hoc & Sensor Wireless Networks, 2017, 37(1-4).
[6] Gupta L, Jain R, Vaszkun G. Survey of important issues in UAV communication networks[J]. IEEE Communications Surveys & Tutorials, 2015, 18(02): 1123-1152.
[7] Ferronato J J, Trentin M A S. Analysis of routing protocols OLSR, AODV and ZRP in real urban vehicular scenario with density variation[J]. IEEE Latin America Transactions, 2017, 15(09): 1727-1734.
[8] Jacquet P, Muhlethaler P, Clausen T, et al. Optimized link state routing protocol for ad hoc networks[C]// IEEE International Multi Topic Conference, 2001. IEEE INMIC 2001. Technology for the 21st Century. IEEE, 2001: 62-68.
[9] Duan Wei, Li Dashuang, Jiang Yongguang, et al. Research on OLSRv2 Draft and its Related Specifications[J]. Communication Technology, 2014(5): 527-531.
[10] Maccari L, Maischberger M, Cigno R L. Where have all the MPRs gone? On the optimal selection of Multi-Point Relays[J]. Ad Hoc Networks, 2018, 77: 69-83.
[11] Wang Xudong, Mi Zhichao, Jiang Yuqing, et al. A Speed-Weighted OLSR Algorithm Based on Location Information[J]. Communication Technology, 2018, 51(12): 2885-2890.
[12] Zhou Changjia, Zhou Jianguo. A Routing Algorithm Suitable for UAV Networks Based on OLSR[J]. Computer Engineering, 2021, 47(10): 174-179,185.
[13] Yao Yukun, Zhang Benjun, Zhou Yang. Timely and Stable Routing Strategy Based on Q-learning Algorithm in UAV Ad Hoc Networks[J]. Application Research of Computers, 2022, 39(02): 531-536.
[14] Wang Jing, Li Fangfang, Yu Quan. An Optimized Routing Protocol for Wireless Mesh Networks Based on Link State Awareness[J]. Computer Science, 2012, 39(11): 37-40.
[15] Watkins J C, Dayan P. Technical Note Q-Learning.[J]. Machine Learning, 1992, 8(03): 279-292.
[16] Huang Xincheng, Chen Guangzu, Zheng Min, et al. QoS Routing Method for Flight Self-Organizing Networks Based on Q-learning[J]. Journal of the University of Chinese Academy of Sciences, 2022, 39(01): 134-143.
[17] Jin C, Allen-Zhu Z, Bubeck S, et al. Is Q-learning provably efficient?[J]. Advances in Neural Information Processing Systems, 2018, 31: 4868-4878.
[18] Xiong Ke, Jin Xin, Liu Qiang. QL-OLSR: An Optimized Mobile Ad Hoc Network Routing Protocol Based on Q-Learning Ideas[J]. Journal of Beijing Jiaotong University, 2020, 44(02): 66-73.
[19] Xu Jiuqiang, Li Hequn, Wang Jinfang, et al. Research on Routing Strategy Based on Edge Weight and Node Load[J]. Journal of Northeastern University (Natural Science Edition), 2015, 36(12): 1691-1695.
[20] Zhou Tong. Research on Load-Adaptive Multipath Transmission Methods in Mobile Ad Hoc Networks[D]. Shanghai: Shanghai Jiao Tong University, 2017. ★
★Scan the QR code to read and download this paper on CNKI
★Original article published in《Mobile Communications2023 Issue 10★
doi:10.3969/j.issn.1006-1010.20230825-0001
Classification Number: TN929.5 Document Identifier Code: A
Article Number: 1006-1010(2023)10-0017-07
Citation Format: Wang Bingyan, Zheng Xiangping, Jia Wenjie, et al. Q-Learning UANET Routing Protocol Based on Link Quality and Node Load Estimation[J]. Mobile Communications, 2023, 47(10): 17-23.
WANG Bingyan, ZHENG Xiangping, JIA Wenjie, et al. Q-Learning UANET Routing Protocol Based on Link Quality and Node Load Estimation[J]. Mobile Communications, 2023, 47(10): 17-23.
Author InformationWang Bingyan (orcid.org/0009-0001-3331-444X): Master’s student at the School of Communication and Information Engineering, Nanjing University of Posts and Telecommunications, majoring in wireless network protocol stack.Zheng Xiangping: Senior Engineer at Jiangsu Yongfeng Machinery Co., Ltd., primarily researching unmanned equipment.Jia Wenjie: Master’s student at the School of Communication and Information Engineering, Nanjing University of Posts and Telecommunications, focusing on mobile ad hoc networks.Li Dapeng: Professor and PhD supervisor at the School of Communication and Information Engineering, Nanjing University of Posts and Telecommunications, specializing in wireless communication and mobile ad hoc networks.
Submission method for《Mobile Communications》is online submission
Please log in to the web submission system
Link address:http://ydtx.cbpt.cnki.net
Highlights ReviewTable of Contents | Issue 10 of 2023 Special Topic: Mobile Ad Hoc NetworksTable of Contents | Issue 9 of 2023 Special Topic: 6G Intelligent Sensing6G Intelligent Sensing | Special papers from the 9th issue of 2023 (14 papers)IoT Technology for 6G | Special Issue of the 8th issue of 2023(11 papers)Integrated Networks of Air, Ground, and Sea | Special papers from the 7th issue of 2023
#Scan to Follow Us#《Mobile Communications》Uses Papers to Interpret Communication
《Mobile Communications》 magazine is supervised by China Electronics Technology Group Corporation and hosted by the Seventh Research Institute of China Electronics Technology Group Corporation. It is a “Double Effect Journal” in the Chinese journal matrix, a fine electronic journal of the Ministry of Industry and Information Technology of China, a source journal for Chinese science and technology papers, and included in the “Directory of High-Quality Science and Technology Journals” by the Chinese Association for Science and Technology. Domestic continuous publication number: CN44-1301/TN, International Standard Serial Number: ISSN1006-1010, Postal Distribution Code: 46-181.