<figure><img src="image_1.png" /></figure>

HAL
open science

# A Power Adjusting Algorithm on Mobility Control in Mobile Ad Hoc Networks

Jianrui Yuan, Jintao Meng

<figure><img src="image_2.png" /></figure>

## ► To cite this version:

Jianrui Yuan, Jintao Meng. A Power Adjusting Algorithm on Mobility Control in Mobile Ad Hoc Networks. 8th Network and Parallel Computing (NPC), Oct 2011, Changsha., China. pp.214-231, 10.1007/978-3-642-24403-2_18. hal-01593033

HAL Id: hal-01593033

https://inria.hal.science/hal-01593033

Submitted on 25 Sep 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Power Adjusting Algorithm on Mobility Control in Mobile Ad Hoc Networks

Jianrui Yuan · Jintao Meng

Received: date / Accepted: date

**Abstract** Power saving is one of the key issues in mobile ad-hoc networks (MANET), while previous researches in MAC layer are mostly focused on improving the channel utilization by adopting variable-range transmission power control. In this paper we focus on the power savings in the network layer, and propose a power adjusting algorithm (we term it PAA). In the presence of mobile host's mobility, PAA is designed to conserve energy by adjusting the transmission power to maintain the route's connectivity and restarting the route discovery periodically to find the new better route dynamically. After analyzing the operations of PAA, we find that the length of route discovery restarted period is a critical argument which will affect power saving, so we propose an optimizing model which finds the optimal value of this argument by analyzing the energy consumption of this algorithm. PAA can handle the mobility of MANET by adjusting the transmission power and in the meantime save energy by restarting route discovery periodically to balance the energy consumption on route discovery and packets delivering. It is suggested that PAA can be implemented in the dynamic source routing protocol (DSR). Simulation results are provided, which demonstrate DSR embedded with PAA saves nearly 40% energy compared to DSR without PAA in the presence of high mobility.

**Keywords** Mobile ad-hoc networks (MANETs) · Power control · Dynamic Source Routing (DSR) · Mobility control · Power efficiency

Jianrui Yuan

Department of Computer Science, Central South University, Changsha 410083, PR. China.
she is also with High Performance Computing Center, Shenzhen Institutes of advanced Technology, Shenzhen 518055, PR. China.

E-mail: yuan.jianrui@gmail.com

Jintao Meng

High Performance Computing Center, Shenzhen Institutes of advanced Technology, Shenzhen 518055, PR. China.

E-mail: meng.jintao@gmail.com

Correspondence to Jintao Meng, E-mail: meng.jintao@gmail.com, Tel: 0755-86392368.
# 1 Introduction

Mobile ad-hoc network (MANET) is a kind of wireless networks with mobile hosts (MHs), it was deployed without any fixed routers, and all nodes are capable of movement and can be connected dynamically in an arbitrary manner. Two mobile hosts can communicate with each other either directly or indirectly. Nodes of these networks function as routers which discover and maintain routes to other nodes in the network. Representative environments of the mobile ad-hoc network applications are fleets in oceans, natural disasters, and battle fields. Some or all of the nodes in a MANET may rely on batteries or other exhaustible energy resources. As such, one of the most important system design requirements in MANETs is power saving [1].

Power saving operations in MAC protocol is initially discussed in [2], [3]. By introducing the appropriate distributed active-sleep schedule for each node, the authors of [2] propose an efficient power saving MAC protocol for multi-hop mobile ad hoc networks called p-MANET, which avoids power consumption by activating mobile node during one beacon interval for every n interval, where n is the size of a super frame. The authors of [3] propose an on-demand power management framework for ad hoc networks. In this framework nodes that are not involved into delivering may go to sleep to adapt to the traffic load, which will save energy in the ad-hoc network. These two algorithms are both energy-saving schemes which are adaptive to traffic load. The present paper, however, studies the power saving issue in MANETs from a different perspective. Rather than adaptive to traffic load, our algorithm presented in this paper is adaptive to MHs' mobility, which can be implemented in the existing routing protocols in MANETs to achieve energy efficiency and maintain network connectivity simultaneously. Recent power control developments for MANETs also include the transmission power control mechanisms (e.g. [4], [5], [6]) for increasing channel utilization, and the distributed protocol [7] for interplaying between the MAC and network layers. Motivated by these works, in this paper we introduce a novel power control mechanism into the network layer to control the mobility, which can conserve energy and maintain network connectivity in MANETs. With the aid of this power control method, we are able to design an algorithm which is shown to be promising in conserving energy in both MAC layer and network layer when implemented in the routing protocols.

The recently routing protocols designed for wireless ad hoc network include the notable Dynamic Source Routing (DSR) Protocol [8] and Ad-hoc On Demand Distance Vector Routing (AODV) protocol [9]. DSR is a routing protocol for wireless ad hoc networks. This protocol uses source routing, in which all the routing information is maintained and dynamically updated at mobile nodes. It has two major phases, namely Route Discovery and Route Maintenance. These two functions work together to enable any host in the ad hoc network to dynamically discover and maintain a route to any other host in the network. The source broadcasts a Route Request (RREQ) message to find a route, Route Reply (RREP) is then generated if the message has reached the intended destination node. AODV builds routes using a route request & route reply query cycle. When a source node desires a route to a destination for which it does not already have a route, it broadcasts a RREQ packet across the network. A node receiving the RREQ may unicast a RREP back to its source or rebroadcasts the RREQ depending on if it is the destination or not. Nodes keep track of the RREQ's source IP address and broadcast ID. As the RREP propagates back to the source, nodes set up
forward pointers to the destination. Once the source node receives the RREP, it may
begin to forward data packets to the destination.

These routing protocols are usually sensitive to the mobility of MHs. The MH's mobility frequently cause the route to be broken, due to the fact that the receiver frequently moves out of the transmission range of the sender. In DSR, if some active link is broken, the downstream neighbor is currently unreachable. Then the node broadcasts a Route Error (RERR) packet back to the source, indicating that the route topology has changed, the source node must start route discovery by broadcasting the RREQ packet to find a new path in this case. In AODV, some periodic hello messages can be used to ensure symmetric links, as well as to detect link failures [14]. Once the next hop becomes unreachable, the node upstream of the break first repair the failed link locally, if it failed then the node propagates an unsolicited RREP to all active upstream nodes. Upon receiving notification of a broken link; source nodes can restart the discovery process if they still require a route to the destination. Even though there is certain mechanism of route maintenance implemented in these protocols to maintain network connectivity in the presence of mobility of MHs, it is still a challenge how to schedule the two schemes, namely route discovery and route maintenance so as to reach a state of global power saving. Therefore, this paper is aimed at designing an algorithm to control mobility and also save energy by balance the energy consumption on route discovery and packets delivering.

We apply power control into the routing protocol design in MANET for long lived
flow, e.g. the TCP flow in MANET. We focus on the power saving in both MAC
layer and network layer, and propose a power adjusting algorithm (PAA). The main
techniques in PAA are

1. Conserving power in the routing protocol, this includes the power consumed on both route discovery and data transmission.

2. Adjusting transmission power in the presence of MHs' mobility to keep the route's connectivity when the packets are transmitting on this route.

3. Restarting the route discovery after an appropriate period to find a new better route for data transmission.

Therefore, PAA is essentially a period schedule which introduces the adjustable transmission power control, and periodically restarts the route discovery to balance the energy consumption on route discovery and packets delivering. This algorithm can be implemented within both DSR and AODV. In the simulation DSR is selected to be implemented with PAA for its simple schedule on route maintenance, and the simulation result shows that the DSR with PAA saved nearly 40% energy compared to the DSR without PAA.

The remainder of this paper is organized as follows. In Section 2, the propagation model, mobility model, and network assumptions used in this paper are introduced. Section 3 proposes and describes the power adjusting algorithm (PAA). Section 4 discusses the parameters of the PAA, where we propose an energy model to obtain the desired parameter for PAA in order to minimize the energy consumption. In Section 5, we implement the PAA and perform simulations to analyze and compare the DSR with PAA and DSR without PAA on the power saving performance. Finally, the conclusions are drawn in section 6.
## 2 PROPAGATION MODEL, MOBILITY MODEL, AND NETWORK ASSUMPTIONS

We first introduce the propagation model and mobility model used in this paper, and then some network assumptions and notations are listed which will help us simple the problems and models.

### 2.1 Propagation Model

Here we use free space propagation model to forecast the power level of sender and receiver within line of sight. Let $P_t$ and $P_r$ be the power level when the packet is transmitted at the sender and received at the receiver respectively, then the power level of the receiver, which is d away from the sender, can be given out by the Friis formula [10]:

$$P_r = \frac{P_t G_r G_t \lambda^2}{(4\pi)^2 d^2 L}, \qquad (1)$$

where $\lambda$ is the carrier wavelength, d is the distance between the sender and the receiver, L is the system wastage factor, $G_t$ and $G_r$ are the antenna gains at the sender and receiver respectively. Note that $\lambda, L, G_t$ and $G_r$ are constants in this formula.

As in the free space we let the path loss exponent is 2, and then the power consumed on the transmitter side by sending one unit of data is:

$$P_t = \varepsilon_{11} + \varepsilon_{2}d^{2}, \qquad (2)$$

and the power consumed on the receiver side by receiving one unit of data is

$$P_r = \varepsilon_{12}, \qquad (3)$$

here $\varepsilon_{11}$ is the power to run the transmitter circuitry, $\varepsilon_{12}$ is the power to run the receiver circuitry, and $\varepsilon_2$ is the power for the transmit amplifier to achieve an acceptable SNR (Signal to Noise Ratio).

Then the power consumed by the network to forward one unit of data can be calculated below:

$$P_f = P_t + P_r = \varepsilon_1 + \varepsilon_2 d^2, \qquad (4)$$

where we have denoted $\varepsilon_1 = \varepsilon_{11} + \varepsilon_{12}$.

As the power consumption on computation is less than the energy for radio transmission by order of magnitude, we ignore the power consumption on computation in this paper.

### 2.2 Mobility Model

Many mobility model (e.g. random walk model, pursue mobility model, ant mobility model) [11] are proposed in recent years, we use the random walk model to simplify our simulation here.

In the random walk model, a MH moves from its current location to a new location by randomly choosing a direction and speed in which to travel. The new speed and direction are both chosen from pre-defined ranges, [0, maxspeed] and [0, 2π] respectively.
<figure><img src="image_4.png" /><figcaption>**Fig. 1** Traveling pattern of a MH using the 2-D Random Walk Mobility Model.</figcaption></figure>

Each movement in the random walk model occurs in a constant time interval t, at the end of which a new direction and speed are calculated. If a MH which moves according to this model reaches a simulation boundary, it "bounces" off the simulation border with an angle determined by the incoming direction. The MH then continues along this new path. Figure 1 cited from [11] shows an example of the movement observed from this 2-D model. The MH begins its movement in the center of the 300m × 600m simulation area or position (150, 300). At each point, the MH randomly chooses a direction between 0 and 2 and a speed between 0 and 10 m/s. The MN is allowed to travel for 60 seconds before changing direction and speed.

## 2.3 Network Assumptions

1. There are $N$ mobile hosts uniformly displayed in an area with radius $R$.

2. We adapt the random walk mobility model as our mobile host's mobility model.

3. The optimal transmission radius of the mobile host, which minimized the power consumption in the multi-hop ad hoc network, is characteristic distance [12], denoted as $r_{char}$, where $r_{char} = \sqrt{\frac{\log n+c(n)}{\varepsilon_1}}$.

4. We also make sure that $r_{char}$ and $n$ satisfy $\pi r_{char}^2 \ge \frac{\log n+c(n)}{n}$, this condition will keep network being connected [13].

5. The mobile host's max speed is set to be $v_m$ m/s in the random walk model.

6. The data rate of the flow through the network is $r_f$ packets/s.

7. The length of the message RREQ, RREP, DATA is $L_{RREQ}$, $L_{RREP}$, $L_{DATA}$, respectively.

8. The main cause to the break of route is the mobility of the mobile host, which means that when the receiver move out of the sender's transmission range, a link break
<figure><img src="image_5.png" /><figcaption>**Fig. 2** A route (2, 3, 4, 5, 6) constructed by route discovery.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>**Fig. 3** The changing route (2, 3, 4, 5, 6) caused by the mobility of the mobile hosts.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>**Fig. 4** A new better route (2, 8, 1, 5, 6) found by restarting the route discovery</figcaption></figure>

will happen, and this will cause the route break. We ignore the result of host failure, unreliable channel, and network congestion in this paper.
# 3 THE POWER ADJUSTING ALGORITHM DESIGN

In this section we will describe the power adjusting algorithm (PAA) which can be embedded in the existing routing protocols such as DSR for power conserving, and then some explications are list to illuminate this algorithm step by step.

## 3.1 Description of PAA

Now for a flow with data rate $r_f$ originate from MH $s$ and route to MH $d$, as PAA construct a periodic schedule on packet transmission, we simply let the time of sending every $k$ packets to be one period $T$, where $T = \frac{k}{r_f}$, then after one period of sending $k$ packets, the old route may not be energy efficient due to the mobility of hosts, then the new route need to be found, so route discovery is restarted to find a new route to the destination to instead the old one, Figure 2 has shown a route from MH 2 to MH 6 constructed by route discovery. Then after a period of $T$ this route become less energy efficient as in Figure 3. At last In Figure 4, we need to find a new more energy efficient route (2, 8, 1, 5, 6) by restarting route discovery.

According to the above discussion, we describe the algorithm of PAA as below:

Step 1. The source of this flow will start route discovery to find a route $(n_0n_1...n_l)$ to the destination, where $n_0 = s$, $n_l = d$. In order to save power, we use the characteristic distance $r_{char}$ as the transmission radius of the RREQ, and RREP messages.

Step 2. By analyzing the power level of RREQ and RREP messages received by the host, every host on the route path, will compute out the distance to its adjacent hosts, we denotes the initialed distance between adjacent MHs $n_i$ and $n_j$ on the route path to be $d_{ij}^0$.

Step 3. Every $\frac{1}{r_f}$ seconds, one packet will be transmitted along this route, let us say this is the $t$th ($1 \le t \le k$) packet on the fly, we forward it with the transmission radius of $(d_{ij}^{t-1} + 2\frac{v_m}{r_f})$ from $n_i$ to $n_j$, where $d_{ij}^{t-1}$ is the distance which was estimated when the $(t-1)$th packet passed through the adjacent hosts $n_i$ and $n_j$ on the route path.

Step 4. If there are no more packets, this flow should be canceled from the network.

Step 5. For every period of $T = \frac{k}{r_f}$ seconds, after sending every $k$ packets, we restart the route discovery to find a new route $(n_0n_1...n_l)$ to the destination host, and then go to Step 2 to continue.

## 3.2 Analysis of PAA

In Step 1, the source broadcasts the RREQ messages to find the destination, after receiving the RREQ messages the desination will reply the source by sending a RREP message to construct a route $(n_0n_1...n_l)$ from the source to the destination. By setting the transmission power to $P_t = \varepsilon_1 + \varepsilon_2r_{char}^2$, the transmission radius of RREQ and RREP message will be $r_{char}$. Finally the route $(n_0n_1...n_l)$ from the source to the destination is constructed by route discovery.

In Step 2, every host $i$ on the route path will calculate the distance $d_{ij}^0$ to the downstream host $j$ (except the source) by analyzing the power level of the RREQ or RREP message. In formula (1), the distance $d_{ij}^0$ can be calculated from the transmitted power level $P_t$ and received power level $P_r$. As in Step 1, we set the transmission
radius of RREQ and RREP message to be $r_{char}$, so the Sender's power level will be $P_t = \varepsilon_1 + \varepsilon_2 r_{char}^2$, and $P_r$ can be get from the receiver side locally. Finally the initialed distance $d_{ij}^0$ between the sender $i$ and the receiver $j$ can be calculate as:

$$d_{ij}^0 = \frac{\lambda}{r\pi} \sqrt{\frac{P_t^i G_t G_r}{P_r^j L}}.$$

In Step 3, $k$ data packets can be delivered to the destination within a period of $T = \frac{k}{r_f}$ seconds, and every $\frac{1}{r_f}$ seconds one packet will pass through the route. When the $t$-th packet passes through this route, we can estimate the distance $d_{ij}^t$ between hosts $n_i$ and $n_j$ from the distance $d_{ij}^{t-1}$ which is the distance when the packet $(t-1)$-th packet passes through $(t \ge 1)$, as the max speed the mobile host is $v_m$, so the distance $d_{ij}^t$ satisfies

$$d_{ij}^{t-1} - 2\frac{v_m}{r_f} \le d_{ij}^t \le d_{ij}^{t-1} + 2\frac{v_m}{r_f}, \quad (5)$$

in order to make sure that the packet $t$ can be successfully delivered to the host $n_j$ from host $n_i$, we just let the host $n_i$'s the RF power level cover a transmission distance of $d_{ij}^{t-1} + 2\frac{v_m}{r_f}$. Then after the transmission of packet $t$, we can estimate the distance $d_{ij}^t$ from the transmitted power level $P_t$ and the received power level $P_r$, and this new calculated distance $d_{ij}^t$ can be calculated to estimate the transmission range of the packet $t+1$. According to Equation (1), we can get $d_{ij}^t$ as below:

$$d_{ij}^t = \frac{\lambda}{r\pi} \sqrt{\frac{P_t^t G_t G_r}{P_r^t L}},$$

here $P_t = \varepsilon_1 + \varepsilon_2(d_{ij}^{t-1} + 2\frac{v_m}{r_f})^2$, and $P_r$ is the receiver's power level when the $(t-1)$-th packet passes through the link $(i, j)$.

In Step 4, when the flow has no packet to send, the network needs to cancel this flow.

In Step 5, when the final packet (packet $k$) was delivered along this route, the source will restart route discovery to find new route, which will find a new energy efficient route compared to the current one according to the current position of the mobile host in the network. Finally we will further discuss the parameter setting on $k$ in a period in Section 4.

## 4 PARAMETERS SETTING OF PAA

The length of a period is vital important in this algorithm, that means, if the period is too short, route discovery are restarted to frequently, which will waste more energy on route discovery, but if the length of period is too long, the link state along the route (eg. the route in Figure 3) will become more and more worse as the MH moves around in the network area, this will also waste much energy on delivering the packet along this energy inefficient route. Now we need to find an appropriate length of period for route discovery, that means when the energy wasted on the current route become unacceptable, the restarted route discovery will find a new better route to save as much energy as possible on delivering the packets.
Now before finding the optimal length of the period, we need first analyze the average distance of the MHs displayed in the network, then the energy consumption of the route discovery, and finally the distance variety between adjacent hosts on the route path in the present of MH's mobility.

## 4.1 The average distance of any two MHs

Lemma 1: Two vectors $v_1(r_1, \theta_1), v_2(r_2, \theta_2)$ where $0 \le r_1, r_2 \le R$, $0 \le \theta_1, \theta_2 \le 2\pi$, are uniformly distributed in a circle with radius $R$, the sum of the two vector $v_1, v_2$ is $v$, that means $v = v_1 + v_2$, then the probability of $v$ locating at $(r, \theta)$ (where $0 \le r \le R$, $0 \le \theta \le 2\pi$) is

$$P(r, \theta, R) = \frac{1}{\pi^2 R^2} \left( 2 \arccos \frac{r}{2R} - \frac{r}{R} \sqrt{1 - \left( \frac{r}{2R} \right)^2} \right). \quad (6)$$

*Proof:* In Figure 3, a vector $v(r, \theta)$ is located in a circle with radius $2R$, two small circles with radius $R$ centered at the start point and the end point of the vector $v(r, \theta)$ are drawn in Figure 5. Then the sum of the two vectors $v_1(r_1, \theta_1), v_2(r_2, \theta_2)$ with length $R$ will be $v(r, \theta)$, and all the possibility position of vector $v_1$ should located in the overlapping regions of the two small circles. Then the area of the overlapping regions of the two small circles is

$$A = R^2(\theta - \sin(\theta)) = R^2 \left( 2 \arccos \frac{r}{2R} - \frac{r}{R} \sqrt{1 - \left( \frac{r}{2R} \right)^2} \right). \quad (7)$$

The variable area of the vector $v_1(r_1, \theta_1)$ or $v_2(r_2, \theta_2)$ is $\pi R^2$, so the probability of the sum of two vectors $v$ located at $(r, \theta)$ is

$$P(r, \theta, R) = \frac{A}{\pi R^2 \pi R^2} = \frac{1}{\pi^2 R^2} \left( 2 \arccos \frac{r}{2R} - \frac{r}{R} \sqrt{1 - \left( \frac{r}{2R} \right)^2} \right). \quad (8)$$

Now for any two hosts uniformly displayed in the network with radius $R$, the location of the two host is $v_1(r_1, \theta_1), v_2(r_2, \theta_2)$ respectively, where $0 \le r_1, r_2 \le R$, $0 \le \theta_1, \theta_2 \le 2\pi$. This can be seen from Figure 6, then the average distance $l$ of this two MHs will be

$$E(l) = \int_{0}^{2R} \int_{0}^{2\pi} P(r, \theta, R) r^2 d\theta dr = \frac{128R}{45\pi}. \quad (9)$$

Therefore, for any two hosts which are uniformly located in a network area with radius $R$, their average distance is $\frac{128R}{45\pi}$.

## 4.2 Energy comsumption on route discovery

In a network with $N$ MHs, the energy consumption of route discovery is mainly consumed by broadcasting the RREQ messages and unicasting the RREP messages, this means

$$E_{restart} = E_{RREQ} + E_{RREP}. \quad (10)$$

The source host broadcasting a RREQ message and this message will flood the whole network, so nearly every host will receive a RREQ message and they will rebroadcast the RREQ message to its neighbors. As the transmission range of the broadcasting
<figure><img src="image_8.png" /><figcaption>Fig. 5 Two vectors $v_1(r_1, \theta_1)$, $v_2(r_2, \theta_2)$ and their sum $v(r, \theta)$.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 6 Two vectors $v_1(r_1, \theta_1)$, $v_2(r_2, \theta_2)$ and their sum $v(r, \theta)$.</figcaption></figure>

is $r_{char}$ which is suggested in PAA, then the energy consumption on broadcasting the RREQ message can be calculated approximately as follow

$$E_{RREQ} = NL_{RREQ}(\varepsilon_1 + \varepsilon_2 r_{char}^2). \qquad (11)$$

The destination host will reply a RREP message after received a RREQ message, this RREP message will be unicasted back to the source, all the hosts who relay the RREP message will form a route $(n_0 n_1 \dots n_l)$ from the source to the destination. As the routing protocol selects the route with minimum number of hops to be the final
<figure><img src="image_10.png" /><figcaption>Fig. 7 The movement of two adjacent MHs $n_i$ and $n_j$.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Fig. 8 The movement of MHs $n_j$ from the view of host $n_i$.</figcaption></figure>

route, so the average number of hops of the active route ($n_0n_1...n_l$) will be

$$L = \lceil \frac{E(l)}{r_{char}} \rceil = \lceil \frac{128R}{45\pi r_{char}} \rceil. \qquad (12)$$

Then the energy consumption of unicasting the RREP message can be calculated approximately as follows

$$E_{RREP} = LL_{RREP}(\varepsilon_1 + \varepsilon_2 r_{char}^2) = \lceil \frac{128R}{45\pi r_{char}} \rceil L_{RREP}(\varepsilon_1 + \varepsilon_2 r_{char}^2). \quad (13)$$

Finally the energy consumption of the route discovery is

$$E_{RREP} == (NL_{RREQ} + \lceil \frac{128R}{45\pi r_{char}} \rceil)L_{RREP}(\varepsilon_1 + \varepsilon_2 r_{char}^2). \quad (14)$$

## 4.3 The distance variety between adjacent MHs on the routing path

For any two objects randomly moving in the space, the distance between them will become larger and larger, this phenomenon is called diffusion in physics. Here we will estimate the distance variety of two adjacent MHs on the routing path, and this result will be used to build the energy consumption model of PAA in the next subsection, and then the optimal length of the period can be calculated out from this model.

The average distance of any two adjacent host $n_i$ and $n_j$ along the route path ($n_0n_1...n_l$) when packet $t-1$ and packet $t$ comes are set to be $d_{t-1}$, $d_t$ respectively. We define the distance variety to be $\Delta d = d_t^2 - d_{t-1}^2$. As the routing protocol selects the route with minimum number of hops to be the final route, the preliminary distance between any two adjacent hosts along the route path just after the route discovery restarted is nearly $r_{char}$, we just set $d_0 = r_{char}$ for simple.
As we have assumed the flow rate is $r_f$, so the time between any two continuous packets is $\frac{1}{r_f}$, and the MH's max speed in their random walk mobility model is set to be $v_m$, so the maximum distance that the MHs can move during the interim of two continuous packets is $r_m = \frac{v_m}{r_f}$.

The displacement of the two MHs $n_i$ and $n_j$ during the interim of two packets is denoted as $s_1(r_1, \theta_1)$, $s_2(r_2, \theta_2)$ respectively, where $0 \le s_1, s_2 \le r_m$, $0 \le \theta_1, \theta_2 \le 2\pi$. The movement of the two hosts $n_i$ and $n_j$ can be seen in figure 7, and from the viewpoint of host $n_i$, the movement of host $n_j$ can be seen in figure 8, and in figure 5 (b), the length $O_1O_2$ of is $d_{t-1}$, the length of $O_1M$ is $d_t$. Then we can estimate distance variety $\Delta d$ as follows

$$ \Delta d = d_t^2 - d_{t-1}^2 = \int_0^{2r_m} \int_0^{2\pi} P(s, \theta, r_m)(d_{t-1}^2 + s^2 + 2d_{t-1}s \cos \theta - d_{t-1}^2)s ds d\theta, \quad (15) $$

where $P(s, \theta, r_m)$ is the probability of the final position of the MH $n_j$ located at $s(r, \theta)$ from the viewpoint of MH $n_i$, here $s = -s_1 + s_2$, and

$$ \sqrt{d_{t-1}^2 + s^2 + 2d_{t-1}s \cos \theta} $$

is the length of vector $O_1M$, which is the distance of the two host.

By some mathematical manipulations the equation (15) is reduced to the following equation:

$$ \Delta d = d_t^2 - d_{t-1}^2 = r_m^2. \quad (16) $$

The above equation means that the distance variety of two adjacent MHs $n_i$ and $n_j$ is square of the maximum distance that the MH can move during the interval of two consecutive packets.

## 4.4 Finding the optimal length of the period

In a period $T$, we let that $k$ packets can be transmitted along the route, then the problem of finding optimal period $T$ is transferred to find optimal number of packets can be transmitted in a period. Note the data rate $r_f$ of the flow is assumed to be constant here.

After the route discovery, a route path $(n_0n_1...n_l)$ from the source to the destination is constructed. As in Step 3 of PAA, the energy of delivering the $t$-th packet on this route path can be calculated in terms of

$$ E(t) = \sum_{t=1}^{l} L_{DATA}(\varepsilon_1 + \varepsilon_2 d_t^2) = LL_{DATA}(\varepsilon_1 + \varepsilon_2 d_t^2). \quad (17) $$

Then the energy of delivering $k$ packet in a period on an active route $(n_0n_1...n_l)$ should be

$$ E_p = \sum_{t=1}^{k} E(t) = LL_{DATA}(k\varepsilon_1 + \varepsilon_2 \sum_{t=1}^{k} d_t^2). \quad (18) $$
Now we need to minimize the average energy consumption on delivering one packet in a period, so this problem can be modeled as follow

$$ \text{Minimize} \quad \frac{1}{k}(E_p + E_{\text{restart}}) \qquad (19) $$

$$ \text{Subjected to} \quad d_0 = r_{\text{char}} \qquad (20) $$

$$ d_1 = d_0 + 2v_m \qquad (21) $$

$$ d_t^2 = d_{t-1}^2 + v_m^2, \quad 2 \le t \le k, \qquad (22) $$

where $E_{\text{restart}}$ is the energy cost on route discovery, equation (19) means that we need to minimize the average energy consumption on delivering one packet. The conditions (21) is derived from step 3 of PAA, and (22) is derived from equation (16).

Now by substituting the conditions (22) into the object function (19) we will get the function below

$$ E(k) = \frac{LL_{DATA}\varepsilon_2 r_m^2}{2}k + \frac{1}{k}\left(\frac{LL_{DATA}\varepsilon_2 r_m^2}{2} + E_{\text{restart}}\right) + LL_{DATA}(\varepsilon_1 + \varepsilon_2(d_0 + 2v_m)^2 - \frac{3}{2}\varepsilon_2 r_m^2) \qquad (23) $$

In order to get the optimal length of period, we need to minimize the energy consumption (23), to make the energy on delivering packet in the period minimized. So we can obtain the first order derivative of function (21) and then get the optimal number of packets delivering in a period

$$ k_{\text{opt}} = \sqrt{1 + \frac{2E_{\text{restart}}}{LL_{DATA}\varepsilon_2 r_m^2}}, \qquad (24) $$

when the parameters are determined, combining with equations (10),(11),(12),(14), we can get the optimal number of packet, then the length of the period in this network to restart the route discovery schedule will be $T = \frac{k_{\text{opt}}}{r_f}$.

## 5 SIMULATION RESULTS

In this section, we have implemented the routing protocol DSR embedded with PAA and DSR without PAA. The parameter setting of these simulations is listed in Table I. In the simulation, 100 flows are randomly selected in a mobile ad-hoc network, and every flow needs to deliver 1000 packets through the network. First we verify the optimal number of packets can be sent in a period, then we compare the number of route discovery, the average energy consumption on delivering one packet, and the total energy consumption between the routing protocol DSR with PAA and DSR without PAA by changing the MH's maximum speed in the random walk mobility model. These results shows that the algorithm of PAA balances the energy consumed on route discovery and data delivering, this enable the routing protocol DSR with PAA conserve energy in the present of mobility.

In Figure 9, as the number of packets k changes from 1 to 200, the average energy consumption on delivering one packet is plotted in this figure, here the max speed of the mobile host is set to be 10m/s. From this picture, we get that, when the number of packet k is in the range of [20, 60], more energy will be conserved on packet delivering.
<figure><img src="image_12.png" /><figcaption>Fig. 9 Verification of the optimal length of period.</figcaption></figure>

<table><caption>**Table 1** The parameters in the simulation</caption><thead><tr><td>Parameter</td><td>Value</td></tr></thead><tbody><tr><td>N</td><td>1000</td></tr><tr><td>R</td><td>1000m</td></tr><tr><td>ε<sub>1</sub></td><td>180,000pJ/bit/m<sup>2</sup></td></tr><tr><td>ε<sub>2</sub></td><td>10pJ/bit/m<sup>2</sup></td></tr><tr><td>L<sub>RREQ</sub></td><td>16byte</td></tr><tr><td>L<sub>RREP</sub></td><td>16byte</td></tr><tr><td>L<sub>DATA</sub></td><td>512byte</td></tr><tr><td>r<sub>f</sub></td><td>1packet/s</td></tr></tbody></table>

The optimal value that computed from our model is 57, so the value computed from the model, will be acceptable in the algorithm of PAA.

By increasing the maximum speed of MHs from 1 m/s to 20 m/s in the mobility model, the number of restarted route discovery per flow, and the average energy consumption on delivering one packet are plotted in Figure 10, and Figure 11 respectively. In figure 6, the number of route discovery restarted is increased greatly in DSR without PAA compared to DSR with PAA. That's because the increasing max speed will enlarge the possibility of link break caused by MH's mobility along the route path in DSR without PAA, whereas this figure increases slowly in the DSR with PAA, that's because the number of route discovery restarted is largely decreased by adjusting the transmission power dynamically to adopt to the mobility of MHs.

Figure 7 demonstrates the route energy state on delivering packets. In this figure, the route energy state of DSR without PAA is always stable at $1.25 \times 10^10pJ$, while
<figure><img src="image_13.png" /><figcaption>Fig. 10 The number of route discovery per flow on delivering 1000 packets.</figcaption></figure>

the route energy state of DSR with PAA increase as the MH's max speed increase. So the route energy state of DSR without PAA is maintained in good state, and the route energy state of DSR with PAA is becoming worse as the max speed increasing. As it has shown in figure 6, the good route state was maintained by DSR without PAA at the cost of much larger number of restarting route discovery, while PAA is aimed to reach a global balance not only in energy consumption on restarting route discovery but also on maintaining route energy consumption state on packet delivering. Clearly less number of route discovery leads to more energy consumption on packet delivering, here the number of route discovery should be select carefully in PAA to minimize the total energy consumption.

The simulation result about the total energy consumption of the two protocols is plotted in figure 8. From the figure, you can see that 40protocol DSR with PAA when the max speed is becoming high. In the present of mobility of mobile host, the protocol DSR without PAA always restart the route discovery when a link break happens, it is suffering the mobility of MHs. While in the protocol DSR with PAA, the mobility of mobile host was under the control of PAA, and further more with the appropriate setting of the length of restarted period, the route discovery is restart to adjust the route path, which always balance the energy consumed on route discovery and packet delivering to reach a global power saving effect. Simulation results demonstrate that 40% energy was saved by using PAA to control the mobility of mobile host.
<figure><img src="image_14.png" /><figcaption>Fig. 11 Average consumption on delivering one packet</figcaption></figure>

## 6 CONCLUSIONS

In this paper, we have proposed a power adjusting algorithm (PAA) which can be embedded in the routing protocol (e.g. DSR, AODV) to save power in the network layer. The algorithm of PAA introduced the adjustable transmission power control to control the mobility of MHs. By properly setting the length of period to restart the route discovery, PAA has the capability of balancing the energy consumption on route discovery and packets delivering to save power in network layer. By simulations, we first verified the optimal length of period calculated from our model, and then by analyzing the number of restarted route discovery and the route energy state, we also verified that PAA has indeed balanced the energy consumption on route discovery and packets delivering. Simulation results shows that the routing protocol DSR with PAA saves nearly 40% energy consumption under high speed mobility.

## References

1. S. Corson, and J. Macker, "Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations," *IETF RFC2501*, Jan, 1999.

2. C. Wang, C. Wu, and G. Chen, "p-MANET: Efficient Power Saving Protocol for Multi-Hop Mobile Ad Hoc Networks," in *Proceedings of Third International Conference on Information Technology and Applications (ICITA'05)*, Washington, USA, 2005, vol. 2, pp. 271-276

3. R. Zheng, and R. Kravets, "On-demand Power Management for Ad Hoc Networks," in *Proceedings Of IEEE INFOCOM*, April. 2003, vol. 1, pp. 481-491

4. S. Wu, Y. Tseng, and J. Sheu, "Intelligent Medium Access for Mobile ad hoc networks with busy tones and power control," *IEEE journal on Selected Areas in Communications*, vol. 18, no. 9, pp. 1647-1657, September. 2000
<figure><img src="image_15.png" /><figcaption>Fig. 12 The total energy consumption on delivering 1000 packets</figcaption></figure>

5. J. Gomez, and A. Campbell, "A case for variable-range transmission power control in wireless ad hoc network," in *Proceeding Of IEEE INFOCOM*, March 2004, vol. 2, pp 1425-1436

6. J. Monks, V. Bharghavan, and W. Hwu, "A Power Controlled Multiple Access Protocol for Wireless Packet Networks," in *Proc. Of IEEE INFOCOM*, Anchorage, USA, April. 2001, vol. 1, pp 219-228

7. M. Zawodniok M, and S. Jagannathan, "A Distributed Transmission Power Control Protocol for Mobile Ad Hoc Networks," in *Proc. of the IEEE WCNC*, 2004, pp. 1915-1920

8. D. B. Johnson and D. A. Maltz, "Dynamic source routing in ad hoc wireless networks," in *Mobile Computing*, pp. 153-181, 1996

9. Charles Perkins, "Ad-hoc On Demand Distance Vector (AODV) routing," *intenet-Draft*, November 1997

10. T. Rappaport, "Wireless Communications: Principles and Practice," Prentice Hall, New Jersey. 1996.

11. T. Camp, J. Boleng, and V. Davies, "A survey of mobility models for ad hoc network research," In *Proceeding of Wireless Communications and Mobile Computing (WCMC'02)*, 2002, vol. 2, no. 5, pp. 483-502.

12. M. Bhardwaj, T. Garnett, and A. Chandrakasan, "Upper bounds on the lifetime of sensor networks," in *Proceedings of IEEE International Conference on Communications*, Helsinki, Finland, June 2001, vol. 3, pp. 785-790.

13. P. Gupta and P. Kumar, "Critical Power for Asymptotic Connectivity in Wireless Networks," in *Stochastic Analysis, Control, Optimization and Applications*, Boston, 1998, pp. 547-566.

14. Charles E.Perkins and Elizabeth M.Royer, "Ad-hoc On-Demand Distance Vector Routing", in *Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications*, New Orleans, LA, February 1999, pp. 90-100