International Journal of Scientific & Engineering Research, Volume 3, Issue 11, November-2012 1

ISSN 2229-5518

M a x i m i zi n g T h e N u m b e r Of B ro a d c a s t Op e r a t i o n s

I n R a n d o m G e o m e t ri c A d h o c Wi rel e s s N e tw or k s

1P.Abdul Wahid 2Avadhanula Karthik 3 Ch. Srinath Reddy

1, 2(M Tech(Software Engineering) Dept.of Computer Science & Technology,(Student) Sreenidhi Institute of Science & Technology/An Autonomous Institution,Hyderabad,AP, India)

3(Assistant Professor in Sreenidhi Institute of Science & Technology/An Autonomous Institu-

tion,Hyderabad,AP, India)

Abstract

We consider static ad hoc wireless networks whose nodes, equipped with the same initial battery charge, may dynamically change their transmission range. When a node v transmits with range r (v), its battery charge is de- creased by , where > 0 is a fixed constant. The goal is to provide a range assignment schedule that maximizes the number of broadcast operations from a given source (this number is denoted by the length of the schedule). This maximization problem, denoted by MAX LIFETIME, is known to be NP-hard and the best al- gorithm yields worst-case approximation ratio Θ(log n), where n is the number of nodes of the network. We consider random geometric instances formed by selecting n points independently and uniformly at random from a square of side length √n in the Euclidean plane. We present an efficient algorithm that constructs a range as- signment schedule having length not smaller than 1/12 of the optimum with high probability. Then we design an efficient distributed version of the above algorithm, where nodes initially know n and their own position only. The resulting schedule guarantees the same approximation ratio achieved by the centralized version, thus, ob- taining the first distributed algorithm having provably good performance for this problem.

IndexTerms: -Energy aware systems, wireless communication, graph algorithms,network problems

1.1 INTRODUCTION

—————————— ——————————

In static ad hoc wireless networks, nodes have the ability to vary their transmission ranges (and thus, their energy consumption) in order to provide good network connectivity and low energy consumption at the same time. This paper proposes the static ad- hoc wireless networks in which nodes have the abil- ity to vary their transmission ranges (and thus, their
energy consumption) in order to provide good net-
work connectivity and low energy consumption at the same time. When a node v transmits with range, its battery charge is decreased. In this project the node with the maximum energy which is capable of transferring the messages is selected as pivot node among the given nodes in a network. The goal is to provide a range assignment schedule that maximizes
the number of broadcast operations from a given

IJSER © 2012

http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 3, Issue 11, November-2012 2

ISSN 2229-5518

source (this number is denoted by the length of the schedule). This maximization problem, denoted by MAX LIFETIME, is known to be NP-hard and the best algorithm yields worst-case approximation ratio with the total number of nodes of the network.
In networks, Server will select random node to broadcast the message to the receiver. By selecting random node server will send the message to the cli- ent. All nodes should have some initial battery charge. If the node receive or send any messages then it will lose some energy.

LIMITATIONS:

When the message is transmitted, the node will become incapable for sending further messages through the same node.

The servers LIFE PERIOD will be reduced.

In this paper, we provided efficient solutions for the MAX LIFETIME problem. Initially server will get all the nodes energy details by giving the energy request to the node. Server will select max energy node by comparing all the nodes energy. The server selects the
max energy node as PIVOT node and uses it as the
scenarios, where nodes are equipped with batteries of limited charge: the goal here is to maximize the num- ber of broadcast operations. Indeed, in a network where each device has its own battery, minimizing only the overall power consumption can cause early power drains in few key nodes, hence, disconnecting the network. This important range assignment problem has been first analytically is studied and it is the sub- ject of our paper.Time is divided into (time) periods. Period t is devoted to broadcast the tth message from the source s. All nodes are initially equipped with the same battery charge B > 0.
A range assignment schedule S is a sequence of range assignment and the length m of a range assignment schedule is the number of periods. At every period t, the battery charge of each node v is reduced by amount βrt(v)2, where rt(v) denotes the range assigned to node v during t and β > 0 is a fixed constant de- pending on the adopted technology. So, a range as- signment schedule is said to be feasible if, at any peri- od t, rt yields a broadcast tree from s, and for any
v ЄV , it holds that

2

node for transferring the information. The Server then

∑ (V)

<=B

selects the Max charge Node from the remaining nodes for transferring further information.Good Per- formances of the Network without break in the infor- mation transfer.We can achieve MAX LIFETIME of network by selecting the nodes randomly for message transfer.

1.2 THE MAX LIFETIME PROBLEM

The MIN ENERGY BROADCAST problem does not consider some important ad hoc wireless network
In this paper, we assume that β=1; however, all our results can be easily extended to any β> 0. The MAX LIFETIME problem requires to find a feasible range assignment schedule of maximal length.MAX LIFE- TIME is shown to be NP-hard. In the same paper, by means of a rather involved reduction to MIN ENER- GY BROADCAST with nonuniform node efficiency,a polynomial-time algorithm is provided, yielding ap- proximation ratio Θ(log n). This positive result also

IJSER © 2012

http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 3, Issue 11, November-2012 3

ISSN 2229-5518

holds when the initial node battery charges are not uniform. the broadcast tree is fixed during the entire schedule and the quality of solutions returned by the MST-based algorithm is investigated. Such results and techniques are not useful for solving MAX LIFETIME problem, as the broadcast tree may change at each pe- riod.

1.3 OUR RESULTS

To the best of our knowledge, previous analytical re- sults on MAX LIFETIME concern worst-case instanc- es only. Some experimental studies on MIN ENERGY BROADCAST have been done on random geometric instances.Such input distributions turn out to be very important in the study of range assignment problems. On one hand, they represent the most natural random instance family, where greedy heuristics have a bad behavior. On the other hand, random geometric distri- butions provide a good model for well-spread net- works located on two-dimensional regions.
We study MAX LIFETIME in random geometric in- stances of arbitrary size: the set V is formed by n nodes selected uniformly and independently at random from the twodimensional square of side length(√n). Such instances will be simply denoted by random sets. Note that the maximal euclidean distance between two nodes in random sets is √2n so the maximal range val- ue rk can be assumed to be atmost √2n.
A natural and important open question is to establish
whether efficiently constructible range assignment schedules exist for MAX LIFETIME having provably good length on random sets. Moreover, the design of
efficient distributed
implementations of such schedules is of particular rel- evance in ad hoc wireless networks.
To this aim, as a first step, we provide an upper bound on the length of an optimal range assignment schedule S for any finite set V in the two-dimensional plane. Note that this upper bound holds for any in- stance, not only for random sets. When V is a random set, we present an efficient centralized algorithm that, with high probability, returns a feasible schedule of length which is not smaller than 1/12 of the optimum. Here and in the sequel, the term with high probability means that the event holds with probability at least

1-1/nc for some constant c > 0.

We then exploit our algorithm in order to design a ful- ly distributed protocol for MAX LIFETIME. The pro- tocol acts in discrete time slots and assumes that every node initially knows n, its unique label in [1,.. n] (our results remain valid even if labels are chosen in [1,. .
.;N], where N Є O(n), and its euclidean position.
This assumption is reasonable in static ad hoc wireless networks since the node position can be either stored in the node during the deployment phase or it can be locally computed using a GPS system in a setup phase. This operation is not too expensive in terms of energy consumption since it is performed only once during the setup phase.We then show that the resulting schedule is equivalent to the one yielded by the cen- tralized version, and hence, when applied to random sets, it achieves, with high probability, constant ap- proximation ratio as well. We thus get the first distrib- uted algorithm for MAX LIFETIME having provably
good performance.

IJSER © 2012

http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 3, Issue 11, November-2012 4

ISSN 2229-5518

We remark that in the analysis of our protocol, we consider both the costs due to the construction of the range assignment schedule and that due to its use for the broadcast operations. Furthermore, our protocol is designed to take care about message collisions yielded by the interference problems, thus, no cost is hidden in the analysis.
The MAX LIFETIME problem does not consider the goal of minimizing the completion time of the broad- cast operations,i.e., the number of time slots required to get all the nodes informed (a node is said to be in- formed if it has received the source message). Howev- er, the completion time is clearly an important meas- ure to evaluate the efficiency of a solution. We thus provide an analysis of the amortized completion time of each broadcast operation yielded by our protocol. If the length of the range assignment schedule generated by the protocol is T, then the amortized completion time is given by the overall number of elapsed time slots divided by T. It turns out that our protocol has amortized completion time.

O(r2 + r 2 + )

2

2. PRELIMINARIES

A random set V is formed by n nodes selected uni- formly and independently at random from the square Q of side length √n. The source node s can be any node in V . The length of a maximum feasible range assignment schedule (in short, schedule) for an input (V,s) is denoted by opt(V,s).
Given a set V of n nodes in the two-dimensional eu- clidean plane and a positive real r, the disk graph G(V,r) is the symmetric graph where edge (u,v) exists iff dist(v,w)<= r.When V is a random set, the resulting disk graph distribution is known as geometric random graphs. It is known that for sufficiently large n, a ran- dom geometric graph G(V,r) is connected with high probability if and only if r>=µ√logn , where µ=1+Є for any constant Є > 0.The value CT(n)= µ√logn is known as the connectivity threshold of random geo- metric graphs.
Note that the connectivity threshold grows when the area of the square grows as a consequence of the assumption of having a fixed node density for squares of any size. A more realistic assumption would be to consider node ranges as fixed. As a consequence, higher node densities would be required in order to maintain the network connected with high probability while the area of the square grows. In this paper, we adopt the former approach to simplify calculations; nevertheless, our results can be easily translated to suit the latter approach—by means of a unit conversion— and thus, handle networks of growing sizes where nodes have fixed ranges.

Assumptions on range set Ґ. We recall that Ґ=

{0,r1,r2,….rk} is such that 0<r1<r2,….<rk<=√2n.In ad- dition we assume that,1< r1< CT(n) This condition is motivated by our choice of studying random sets. In- deed, define Cs as the connected component contain- ing s in the disk graph G(V, r1). If r1>= CT(n), then MAX LIFETIME on random sets admits a trivial
schedule which is, with high probability, optimal:

IJSER © 2012

http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 3, Issue 11, November-2012 5

ISSN 2229-5518

Since the source must transmit in every period with range at least r1 and Cs, with high probability, contains all nodes, then an optimal schedule is obtained by as- signing range r1 to all other nodes at every period. This motivates our assumption on r1.

3. ALGORITHM USED

In this paper we present a simple and efficient Broadcast Schedule Algorithm for MAX LIFETIME and then analyze its performance. The algorithm partitions Q in- to square cells and selects, for every period, a set of pivots, i.e., nodes having assigned range r2. Each set of pivots is responsible for spreading the message of its period. This message is delivered to one of the pivots from the source by means of transmissions with range r1, thus, exploiting the sub graph Cs.
The source message is sent through nodes in Cs to the first pivot, using range r1.When a pivot transmit with range r2, all nodes in its cell and in the neighbor- ing cells receive the message.
In this section, we present a simple and efficient algo- rithm for MAX LIFETIME and then analyze its per- formance. For the sake of simplicity, we restrict our- selves to the case r2>=2√2c√logn.Nevertheless, it is easy to extend all our results to the more general as- sumption.The following algorithm partitions Q into square cells and selects, for every period, a set of piv- ots, i.e., nodes having assigned range r2. Each set of pivots is responsible for spreading the message of its period. This message is delivered to one of the pivots from the source by means of transmissions with range
r1, thus, exploiting the subgraph Cs. Observe that we
here assume every node knows the positions of all the other nodes and the cell partition: the algorithm is thus centralized:See Fig. 1 for an example of execution of Algorithm BS.

Fig1: Execution example for algorithm BS. The source message is sent through nodes in Cs to the first pivot, using range r1. When a pivot transmits with range r2, all nodes in its cell and in the neighboring cells receive the message.

IJSER © 2012

http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 3, Issue 11, November-2012 6

ISSN 2229-5518

Description: Input:


Set V Q of n nodes; a source s Є V ; a battery Charge B > 0; the range set T = {0,r1,r2,……rk} Output:
A range-assignment schedule S.
Partition Q into square cells of side length r2/2 2
for any cell Qj, let Vj be the set of nodes in Qj;
Construct an arbitrary ordering in Vj;

Steps involved:

1. Let Cs be the connected component in G(V,r1)
; that contains s;
2. if |Cs| ≤ r22 then
3. Ws Cs;
4. else
5. Ws any connected subgraph of Cs s.t. |Ws| = r2

2 and

6. s Ws;
7. construct an arbitrary ordering of Ws;
8. for any period t = 1, . . . . . do
9. if node with index t mod |Ws| in Ws has re- maining

10. battery charge at least r2 2

11. then
12. it is selected as pivot and range r2 is assigned to it;
13. else
14. the algorithm stops;
15. for any cell Qj do
16. if node with index t mod |V| in Qj has remain- ing

17. battery charge at least r22 then

18. it is selected as pivot and range r2 is assigned to it;
19. else
20. the algorithm stops;
21. all nodes in Ws not selected yet have radius r1

4. OPEN PROBLEMS

In this paper, we provided efficient solutions for the MAXLIFETIME problem on random sets. Further in- teresting future studies should address other basic op- erations such as the gossiping operation which is known to be NP-hard as well . A more technical prob- lem, left open by our work, is the study of MAX LIFETIME when Ґ contains more than onepositive value smaller than the connectivity threshold CT(n) of random geometric graphs. This case seems to be very hard since it concerns the size and the structure of the connected components of such random graphs under the connectivity threshold.Finally, we emphasize that after the presentation of the conference version of this work, a new protocol for MIN ENERGY BROAD- CAST. This new protocol is inspired by ours and achieves provably good performances on random-grid instances yielded by nonuniform node distributions.

5. CONCLUSION:

This paper proposes the static ad hoc wireless networks in which nodes have the ability to vary their transmission ranges (and thus, their energy consumption) in order to provide good network con- nectivity and low energy consumption at the same

IJSER © 2012

http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 3, Issue 11, November-2012 7

ISSN 2229-5518

time.. In this paper, the node with the maximum en- ergy is selected as pivot node among the given nodes in a network which is capable of transferring the messages to the individual Clients.
This paper provides a range assign- mentschedule that maximizes the number of broad- cast operations from a given source (this number is denoted by the length of the schedule). This maxi- mization problem, denoted by MAX LIFETIME, is known to be NP-hard and the best algorithm, BROADCAST SCHEDULING ALGORITHM yields worst-case approximation ratio with the total number of nodes of the network.

6. FUTURE ENHANCEMENTS:

As a future work, we can include more than one positive Threshold T value smaller than the connectivity threshold CT(n) of the random Geo- metric Graphs in the study of “MAX LIFETIME “.This case seems to be very hard since it concerns the size and the structure of the connected compo- nents of such random graphs under the connectivity threshold.

7. REFERENCES

1. A. Ephremides, G.D. Nguyen, and J.E. Wieselthier, “On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks,” Proc. IEEE INFOCOM, pp. 585-594, 2000.
2. I. Kang and R. Poovendran, “Maximizing Network
Lifetime of Wireless Broadcast Ad Hoc Networks,” J.
ACM Mobile Networks and Applications, vol. 10, no.
6, pp. 879-896, 2005.
3. C. Ambuehl, “An Optimal Bound for the MST Al- gorithm to Compute Energy Efficient Broadcast Trees in Wireless Networks,” Proc. Int’l Colloquium Au- tomata, Languages and Programming (ICALP ’05), pp. 1139-1150, 2005.
4. G. Calinescu, X.Y. Li, O. Frieder, and P.J. Wan, “Minimum-Energy Broadcast Routing in Static Ad Hoc Wireless Networks,” Proc. IEEE INFOCOM, pp.
1162-1171, Apr. 2001.
5. G. Calinescu, S. Kapoor, A. Olshevsky, and A. Zeli- kovsky, “Network Lifetime and Power Assignment in Ad Hoc Wireless Networks,” Proc. European Symp. Algorithms (ESA ’03), pp. 114-126, 2003.
6. G. Calinescu, X.Y. Li, O. Frieder, and P.J. Wan, “Minimum-Energy Broadcast Routing in Static Ad Hoc Wireless Networks,” Proc. IEEE INFOCOM, pp.
1162-1171, Apr. 2001.
7. M. Cardei, J. Wu, and M. Lu, “Improving Network Lifetime Using Sensors with Adjustable Sensing Ranges,” Int’l J. Sensor Networks, vol. 1, nos. 1/2, pp.
41-49, 2006.
8. A. Ephremides, G.D. Nguyen, and J.E. Wieselthier, “On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks,” Proc. IEEE INFOCOM, pp. 585-594, 2000.
9 A.D. Flaxman, A.M. Frieze, and J.C. Vera, “On the Average Case Performance of Some Greedy Approx- imation Algorithms for the Uncapacitated Facility Lo- cation Problem,” Proc. ACM Symp. Theory of Com- puting (STOC ’05), pp. 441-449, 2005.

IJSER © 2012

http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 3, Issue 11, November-2012 8

ISSN 2229-5518

10 M. Flammini, A. Navarra, and S. Perennes, “The Real Approximation Factor of the MST Heuristic for the Minimum Energy Broadcast,” Proc. Int’l Work- shop Experimental and Efficient Algorithms (WEA
’05), pp. 22-31, 2005.
11 P. Gupta and P.R. Kumar, “Critical Power for As-
ymptotic Connectivity in Wireless Networks,” Sto-
chastic Analysis, Control, Optimization and Applica- tions, pp. 547-566, Birkhauser, 1999.
12 I. Kang and R. Poovendran, “Maximizing Network Lifetime of Wireless Broadcast Ad Hoc Networks,” J. ACM Mobile Networks and Applications, vol. 10, no.
6, pp. 879-896, 2005.
13 L.M. Kirousis, E. Kranakis, D. Krizanc, and A. Pelc, “Power Consumption in Packet Radio Net- works,” Theoretical Computer Science, vol. 243, pp.
289-305, 2000.
14 M. Mitzenmacher and E. Upfal, Probability and
Computing.Cambridge Univ. Press, 2005.
15 K. Pahlavan and A. Levesque, Wireless Infor- mation Networks.Wiley-Interscience, 1995.

IJSER © 2012

http://www.ijser.org