CN103108372A - Interference sensing cross-layer routing method based on node sending and receiving capacity - Google Patents

Abstract

The present invention is an interference-aware cross-layer routing method based on node sending and receiving capabilities. The method is based on the 802.11MAC layer and defines parameters for measuring node sending and receiving capabilities.

, these two parameters can reflect the strength of interference around the node and the degree of communication load on the node; on this basis, a new routing criterion is defined in combination with the MAC layer and the network layer, and the new criterion is related to the number of active neighbor nodes around , the number of data streams passing through the node, the ability of the node to access the channel, and the topology changes around the node, which can more comprehensively reflect the real situation of the network. The present invention aims at reducing the interference suffered by the route, and selects the path with the largest comprehensive capacity of the bottleneck node or the path with the least interference of the bottleneck link as the route, thereby reducing the average end-to-end time delay and packet loss rate, and improving the throughput .

Description

Interference perception cross-layer routing method based on node sending and receiving ability

Technical field

The present invention relates to a kind of implementation that is used in particular for cross-layer routing in Ad Hoc network, belong to communication technical field.

Background technology

Ad Hoc network (MANETs) is a kind of multi-hop wireless network without the center self-organizing, and node both can be used as main frame and router enters or deviated from network freely.But due to any mobility of node, network topology can change frequently, and often unpredictable.Therefore the How to choose route that arrives destination node has become the problem of the important and core of of AdHoc network.Because MANETs is exclusive, the design of the cross-layer of Routing Protocol has become irresistible trend, and the main thought of cross-layer design is the correlation of utilizing each layer, increases

Thereby vertical communication between layers reduces the waste raising network performance that internodal level communication reduces resource.

Traditional ad hoc Routing Protocol adopts jumping figure as the metric parameter of Route Selection, but the minimum path of jumping figure and do not mean that to be exactly optimal path, so need to introduce new route index.At present, MAC layer and network layer are carried out some researchs of cross-layer design and think: interference is relevant with the number of neighbor node, and interference is defined as the weighting of neighbor node number in the different communication scope.Will there be two problems in this: 1. for certain node in network, not all neighbor node all can produce disturb it, only is selected as working node that route is used for forwarding and receive grouping and just can produces it and disturb.2. node will be added up the transmission HELLO broadcast packe in the necessary cycle of information of neighbor node fully, and this not only increases work load to node, and more seriously the performance of network also can be because of cycle transmission and the reduction greatly of broadcast packet.Other researchs have proposed to weigh the parameter of node access capability based on MAC layer re-transmission policy, with the busy extent that embodies channel around node and the ability of seizing channel thereof, and select the strong node of access capability as path node.two problems of this same existence: the ability that 1. accesses channel from the viewpoint definition node of MAC layer number of retransmissions, can not effectively reflect real situation, the parameter that can directly reflect the ability of MAC layer access channel is network allocation vector NAV((Network Allocation Vector), because NAV has pointed out channel and has been in the duration of busy condition, during this period of time node can not send information, in other words, node during this period of time can not access channel, at a time, the value of the interior NAV of section is larger, the possibility that shows the channel of interior nodes access during this period of time is less.2. only considered the transmitting capacity of node and ignored the receiving ability of node, even node has very strong transmitting capacity, if receiving ability is very poor, grouping can not in time receive and forward, and finally affect the performance of network.

Summary of the invention

Technical problem:The purpose of this invention is to provide a kind of interference perception cross-layer routing method based on node sending and receiving ability.The transmitting capacity that should consider node when the method requires to set up route is considered the receiving ability of node again, they with enliven the neighbor node number on every side, topology variation situation is relevant on every side through the ability of the data flow number of node, node access channel and node; Utilize the route that the method is set up to improve significantly network

Performance.

Technical scheme:The present invention aims to provide a kind of interference perception cross-layer routing method based on node sending and receiving ability.The method comprises:

A. define and computing node transmitting capacity and node time departure, for integration capability and the suffered interference of link of computing node are prepared.Take Fig. 1 as example, node C sends and belongs to data flow S

The ability of D grouping

Belong to data flow S with reception

The ability of D grouping

Be respectively:

Wherein,

Expression node C is in the probability of transmission state;

When expression node C can send grouping, the next one grouping of transmission was to belong to data flow S

The probability of D;

Expression node C is data flow S

D successfully preengages the probability of channel;

Expression node C after channel, will belong to data flow S in reservation

The probability that sends to down hop of the grouping success of D, they all can be tried to achieve by formula (2).

B. the suffered interference of computing node integration capability and link is prepared for defining new route criterion.Set

The expression source node S is to destination node D's

Paths, set

The expression path

Comprise

Individual sequence node, node

It is node Upper hop, node Integration capability be:

Or

Wherein,

,

With

Represent respectively node Transmission belongs to data flow S Ability and the reception of D grouping belong to data flow S

The ability of D grouping,

The expression node

Transmission belongs to data flow S

The ability of D grouping, they can be tried to achieve by formula (1), (2), (3).

Link ( ,

) suffered interference is:

C. the route criterion that redefines.The node that defines integration capability minimum in certain paths is that bottleneck node, the maximum link of interference are bottleneck link.Select path or the bottleneck link of bottleneck node integration capability maximum to disturb minimum path as route, namely the route criterion is:

Or

D. Route establishment process.

If it is expired that d1. source node does not arrive route or this route of destination node, calculate the ability value (transmitting capacity and integration capability) of oneself and insert route inquiry message RREQ grouping, node sends this RREQ grouping towards periphery;

D2. intermediate node operates below execution after receiving this RREQ grouping successively:

1. judge whether to receive the RREQ grouping of identical source node sequence number, abandon this RREQ grouping if having; Do not register this RREQ grouping.

2. calculate own ability value, according to new route criterion foundation or upgrade reverse route;

If 3. intermediate node is destination node, the ability value of oneself is inserted the respective regions that route is answered the rrep message grouping, send RREP message to source node; Otherwise give other node with the RREQ forwarding of packets after the ability value in renewal RREQ grouping, until destination node is received the rear transmission of this RREQ grouping RREP grouping.

D3. source node after receiving that destination node is issued the RREP message of oneself, recomputates the suffered ability value of oneself, sets up or renewal forward direction route according to new route criterion.

Useful result:The present invention has utilized the mechanism of cross-layer to propose in a MANETs method for routing based on node transmitting capacity and receiving ability, the route of utilizing the method to set up has minimum bottleneck link to be disturbed, and can improve significantly the network performances such as average end-to-end delay, throughput, packet loss.This routing algorithm is a kind of typical proactive routing protocol, is applicable to disturb in network larger network.

Description of drawings

Fig. 1 is defined node transmitting capacity and receiving ability.

Fig. 2 is that IEEE 802.11 DCF receive the flow chart when dividing into groups.

Fig. 3 is new routing algorithm cross-layer structure schematic diagram.

Fig. 4 is the workflow diagram of new routing algorithm.

Embodiment

In 9 nodes of network shown in Figure 1, there are 5 data flow, be respectively S

D, S1

D, S2

D, S3

D, S4

D。Be easy analysis, suppose transmitting data stream S1

D, S2

D, S3

D, S4

The route of D is set up, and will set up transmitting data stream S now

The route of D, and Node B has sent route requests grouping RREQ(Route Request) to node C, defined node C sends and belongs to data flow S now

The ability of D grouping

Belong to data flow S with reception

The ability of D grouping

As follows.

$\mathrm{CAP}+{\mathrm{SEND}}_C^{S\→D}=P_{\mathrm{send}\_{\mathrm{state}}_C}^{S\→D}\·P_{{\mathrm{service}}_C}^{S\→D}\·P_{\mathrm{contention}\_{\mathrm{success}}_C}^{S\→D}\·P_{\mathrm{deliver}\_{\mathrm{success}}_C}^{S\→D}---\left(1\right)$

Wherein,

$\left\{\begin{array}{c}{P}_{\mathrm{send}\_{\mathrm{state}}_C}^{S\→D}=\frac{T-T_{\mathrm{contention}}}{T}\\ P_{{\mathrm{service}}_C}^{S\→D}=\frac{1}{\mathrm{num}\_{\mathrm{flow}}_C+1}\\ P_{\mathrm{contention}\_{\mathrm{success}}_C}^{S\→D}=\frac{1}{N}\underset{i=1}{\overset{N}{\mathrm{\Σ}}}\frac{\mathrm{num}\_{\mathrm{rts}}_{\mathrm{not}\_{\mathrm{retry}}_C}^{S\→D}}{\mathrm{num}\_{\mathrm{rts}}_{{\mathrm{total}}_C}^{S\→D}}\\ P_{\mathrm{deliver}\_{\mathrm{success}}_C}^{S\→D}=\frac{1}{N}\underset{i=1}{\overset{N}{\mathrm{\Σ}}}\frac{\mathrm{num}\_{\mathrm{data}}_{\mathrm{not}\_{\mathrm{retry}}_C}^{S\→D}}{\mathrm{num}\_{\mathrm{data}}_{{\mathrm{total}}_C}^{S\→D}}\end{array}\right.---\left(2\right)$

$\mathrm{CAP}\_{\mathrm{SEND}}_C^{S\→D}=\mathrm{CAP}\_{\mathrm{RECV}}_B^{S\→D}---\left(3\right)$

In formula (1):

1.

Expression node C is in the probability of transmission state.It is defined as: in the period, node C is in non-competing time period (T-T at T _Contention) shared ratio.

2.

When expression node C can send grouping, the next one grouping of transmission was the probability that belongs to data flow S → D.Because four (num_flow have been arranged this moment _C=4) data flow is through node C, if data flow S → D also will pass through node C, so according to formula (2), the probability that the grouping of the next one of transmission belongs to data flow S → D is 1/5.

3. Expression node C is the probability that data flow S → D successfully preengages channel.It is defined as node C at nearest N T in the period, the RTS number of the non-re-transmission that belongs to data flow C → D of transmission With the total number of RTS grouping that belongs to data flow C → D that sends

The mean value of ratio.

4.

Expression node C after channel, will belong to the probability that sends to down hop of the grouping success of data flow S → D in reservation.It is defined as node C at nearest N T in the period, the DATA of the non-re-transmission that belongs to data flow S → D of the transmission number of dividing into groups With the total number of DATA grouping that belongs to data flow S → D that sends

The mean value of ratio.

About the definition of node C transmitting capacity, node C has been described if the packet that will belong to data flow S → D of success sends in formula (1) and (2), must have satisfied simultaneously following four conditions:

1. node C will be in the transmission state.Because each node has only been installed an antenna, node C can not be in the transmission state always, also will be in accepting state within some period.In order to calculate the probability that is in the transmission state at certain section time interior nodes C, at first to analyze the 802.11MAC layer, Fig. 2 is node IEEE802.11DCF when receiving grouping ^[10]The processing procedure of agreement mainly is described below.

(1) if node is idle, receiving other grouping, does not turn step (2), otherwise turn step (3);

(2) if received power less than the signal threshold level, the network allocation vector NAV(NAV with oneself has pointed out that channel is in the time of busy condition, be in fact a timer, during this period of time node must not send information) be adjusted into an extended inter frame space EIFS(Extended Interframe Space) length (sign

Shown in), turn step (6), otherwise turn step (4);

(3) if signal interference ratio greater than certain threshold value, is adjusted the NAV(sign of oneself

Shown in), turn step (6), otherwise turn step (5);

(4) receive current group, adjust the NAV(sign of oneself according to " duration field " in grouping

Shown in), turn step (6);

(5) grouping bumps, and abandons grouping, adjusts the NAV(sign of oneself

Shown in), turn step (6);

(6) carrying out next round receives.

In Fig. 2,

,

,

,

The link that meeting knot modification NAV makes node delayed delivery grouping everywhere.As long as also in work, node just can not send grouping to the NAV timer of node, can only be used for receiving grouping.The length of NAV is directly proportional to the number of enlivening the neighbor node node of receive data (namely refer to send or) on every side, enlivens the neighbor node number more, and the competition time will be longer, and node is in the probability of transmission state will be lower.So factor of using The probability that approximate representation node C is in the transmission state is reasonably,

Be inversely proportional to the number of enlivening neighbor node around node C.

2. next grouping of node C transmission must belong to data flow S → D.For a certain node in network, may more than data fail to be convened for lack of a quorum through its forwarding, himself may be also the source of data flow.Here we suppose that node is that the probability that data flow is served equates, so just can use Classical Probability Spaces to obtain the probability that node C is data flow S → D service, the i.e. factor

Its number with the data flow of process node C is inversely proportional to.

3. the reservation that node C must be successful is to channel.Before node C is ready for sending and belongs to the packet of flowing S → D, must first remove competitive channel, in IEEE802.11DCF, node is by sending RTS packet reservation channel, if preengage the unsuccessful RTS grouping of retransmitting, until preengage successfully or re-transmission abandons packet during over certain number of retransmissions (maximum is 6).So factor

Reflected that node C node and live-vertex on every side seize the ability of channel, if node C successfully receives the CTS frame, represented the channel booking success and begin next step transmission.

4. after channel booking success, node C must will belong to data flow S-〉the sending of the grouping success of D.Node C will begin transmission of data packets in the reservation of success after channel.Similar with channel booking, if send unsuccessfully, node C can retransmitted data packet, until sends successfully or re-transmission abandoned over certain number of times (maximum is 3) time.So factor

Reflected the network topology change situation of node when reservation sends data after channel, because the AdHoc nodes is removable, probably there is (perhaps a collection of) active node to move to this node direction this moment, transmit with this secondary data and clash, node will have to retransmit the DATA frame, the Internet resources and the time that have consumed when preengaging channel to not wasting.

The definition of the node receiving ability that formula (3) provides represents: the receiving ability of present node equals the transmitting capacity of upstream node.This is because as long as upstream node has successfully sent grouping to downstream node, just represent that downstream node has successfully received grouping.

In sum, the definition of node transmitting capacity combines the number of the data flow of enlivening neighbor node number, process node on every side, ability, these four factors of node ambient network topology variation situation that node is seized channel.And the suffered interference of these four factors and node is directly related, so the transmitting capacity of node can be interpreted as to a certain extent the size of the interference that node is suffered, the suffered interference of the larger expression node of transmitting capacity is less, and vice versa.What like this, in fact the receiving ability of node represented is the size that upstream node is disturbed.

If set

The expression source node S is to destination node D's

Paths, set

The expression path

Comprise Individual sequence node, node

It is node

Upper hop, our defined node

Integration capability be:

（4）

Wherein,

,

With

Represent respectively node

Transmission belongs to data flow S

Ability and the reception of D grouping belong to data flow S

The ability of D grouping, their definition and formula (1), (2), (3) are identical.Formula (4) illustrates that the integration capability of node is the transmitting capacity of node and the weighting of receiving ability, and namely the size of integration capability is by transmitting capacity and the common decision of receiving ability.

Can be write as following form according to formula (3) formula (4):

（5）

According to 3.2 parts, the transmitting capacity of node can be regarded as the size of the suffered interference of node, so can find out node from formula (5)

Integration capability also can be regarded as link (

,

) size that is disturbed, that is:

（6）

The integration capability of node is larger, and the suffered interference of corresponding link is less, and vice versa.What therefore, in fact the size of the integration capability of individual node reflected is the degree that adjacent double bounce is disturbed.3.2 part is pointed out, the interference of our definition is relevant with topology variation situation around the ability of enlivening neighbor node number, the data flow number that passes through node, node access channel on every side and node, compare with other great majority researchs, the interference of our definition more can comprehensively reflect the truth of network.

Based on the integration capability of node, we define new route criterion (RM) and are:

（7）

According to formula (6), formula (7) also can be write as following form, and both are of equal value.

（8）

The node that defines integration capability minimum in certain paths is that bottleneck node, the maximum link of interference are bottleneck link.Like this, newly Routing Protocol will select the path of bottleneck node integration capability maximum or bottleneck link to disturb minimum path as route.

It is that criterion is set up route that traditional Routing Protocol all is based on minimum number, yet the interference that the path of jumping figure minimum may be suffered is very large, affects network performance.For this reason, new route criterion is no longer based on jumping figure, but utilizes the mechanism of cross-layer to select best route based on the sending and receiving ability of node.

Fig. 3 has shown the contact between each layer when in new routing algorithm, node is worked.We can find out from figure, and in route finding process, network layer is set up route according to the situation of link layer and neighbor node competitive channel on every side, the channel booking probability of success and through the number of the data flow of node; In the route keep-process, network layer is by exchanging cross-layer feedback information maintaining routing list with link layer.

New routing algorithm expands from AODV, respectively adds two ability codomains at the head that RREQ divides into groups and RREP (Route Reply) divides into groups: the node transmitting capacity

With the node integration capability

Wherein,

To use according to the integration capability that formula (5) calculates self to down hop, and

To select route to use to next-hop node according to the route criterion of formula (7).The network layer of each node and link layer have a single-track link table, chained list in network layer is used for recording the traffic flow information by node, the chained list of link layer is used for being recorded as each data flow and sends information that RTS grouping and DATA divide into groups, and two chained lists are real-time update all.

Fig. 4 is that node A will set up in the situation of route with Node B, the course of work of new routing algorithm, and detailed process is as follows.

If it is expired that a) node A does not arrive route or this route of destination node, insert the RREQ grouping according to the ability value (transmitting capacity and integration capability) of formula (1), (2), (5) calculating oneself, node sends this RREQ grouping towards periphery;

B) Node B operates below execution after receiving this RREQ grouping successively:

1. judge whether to receive the RREQ grouping of identical source node sequence number, abandon this RREQ grouping if having; Do not register this RREQ grouping;

2. calculate the ability value of oneself, set up or upgrade reverse route according to new route criterion (7);

The ability value that 3. will just calculate be filled into RREP disappear the grouping in, send to node A;

C) node A after receiving the RREP message that Node B is sent, recomputates the ability value of oneself and sets up or renewal forward direction route according to criterion (7).

It should be noted that: 1. in the route discovery stage, new algorithm regulation: though intermediate node have the active ways that arrives destination node by, do not allow it to reply RREQ yet, this be because each node maintenance be the ability value of himself, this value constantly changes with the network real-time status; 2. do not need to broadcast the HELLO information block, this has also reduced network overhead to a certain extent.

Claims (1)

1. An interference-aware cross-layer routing method based on node sending and receiving capabilities, characterized in that the method comprises: a. Calculate node sending capability and node departure time, node C's ability to send packets belonging to data stream S→D

and the ability to receive packets belonging to data stream S→D

They are:

in,

Indicates the probability that node C is in the sending state;

Indicates that when node C can send a packet, the probability that the next packet to be sent belongs to the data flow S→D;

Indicates the probability that node C successfully reserves a channel for data flow S→D;

Indicates the probability that node C will successfully send a packet belonging to data flow S→D to the next hop after reserving the channel; b. Calculate the comprehensive capability of nodes and the interference on the link: the set Paths={P ₁ ,P ₂ ,...,P _m } represents m paths from the source node S to the destination node D, the set

Indicates the l node sequence contained in the path P _t , the node

is a node

The last hop of node

The comprehensive ability is:

or

in,

and

represent nodes respectively

the ability to send packets belonging to data stream S→D and the ability to receive packets belonging to data stream S→D,

represents a node

The ability to send packets belonging to the data stream S→D, the link

The interference received is:

c. Calculate routing criteria: define the node with the smallest comprehensive ability in a certain path as the bottleneck node, the link with the greatest interference as the bottleneck link, select the path with the largest comprehensive ability of the bottleneck node or the path with the least interference of the bottleneck link as the route, That is, the routing criterion is:

or

d. Routing establishment process d1. If the source node does not have a route to the destination node or the route has expired, calculate its own ability value, that is, the sending ability and comprehensive ability, fill in the routing inquiry message RREQ (Route Request) packet, and send this RREQ packet to the surrounding nodes; d2. After receiving the RREQ packet, the intermediate node performs the following operations in sequence: ①Judge whether there is a RREQ packet with the same source node serial number received, if so, discard the RREQ packet; if not, register the RREQ packet; ②Calculate its own capability value, and establish or update the reverse route according to the new routing criterion; ③ If the intermediate node is the destination node, fill in its capability value into the corresponding area of the route reply message RREP (Route Reply) packet, and send the RREP message to the source node; otherwise, update the capability value in the RREQ packet and forward the RREQ packet to Other nodes, until the destination node sends the RREP packet after receiving the RREQ packet; d3. After receiving the RREP message sent by the destination node, the source node recalculates its own capability value, and establishes or updates the forward route according to the new routing criterion. the

Images