A Probabilistic Energy-Aware Model for Mobile Ad-Hoc Networks (Telecommunication Networks) (Analytical and Stochastic Modeling) Part 2

Measuring Energy Consumption

In this section we define a preorder over networks which allows us to compare the average energy cost of different networks but exhibiting the same connectivity behaviour. For this purpose we associate an energy cost with the probabilistic reductions as follows:

In other words, the energy cost to reach N from M in one single step is r if M can reach N after firing on a channel of radius1 r regardless of the message being transmitted is observable or not (or even lost). In the same way, if e =

is an execution then

Let H be a set of networks, we denote bythe set of all executions from M ending in H and driven by F which are not prefix of any other execution ending in H. More formally, H andsuch that

Now, we are ready to define the average energy cost of reaching a set of networks H from the initial network M according to the scheduler F .

Definition 4. Let H be a set of networks. The average energy cost of reaching H from M according to the scheduler F is

The average cost is computed by weighting the cost of each execution by its probability according to F and normalized by the overall probability of reaching H.

Definition 5. Let H be a countable set of sets of networks and F be a set of schedulers. We say that N is more energy efficient than M w.r.t. F and H,

scheduler and, for all schedulers

there exists a scheduler and, for all schedulers

Analysing the SW-ARQ and GBN-ARQ Protocols

High speed data transmission is rapidly becoming an essential requirement of today’s wireless networks. Consequently, adaptive modulation and coding (AMC) techniques are increasingly being used in most of 2.5/3g wireless networks in order to increase the transmission rate. At the same time, a wireless channel is error prone due to fading and other propagation impairments. To address this issue, many control schemes have been proposed. In particular the automatic repeat request (ARQ)-based error control is considered as very attractive to counteract the residual errors without using costly error correction codes at the physical layer (see, e.g., [13,6]). However, portable communication devices must rely on batteries with limited energy to conduct communication. There are three main ARQ protocols: stop-and-wait (SW), go-back-N (GBN) and selective repeat (SR). In this section, we use our framework to analyse both SW-ARQ and GBN-ARQ protocols. First, we show that the protocols exhibit the same observational behaviour, that is they are bisimilar. Then, we compute and compare their energy consumption under various scenarios depending on the stability of the wireless channel.

With respect to SW protocols, GBN takes advantage of the pipelining of the packets, i.e., a sequence of N packets can be sent without receiving any confirmation. This widely used technique is known to highly improve the throughput of the sender, but it is expensive from the energy consumption point of view [6] since correctly received packets may be required to be resent.

Modelling the Protocols. We consider a single transmitter node using ARQ-based error recovery to communicate with a receiver node over a wireless channel. Transmissions occur in fixed-size time slots. Moreover, we restrict to a one time slot.

Fig. 1. Topology of the network and mobility of s

The SW-ARQ-based protocol transmits one packet per slot while the GBN-ARQ-based one transmits n packets (i.e., the full capacity of the channel). For both protocols, the transmitter continuously sends packets until it detects a transmission error through a NACK feedback. Here, we consider an error-free feedback channel2 and assume that the acknowledgment (ACK) or negative acknowledgment (NACK) of each transmitted packet arrives at the sender node one slot after the beginning of its transmission slot. Therefore, the feedback of a packet is received exactly after its transmission for the SW-protocol and in case of a failure (NACK), the packet is automatically resent. Instead for the GBN-protocol, a feedback for the ith packet arrives exactly after the transmission of the (i + n — 1)th packet and in case of a failure the transmission restarts from the ith packet. We model both SW-ARQ and GBN-ARQ-based protocols for a communication channel of capacity n = 3 in our framework. We consider a unique static receiver. In order to take into account the two states nature of the channel, we model the transmitter as a mobile node send ((r, Js)) whose reachable locations are l1, which represents the "good state" of the channel, where the receiver lies within the transmission radius of the channel and l2 the "bad state", where the destination is no longer reachable (see Figure 1). The mobility of the sender is modelled by the two state Markov chain with the following transition probability matrix:

where p and q are the probabilities of the stability of the node in its good and bad states respectively.

In our analysis, we assume that the energy consumption of the feedback messages is negligible. Therefore, they are sent over channels with zero radius. For this reason the static receiver rec is located at l1 , i.e., at the same location of the sender in its good state, so that the feedback will be received with no cost. Note that the sender still transmits over channels with radius r and thus consuming r energy for each fired packet.

Fig. 2. Description and example of the network communications

The process executed by rec, the receiver node, is the same for both protocols and modelled as the process

which upon receiving packet pi over the channel ci, sends ACK (i) over the channel c, then waits for the next packet on ci+1.

For each channel ci, we use a static auxiliary node bi ((0,I)) located at l2, the bad state of the sender, capturing bad transmissions over ci. It executes the following process which upon receiving packet pi over the channel ci, sends NACK(i) over the channel c:

which upon receiving packet pi over the channel ci, sends NACK(i) over the channel c.

GBN-ARQ. Now we introduce the full model of the protocol GBN-ARQ.

We start by modelling its sender node. Recall that, as a simplifying assumption, the channel capacity is 3. It executes the following process:

where the process SEND is defined as follows.

Though that the feedback of a packet is received after the transmission of its two successors, for practical reason, we read a feedback of a packet right after sending it. Indeed, since we do not want feedback to be costly, both sender and receiver must be located at the same place when the feedback is sent. However, the sender node will verify it only after having sent the following two packets.

Recall that the receiver node in our modelling above, reads each packet p1 on its specific channel ci. Thus, in the GBN, if the transmitter sends p1 while being in its good state, then moves to bad and sends p2 and finally moves back to the good state and sends p3, then the later packet will not be read by the receiver as it is blocked on c2. Then, the firing on c3 is lost and this models the fact that packets sent after a bad packet is just a wasting of energy. But since the sender process GB(i) is blocked on the feedback channel c, we introduce a static auxiliary node loose ((0,I)) located at l1 and executing the process:

The full model of GBN protocol is as follows.

SW-ARQ. Now on to the SW-ARQ-based protocol.

This is very simple since it always sends one packet and waits for its feedback. The sender process is defined as follows.

The full protocol is then modelled as the network

Measuring the Energy Cost of the Protocols. This section presents the energy consumption of the above ARQ-based protocols. In order to compare the observational behaviours of the protocols, we assume that the communications over the feedback channel are observable for any observer node located at l1. Thus the protocols are equivalent w.r.t. a set of schedulers F if for all schedulers F in F driving one of the protocols, there exists a scheduler F ‘ in F driving the other one such that both protocols correctly transmit the same packets with the same probabilities. Schedulers constitute an essential feature for modelling communication protocols as they provide freedom in modelling implementation and incomplete knowledge of the system. However, many schedulers could be in fact unrealistic. Consider for example schedulers giving priority to communication actions over movements of the nodes. Such schedulers cancel the two states nature of the communication channel since the latter remains in the same state until there is no longer available communication action. Thus, if the network started with a good channel then all the messages will be transmitted correctly without enduring any lost. In contrast, if it started with a bad channel, then it will be retransmitting indefinitely the first packet since the channel remains always bad. Though, that under such schedulers, both SW-ARQ and GBN-ARQ protocols behave exactly the same way in terms of our observability, they represent however unrealistic implementation scenarios. Therefore, we consider the following set of schedulers denoted Falt which:

1. always alternates between sending packets and node’s movement so that at each interaction of the transmitter with the channel, the later can be either good or bad;

2. gives priority to acknowledgment actions (ACK and NACK) to model the standard assumption of an error-free feedback channel;

3. allows interaction with the outside environment only through its observable actions so that we capture exactly the observable behaviour of the protocol.

Under these assumptions, we can prove the following result which shows that both protocols exhibit the same observable behaviour.

Proposition 1.

We compare their energy efficiency in the context of the set where Hk means that all the packets up to k have been correctly transmitted and is defined aswhere

for some process P and

Then, we compute the energy consumption of the protocols assuming that we start by a move action at the good state so that the first message could be lost if it moves to the bad state3. The results are summarized in the following propositions and illustrated in Figure 3.

Proposition 2.

Proposition 3.

Proposition 3.

These results can be derived by applying the Chapman-Kolmogorv’s forward equations to compute the probability of consecutive failures in the sending of the same packet. Each of these failures (except the first) causes the waste of a number of sent packets equals to the window size. It can be observed that the number of wasted windows has a geometric distribution. Then, the mean of total packets sent to obtain a success, can be straightforwardly derived.

Fig. 3. Energy cost functions for SW and GBN protocols and their comparison

To conclude this section, we note that while both protocols increasingly enjoy bad performance in term of energy consumption when the channel deteriorates, i.e., when q is increasing (see Figures 3-(a) and 3-(b)), the GBN protocol deteriorates faster. Indeed, as illustrated by Figure 3-(c) as the channel deteriorates the additional energy required by GBN protocol to correctly transmit the same number of packets increases to infinite. Thus, the gain of having a high throughput results in a very high energy consumption.

Conclusion

We presented the Probabilistic E-BUM calculus for modeling both connectivity and energy-aware properties of mobile ad-hoc networks.

As a future work we plan to develop an observational preorder which, in one bisimulation step, checkes both observational equivalence and energy-aware preordering. We also plan to extend the model with different metrics and apply it for measuring the level of both sender- and receiver-centered interference.