CN101873663B - A Multipath Routing Algorithm Based on Energy Aware Reliability - Google Patents

Abstract

The invention provides a multi-path routing algorithm based on energy sensing reliability, which comprises the following steps: judging the reliability of links at first to select a link for data transmission, and collecting and promptly updating cost information of the path; forming a set of paths towards a target node, calculating the predicted function value for cost balance of the paths, and arranging the paths in an ascending order; selecting paths with disjoining nodes from a set of the paths; and utilizing the predicted function value to selecte an optimal path which satisfies the reliability criteria and leads to the target node. The algorithm guarantees the routing stability and reliability, reduces the energy consumption of the network, represents a comprehensive solution to the problem of criteria for sequencing path parameters, and has high practicability in the high-mobility wireless independent network environment.

Description

A Multipath Routing Algorithm Based on Energy Aware Reliability

technical field

The present invention proposes a multipath routing algorithm based on energy-aware reliability. Specifically, through the path cost balance prediction function, the QoS mechanism is considered comprehensively, and the energy and reliability mechanisms are used to judge path performance and obtain optimal routing.

Background technique

Wireless sensor network is a special AD-HOC network, which is an autonomous system composed of a series of mobile nodes, and the connection between nodes does not require the support of any base station and infrastructure. A higher and more effective network protocol is required to meet the network requirements for the channel errors that may be caused by the movement of network nodes and data transmission along this path. This feature requires wireless sensor networks to have higher requirements for QOS. In AD-HOC networks, most of them are single-path single-cost routing protocols. Through the document "Multi-path Routing in Mobil Ad Hoc Networks: Issues and Challenges", I learned that multi-path routing can improve communication bandwidth, balance load, increase packet transmission rate and link redundancy, and solve power loss and node mobility, etc. characteristics, especially for real-time data transmission. At the same time, multi-cost routing improves the QoS of the network by combining relevant important parameters as the cost vector of the path, and using the vector as the standard and basis for routing judgment. A key concept of the multi-cost routing algorithm described in the document "Implementing Distributed Multi-cost Routing in Mobile Ad HocNetworks Using DSR" is the dominance relationship between paths. Through a certain functional relationship, a good value is preferentially selected as a routing selection criterion.

R.Leung, J.Liu, E.Poon at all, proposed the MP-DSR algorithm in the document "A QoS-Aware Multi-Path Dynamic Source Routing Protocol for Wireless Ad-Hoc Networks", which is a multi-path unicast source routing Algorithm, this algorithm is a multi-path theory proposed on the basis of DSR single-path, and defines the end-to-end reliability of the network at the same time, based on the calculated path reliability value, finally finds multiple paths that meet the network reliability for data transmission.

The MP-DSR algorithm proposed by R.Leung, J.Liu, E.Poon at al has many deficiencies:

1) First, the algorithm only emphasizes the problem of path reliability, ignoring the importance of energy. In networks powered by batteries, efficient use of energy can improve network performance and lifetime.

2) Second, the algorithm uses the calculated path reliability values as parameters to arrange them in descending order, but does not consider the question of how to arrange paths with equal values according to which criteria.

Contents of the invention

The purpose of the present invention is to provide an effective weighing routing mechanism, specifically a multi-path routing algorithm based on energy-aware reliability.

The basic idea of the present invention is: the algorithm comprehensively considers path reliability and power consumption, and by mining energy and link relevance, combined with the problem of effective energy mechanism and path reliability, a path cost balance prediction function is proposed, and its The optimization function is used as a routing criterion, and finally an effective route with multiple disjoint nodes that meets end-to-end reliability requirements and consumes less energy is obtained, which comprehensively solves the problem of sorting criteria for path parameter values. The algorithm can ensure the stability and reliability of routing, and reduce the energy consumption of nodes in the network.

这里，k是路径，i，j是路径上的节点，P_i，j是节点i，j间的消耗功率即为传输功率，R^(k)是第k条路径的可靠性值；其具体步骤如下：The present invention is an energy-aware reliability-based multipath routing algorithm, which mainly uses energy and reliability as important parameter indicators, and establishes a cost balance prediction function by mining the relationship between energy and reliability

Here, k is the path, i, j is the node on the path, P _{i, j} is the power consumption between nodes i, j is the transmission power, R ^(k) is the reliability value of the kth path; its specific steps as follows:

1) Judging the reliability of the link, so as to select the link to send data, and at the same time collect the cost information of the path and update it in time.

First, the end-to-end reliability formula for parallel transmission according to the defined multiple disjoint paths: By initializing the route lookup algorithm, when the reliability of all paths is equal to the lowest path reliability value, the reliability index set by the network can still be satisfied, and the reliability formula is brought into the path to calculate the lowest reliability value of the path R _lower and The number n of paths to be searched by the source node. By comparing the utilization rate of the link to be searched with the minimum path reliability value, the source node finds at most n neighbor nodes satisfying the minimum path reliability and broadcasts.

2) Form a set of paths to the destination node, calculate the cost balance prediction function value of each path, and arrange them in ascending order; if the values are equal, arrange them in ascending order according to the number of hops, that is, select the priority arrangement with the least number of hops.

Update the path reliability value according to the formula R ^(k) (t) = ∏ _{(i, j) ∈ k} l _{i, j} (t), and add the power consumption values of the links passed, and put the above two values into in the node cache. The intermediate node broadcasts to at most n neighbor nodes that also meet the conditions, performs the above process, and finally obtains the path set of the destination node.

According to the path cost, get the balance prediction function value of each path cost

Among them, k is the path, i, j are the nodes on the path, P _{i, j} is the power consumption between nodes i, j is the transmission power, R ^(k) is the reliability value of the kth path.

At the same time, the prediction function value of each path in the set is calculated and arranged in ascending order. When the function values of the paths are equal, the path with the smallest number of hops is prioritized according to the number of hops.

3) Select the node-disjoint path from the path set, and use the prediction function value to select the optimal path to the destination node that satisfies the reliability condition.

The present invention calculates and compares with the existing classical MP-SDR algorithm through the network topology graph, the algorithm ensures the routing stability and reliability, and reduces the energy consumption in the network at the same time, in the high mobility wireless autonomous network environment, has Higher practicality.

The present invention is suitable for high-mobility wireless autonomous network environment. In this network model, each node is required to have a consistent transmission range through an omni-directional antenna; links can be added or deleted by changing the transmission range through nodes; the network topology is completely dependent on the transmission range , and the nodes can transmit data within the range not greater than the maximum transmission power; nodes in the network can understand the global information of the network status and topology through GPS positioning and other means; when the network load is high, the nodes do not tend to transmit in a longer range; Within the range of network node speed limit, the power consumption of nodes is proportional to the distance between nodes.

The routing algorithm in the present invention is used to construct an optimized balance function, that is, a path cost balance prediction function, according to network characteristics. By considering the node energy and reliability mechanism, the survival time of the network is finally extended, and the algorithm is more accurate and effective in the wireless sensor network that changes frequently with time.

Description of drawings

Figure 1 is a specific link cost topology diagram;

Fig. 2 is a schematic diagram of an embodiment of the present invention;

Fig. 3 is a schematic diagram of the comparison between the path set selected by the MP-DSR routing algorithm and the path set used by the algorithm of the present invention.

Detailed ways

An energy-aware reliability-based multipath routing algorithm of the present invention is specifically implemented as follows: the link availability rate and power consumption value between each node is known, and each node broadcasts to neighboring nodes that meet the conditions.

Here we set the end-to-end reliability value as R=0.6, initialize the routing search algorithm through the document "A QoS-Aware Multi-PathDynamic Source Routing Protocol for Wireless Ad-Hoc Networks", and obtain the number of searched paths n=2, the path The lowest reliability R _lower =0.4.

1) To judge the reliability of the link, first, select the link to send data, and collect the cost information of the path and update it in time. By comparing the link utilization rate to be found with the lowest path reliability value R _lower =0.4, the source node finds at most 2 neighbor nodes satisfying the minimum path reliability and broadcasts. The intermediate nodes execute the above process in sequence.

2) Form a set of paths to the destination node, calculate the cost balance prediction function value of each path, and arrange them in ascending order; if the values are equal, arrange them in ascending order according to the number of hops, that is, select the priority arrangement with the least number of hops.

Figure 1 is a specific link cost topology diagram. The link cost vector is denoted by (l _{i, j} , P _{i, j} ). i, j is the node on the link, l _{i, j} is the availability rate of the link, P _{i, j} is the power consumption of the link between nodes,

这里，k是路径，i，j是路径上的节点，P_i，j是节点i，j间的消耗功率即为传输功率，R^(k)是第k条路径的可靠性值。计算集合中各路径的预测函数值见表1；Update the path reliability value according to the formula R ^(k) (t) = ∏ _{(i, j) ∈} k l _{i, j} (t), and add the power consumption values of the links passed, and put the above two values into in the node cache. The intermediate node broadcasts to at most two neighbor nodes that also meet the conditions, performs the above process, and finally obtains the path set of the destination node. Balancing Prediction Functions According to Path Costs

Here, k is the path, i, j are the nodes on the path, P _{i, j} is the power consumption between nodes i, j is the transmission power, R ^(k) is the reliability value of the kth path. The prediction function values of each path in the calculation set are shown in Table 1;

Table 1 shows the selected path parameter values calculated through a specific topology map instance.

Arrange in ascending order, and get the path set as {④, ⑤, ③, ②, ①} Disjoint path selection algorithm proposed by R.Leung, J.Liu, E.Poon, get {④}R=0.513<0.6{ ④, ③}, R=1-0.487*(1-0.42)=0.7175>0.6 is the final selected path, as shown in Figure 2. In the figure, the thin line arrow represents the set of paths selected by applying the algorithm based on the cost balance prediction mechanism ; The thick arrow is the final path selected to satisfy the cost balance prediction function. According to Anand Srinivas, due to the use of omnidirectional antennas, the WMA (wireless multicast advantage) mechanism can be used to obtain the minimum energy value formula. According to this formula, the minimum energy consumed by routing in the network can be calculated.

$\mathrm{<span\; class="notranslate">\; \&epsiv;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; P</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; T</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; \&NotEqual;</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}\mathrm{<span\; class="notranslate">\; T</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; T</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\underset{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; \&NotEqual;</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\mathrm{<span\; class="notranslate">\; \&omega;</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 80</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 200</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 300</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 600</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1180</span>}$

3) Select node-disjoint paths from the path set in Table 2, and use the prediction function value to select the optimal path to the destination node that satisfies the reliability condition, S-A-D, S-B-C-D. Fig. 3 is a schematic diagram of the comparison between the path set selected by the MP-DSR routing algorithm and the path set used by the algorithm of the present invention. In the figure, the thin line arrows represent the set of paths selected by the MP-DSR routing algorithm, and the thick line arrows represent the final paths selected to meet the end-to-end reliability value.

Table 2 is the comparison of algorithm characteristics of DSR, MP-DSR, and cost balance prediction mechanism

Claims (1)

1. A multi-path routing algorithm based on energy-aware reliability, aimed at finding an effective route that meets end-to-end reliability requirements while energy consumption is low, characterized in that it comprises the following steps: 1) Judging the reliability of the link, so as to select the link to send data, and at the same time collect the cost information of the path and update it in time; First, the end-to-end reliability formula for parallel transmission according to the defined multiple disjoint paths:

By initializing the route lookup algorithm, when the reliability of all paths is equal to the lowest path reliability value, the reliability index set by the network can still be satisfied, and the reliability formula is brought into the path to calculate the lowest reliability value of the path R _lower and The number n of paths to be searched by the source node, by comparing the utilization rate of the link to be searched with the minimum path reliability value, the source node finds at most n neighbor nodes satisfying the minimum path reliability and broadcasts; 2) Form a set of paths to the destination node, calculate the cost balance prediction function value of each path, and arrange them in ascending order; if the values are equal, arrange them in ascending order according to the number of hops, that is, select the priority arrangement with fewer hops; Update the path reliability value according to the formula R ^(k) (t) = ∏ _{(i, j) ∈} k l _{i, j} (t), and add the power consumption values of the links passed, and put the above two values into In the node cache; The intermediate node broadcasts to at most n neighbor nodes that also meet the conditions, performs the above process, and finally obtains the path set of the destination node; Balancing Prediction Functions According to Path Costs

Among them, k is the path, i, j is the node on the path, P _{i, j} is the power consumption between nodes i, j is the transmission power, R ^(k) is the reliability value of the kth path; Calculate the prediction function value of each path in the set and arrange them in ascending order. When the function values of the paths are equal, the path with the smallest number of hops is prioritized according to the number of hops; 3) Select the node-disjoint path from the path set, and use the prediction function value to select the optimal path to the destination node that satisfies the reliability condition. the

Images