Link selection in lossy communication networks

Abstract

The present disclosure encompasses establishing and maintaining a routing protocol based on a measured link metric p, such as for a smart grid communication system. A link between a first node such as a router A and a neighbouring second node B of a communication path from a source to a destination in a packet oriented communication network is selected wherein the two nodes are connected via first and second communication links. An updated link metric p(t+1) at a point in time t+1 of the first communication link is determined. The first or the second communication link is selected for transmitting a further packet from node A to node B by comparing the updated link metric p(t+1) to a threshold p.sub.thr.

Claims

1. A method of selecting a link between a first node A and a second node B of a communication path in a packet oriented communication network, wherein the two nodes A, B are connected via a first communication link and a second communication link, the two communication links are both modelled as Finite State Markov Channels (FSMCs) with two states, the method comprising: establishing a packet transmission observation for a packet being transmitted from node A to node B; determining an updated link metric p(t+1) of the first communication link, based on state transition probabilities and packet transmission success probabilities for the two FSMC states, a previous link metric p(t) and the latest packet transmission observation, wherein the link metric p(t) is a vector with a first component p.sub.1 and a second component p.sub.2 indicative of a condition of the two communication links, respectively; selecting the first or the second communication link for transmitting a next packet from node A to node B by comparing the updated link metric p(t+1) to a threshold p.sub.thr; and selecting the first communication link if the first component of the updated link metric p.sub.1(t+1) exceeds a threshold p.sub.thr depending on the second component P.sub.2(t+1), and selecting the second communication link if p.sub.1(t+1) is below the threshold p.sub.thr depending on the second component p.sub.2(t+1).

2. The method of claim 1, further comprising: determining an updated link metric p(t+1) of the second communication link, based on the state transition probabilities and the packet transmission success probabilities for the two FSMC states, the previous link metric p(t) and the latest packet transmission observation.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The subject matter of the invention will be explained in more detail in the following text with reference to preferred exemplary embodiments which are illustrated in the attached drawings, in which:

(2) FIG. 1 shows a schematic of nodes A and B connected via two links;

(3) FIG. 2 shows a plot of a packet transmission success rate versus time for low-rate low-power powerline communication links;

(4) FIG. 3 schematically shows a Gilbert-Elliott Markov model for a powerline link, and a single-state model for a wireless link;

(5) FIG. 4 shows a plot of a metric p=p(t) against an updated metric p′=p(t+1) for a selection of parameters; and

(6) FIG. 5 shows a decision region for a vector metric.

(7) The reference symbols used in the drawings, and their meanings, are listed in summary form in the list of designations. In principle, identical parts are provided with the same reference symbols in the figures.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

(8) FIG. 1 shows a first link 1 and a second link 2 linking a first node A and a second node B of a communication path from a source to a destination in a packet oriented communication network. The node A may be a router and the node B may be a neighbouring node. At least the first link 1 may have stochastic or time variable properties, thus modelled as a Finite State Markov Channel FSMC with two states, good and bad. Both links may be one of a power line or distribution line communication, PLC or DLC respectively, wireless, copper, or fiber-optic link.

(9) FIG. 2 shows for several links 1, 2 a plot of a packet transmission success rate 3 (packet delivery rate PDR) during a time of day 4. A high value represents a higher success rate, where 100 refers to ideal transmission, and a lower value represents a lower success rate, where a vanishing value refers to no transmission at all. The packet transmission rate 3 may vary drastically for different available links 1, 2. The variation may have different causes depending on the type of underlying link technology, e.g. for a wireless link shadowing may lead to an unsuccessful transmission. Time varying behaviour in wireless links occur due to occasional shadowing, however, these effects are typically measured in seconds or minutes, i.e. much faster than the time constants of PLC links.

(10) However, the plotted links 1, 2 are power transmission line links. PLC links 1, 2 are mainly affected by relatively slow processes such as switching of the power grid and activation of electrical equipment. Thus, state transitions typically occur only every few hours.

(11) For different technology the transmission success rate 3 may be different as a function of time or may vary more dramatically, e.g. for a wireless link in the case of loss of a direct line of sight the transmission success rate may vanish. However, the transmission success rate may be used to determine an updated link metric and to select a link 1, 2.

(12) FIG. 3 schematically shows a special case of a Finite State Markov Channel FSMC in a Gilbert-Elliott GE model for a powerline link 1, and a single-state model for a wireless link 1. The powerline link 1 is modelled as a GE channel with two states ‘good’ 5 and ‘bad’ 6, with packet transmission success probability p.sub.G 7 and p.sub.B 8, respectively. Where good and bad refers to p.sub.G 7 being greater than p.sub.B 8. The metric is further based on state transition probabilities λ.sub.1 9 and λ.sub.2 10 of the good 5 and bad 6 state of the GE model respectively. The wireless link ‘WL’ 2 is modelled simply by its constant average packet transmission success probability p.sub.W 11. This is justified by the fact that typical wireless links in a Smart Grid application are fixed installations and operate in a steady state.

(13) In principle, a transmitter selects on which link to transmit a packet, based on its current information, as represented by the metric or so-called belief state, i.e. the probability of the powerline channel being in a the good state. Assuming that p.sub.B<p.sub.W<p.sub.G, the transmitter selects the PLC link 1 if the PLC link 1 is believed to be in the ‘good’ state 5, since it has a higher success probability 10 than the wireless link, p.sub.W<p.sub.G, and selects the wireless link 2 otherwise.

(14) However, at time a t of the transmission, the transmitter does not know the current state of the links 1, 2, but must predict it based on earlier observations. These observations are the confirmations or acknowledgments obtained by the underlying transmission protocol whether a packet transmission has succeeded earlier. The protocol specifies how the transmitter updates the link information, given these partial observations of the Markov states 5, 6, and how to use it in a threshold policy.

(15) FIG. 4 shows a plot of a metric p=p(t) against an updated metric p′=p(t+1) for a selection of parameters, with parameters λ.sub.1=0.05, λ.sub.2=0.99, p.sub.G=0.95, p.sub.B=0.15. Depending on the acknowledgement or observation of the packet transmitted earlier the link metric or belief at time t+1, p(t+1) may be updated. For a successful transmission, i.e. an observation “ack”, the metric update may be according to the following equation

(16) $p^{\prime }\left(t+1\right)=\frac{{\lambda }_1{p}_{G}p\left(t\right)+{\lambda }_2{p}_B\left(1-p\left(t\right)\right)}{p_{G}p\left(t\right)+p_B\left(1-p\left(t\right)\right)}.$

(17) For an unsuccessful observation, i.e. an observation “nak”, the metric or belief p may be updated according to the following equation

(18) $p^{\prime }\left(t+1\right)=\frac{{\lambda }_1\left(1-p_G\right)p\left(t\right)+{\lambda }_2\left(1-p_B\right)\left(1-p\left(t\right)\right)}{\left(1-p_G\right)p\left(t\right)+\left(1-p_B\right)\left(1-p\left(t\right)\right)}.$

(19) Thus, the metric follows the trend p.sub.ack 12 for a successful earlier transmission, i.e. an observation “ack”. The belief increases rapidly from a low value, e.g. subsequent successful transmission leads to the belief that the link 1 is in a good state 5.

(20) The metric follows the trend p.sub.nak 13 for an unsuccessful earlier transmission, i.e. an observation “nak”. The belief decreases rapidly from a high value, e.g. subsequent transmission failure leads to the belief that the link is in a bad state 6.

(21) In case no information on an earlier transmission on link 1 is available, i.e. the transmission occurred through link 2, the metric follows the trend p.sub.none 14.
p(t+1)=λ.sub.1p(t)+λ.sub.0(1−p(t))

(22) Thus the belief on the current state 5, 6 is propagated only according to FSMC parameters, until further information on the link 1 is available.

(23) FIG. 5 shows a decision region 15, 16 for a vector metric consisting of metrics p.sub.1 and p.sub.2. A vector metric is used in case multiple links 1, 2 are modelled as an FSMC, thus two metrics p.sub.1 and p.sub.2 are to be considered. The decision region 15, 16 then allows making a selection on which link to choose for transmitting a next packet.

(24) The plot shown in FIG. 5 depicts the case of two FSMC links 1, 2. The plot is divided into two decision regions 15, 16. The area in which the vector metric (p.sub.1, p.sub.2) lies specifies the optimum action to be taken by the transmitter. The calculations involved are more complex in the multiple FSMC case. However, this can be pre-calculated for a given set of GE model parameters.

LIST OF DESIGNATIONS

(25) 1, 2 Link 3 Transmission success rate 4 Time 5 Good state 6 Bad state 7 Transmission success probability p.sub.G 8 Transmission success probability p.sub.B 9 State transition probability λ.sub.1 10 State transition probability λ.sub.2 11 Transmission success probability p.sub.W 12 Trend p.sub.ack 13 Trend p.sub.nak 14 Trend p.sub.none 15, 16 Decision region