Improving the Transmissions in Wireless AD HOC Networks Using Local Broadcast Algorithm

Improving the Transmissions in Wireless AD HOC Networks Using Local Broadcast Algorithm

Mohammed Siraj. B1, Dr. S. Rajalakshmi2

1Student, Department of Computer Science and Engineering, Jay Shriram Group of Institutions, Tirupur, India

2Associate Professor, Department of Computer Science and Engineering, Jay Shriram Group of Institutions, India

Abstract

Number of transmission is very high to transmit the data to a receiver in static approach. At the same time number of duplicate data will be occurring. So we use dynamic approach to eliminate the number of transmission in a network. The proposed algorithm uses position information in order to design a strong self-pruning condition. Moreover, having position information may not be practical in some applications. So we design a hybrid (i.e., both neighbor-designating and self-pruning) broadcast algorithm and show that the algorithm can achieve both full delivery and constant approximation only using connectivity information. A set of nodes form a dominating set (DS) if every node in network is either in the set or has a neighbor in the set. A DS is called a connected dominating set (CDS). Here we are finding the minimum CD

1. Introduction

In this project it shown that Local Broadcast algorithm based on the static approaches cannot achieve good approximation factor to the optimum solution when using static approach, local algorithms determine the status of each node proactively based on local topology information and priority function. . However, constant approximation factor is achievable if position information is available. In the dynamic approach, local algorithms determine the status of each node on-the-fly based on local topology information and broadcast state information. Using the dynamic approach, local broadcast algorithms can achieve a constant approximation factor to the optimum solution when position information is available and position information is not available. Here we are selecting the dominant set (DS) for the transaction. Which node has maximum number of ID that will be selected as a dominant set (DS). Scope of the project is enables the fast transmission between nodes. And also reduces the redundancy between the transmissions. In this, we are

using two approaches static and dynamic for what means to broadcast algorithm in wireless network. It determines the status of each node to transmit the data.

One of the fundamental operations in wireless ad hoc networks is broadcasting, where a node disseminates a message to all other nodes in the network. This can be achieved through flooding, in which every node transmits the message after receiving it for the first time. However, flooding can impose a large number of redundant transmissions, which can result in significant waste of constrained resources such as bandwidth and power. In general, not every node is required to forward/transmit the message in order to deliver it to all nodes in the network. A set of nodes form a Dominating Set (DS) if every node in the network is either in the set or has a neighbor in the set. A DS is called a Connected Dominating Set (CDS) if the sub graph induced by its nodes is connected. Clearly, the forwarding nodes, together with the source node, form a CDS. On the other hand, any CDS can be used for broadcasting a message (only nodes in the set are required to forward). Therefore, the problems of finding the minimum number of required transmissions (or forwarding nodes) and finding a Minimum Connected Dominating Set (MCDS) can be reduced to each other. Unfortunately, finding a MCDS (and hence minimum number of forwarding nodes) was proven to be NP hard even when the whole network topology is known. A desired objective of many efficient broadcast algorithms is to reduce the total number of transmissions to preferably within a constant factor of its optimum. For local algorithms and in the absence of global network topology information, this is commonly believed to be very difficult or impossible. The existing local broadcast algorithms can be classified based on whether the forwarding nodes are determined statically (based on only local topology information) or dynamically (based on both local topology and broadcast state information). In the static approach, the distinguishing feature of local

algorithms over other broadcast algorithms is that using local algorithms any local topology changes can affect only the status of those nodes in the vicinity. Therefore, local algorithms can provide scalability as the constructed CDS can be updated, efficiently. The existing local algorithms in this category typically use a priority function known by all nodes in order to determine the status of each node. In this paper we show that, using only local topology information and a globally known priority function, the local broadcast algorithms based on the static approach are not able to guarantee a good approximation factor to the optimum solution (i.e., MCDS). On the other hand, we show that local algorithms based on the static approach can achieve interesting results such as a constant approximation factor and shortest path preservation if the nodes are provided with position information. In the dynamic approach, the status of each node (hence

the CDS) is determined on-the-fly during the broadcast progress. Using this approach, the constructed CDS may vary from one broadcast instance to another even when the whole network topology and the source node remain unchanged. Consequently, the broadcast algorithms based on the dynamic approach typically have small maintenance cost and are expected to be robust against node failures and network topology changes. Many local broadcast algorithms in this category use local neighbor information to reduce the total number of transmissions and to guarantee full delivery (assuming no loss at the MAC/PHY layer). Others, such as probability-based and counter-based algorithms, do not rely on neighbor information. These algorithms typically cannot guarantee full delivery but eliminate the overhead imposed by broadcasting Hello messages or exchanging neighbor information.

Source Destina

tion

Fig 1: Path selection from source to destination

Many of the existing neighbor-information- based broadcast algorithms in this category can be further classified as neighbor-designating and self- pruning algorithms. In neighbor- designating algorithms, each forwarding node selects some of its local neighbors to forward the message. Only the selected nodes are then required to forward the message in the next step. For example, a forwarding node u may select a subset of its 1-hop neighbors such that any 2-hop neighbor of u is a neighbor of at least one of the selected nodes. In self-pruning algorithms, on the other hand, each node decides by itself whether or not to forward a message. The decision is made based on a self-pruning condition. For example, a simple self-pruning condition employed in is whether all neighbors have been covered by previous transmissions. In other words, a node can avoid forwarding/rebroadcasting a message if all of its neighbors have received the message by previous transmissions. In, it was shown that neither neighbor-

designating nor self-pruning algorithms can guarantee both full delivery and a constant approximation if they use only 1-hop neighbor information and do not piggyback information into the broadcast packets. The authors then proposed a self-pruning algorithm based on partial 2-hop neighbor information and proved that the algorithm achieves a constant approximation to the optimum solution and guaranteesfull delivery. However, in their proposed algorithm, each node was assumed to have its (approximate) position information, which is not practical in some applications/scenarios. Also, having position information can provide nontrivial information in wireless ad hoc networks and can greatly simplify the problem. As such, we wish to know whether similar results can be obtained without using position information. In this paper, we answer this remaining question in the positivewe propose a local broadcast algorithm based on 2-hop neighbor information and prove that it guarantees a constant approximation to

the optimum solution. The proposed algorithm is both neighbor-designating and self pruning, i.e., the status of each node is determined by itself and/or other nodes. In particular, using our proposed algorithm, each broadcasting node selects at most one of its neighbors to forward the message. If a node is not selected to forward, it has to decide, on its own, whether or not to forward the message.

1. System Model and Assumptions

   We assume that the network consists of a set of nodes V. Each node is equipped with omni

   directional antennas. Every node u 2 V has a unique id, denoted id(u), and every packet is stamped by the id of its source node and a nonce, a randomly generated number by the source node. For simplicity, we assume that all nodes are located in two- dimensional space. However, all the results presented in this paper can be readily extended to three dimensional ad hoc networks. To model the network, we assume two different nodes u 2 V and v 2 V are connected by an edge if and only if |uv|<= R, where

   |uv| denotes the Euclidean distance between nodes u and v and R is the transmission range of the nodes.

   Fig 2: System Model

   Thus, we can represent the communication graph by GðV ;RÞ, where V is the set of nodes and R is the transmission range. This model is, up to scaling, identical to the unit disk graph model, which is a typical model for two dimensional ad hoc networks. In reality, however, the transmission range can be of arbitrary shape as the wireless signal propagation can be affected by many unpredictable factors. Finally, we assume that the network is connected and static during the broadcast and that there is no loss at the MAC/PHY layer. These assumptions are necessary in order to prove whether or not a broadcast algorithm can guarantee full delivery. Note that without these assumptions even flooding cannot guarantee full delivery.

2. Overview of proposed algorithms

   The proposed algorithm uses position information in order to design a strong self-pruning condition. But in existing, we observed that position information can simplify the problem of reducing the total number of broadcasting nodes. Moreover, having position information may not be practical in some applications. So we design a hybrid (i.e., both neighbor-designating and self-pruning) broadcast algorithm and show that the algorithm can achieve both full delivery and constant approximation only using connectivity information. A set of nodes form a dominating set (DS) if every node in network is either in the set or has a neighbor in the set. A DS is called a connected dominating set (CDS). Here we are finding the minimum CDS.

3. Objective of the Proposed Work

   The main objective of the project is to reduce the number of transmission. Suppose if we are not reducing transmission, we will get redundant data. In this, two approaches are used (static and dynamic) as broadcast algorithm in wireless ad hoc network.

   Local broadcast algorithms determine the status of each node to transmit the data. It is possible if even position information is not available.

4. Proposed algorithm for Transmissions (Hybrid algoritm)

1: Extract ids of the broadcasting node and the selected node from the received message m

2: if u has broadcast the message m before then 3: Discard the message

4: Return

5: end if

6: if u receives m for the first time then 7: Create and fill the list List (m)

8: end if

9: Update the list List (m)

10: Remove the information added to the message by the previous broadcasting node

11: if List(m) = then

12: Select an id from List (m) and add it to the message

13: Schedule the message {(*only update the selected id if m is already in the queue*)}

14: else {(*List (m) = in this case*)} 15: if u was selected then

16: Schedule the message {(*only remove the id of the selected neighbor if m is already in the queue*)}

17: else

18: Remove the message from the queue if u has not been selected by any node before

19: end if

20: end if

3. Conclusion and Future Work

Local broadcast algorithms based on the static approach cannot guarantee a small sized CDS if the position information is not available. I showed that a constant approximation factor is achievable using position information. Using the dynamic approach, the constant approximation is possible using (approximate) position information. In this paper, I showed that local broadcast algorithms based on the dynamic approach do not require position information to guarantee a constant approximation factor.

It avoid the problem in the existing by selecting the dominant set (DS) for the transaction between two nodes. In the proposed the number of transmission is very less so the less number of redundant data occurred. It guarantees full delivery of data using local broadcast algorithm and also a constant approximation to the optimum solution. Algorithm used in which the status of each node is decided on-the-fly.

References

1. M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP- Completeness. W.H. Freeman & Co., 1990.

2. B. Clark, C. Colbourn, and D. Johnson, Unit Disk Graphs,Discrete Math., vol. 86, pp. 165-177, 1990.

3. J. Wu and F. Dai, Broadcasting in Ad Hoc Networks Based onSelf-Pruning, Proc. IEEE INFOCOM, pp. 2240-2250, 2003.

4. J. Wu and W. Lou, Forward-Node-Set- Based Broadcast in Clustered Mobile Ad Hoc Networks, Wireless Comm. and Mobile Computing, vol. 3, no. 2, pp. 155-173, 2003.

5. J. Wu and F. Dai, A Generic Distributed Broadcast Scheme in Ad Hoc Wireless Networks, IEEE Trans. Computers, vol. 53, no. 10, pp. 1343-1354, Oct. 2004.

6. S. Ni, Y. Tseng, Y. Chen, and J. Sheu, The Broadcast Storm Problem in a Mobile Ad Hoc Network, Proc. ACM MobiCom, pp. 151-162, 1999.

7. Z. Haas, J. Halpern, and L. Li, Gossip- Based Ad Hoc Routing,Proc. IEEE INFOCOM, pp. 1707-1716, 2002.

8. D.Y. Sasson and A. Schiper, Probabilistic Broadcast for Flooding in Wireless Mobile Ad Hoc Networks, Proc. IEEE Wireless Comm. and Networking Conf., pp. 1124- 1130, 2003.

9. H. Liu, P. Wan, X. Jia, X. Liu, and F. Yao, Efficient Flooding Scheme Based on 1-Hop Information in Mobile Ad Hoc Networks, Proc. IEEE INFOCOM, 2006.

10. J. Wu, W. Lou, and F. Dai, Extended Multipoint Relays to Determine Connected Dominating Sets in Manets, IEEE Trans. Computers, vol. 55, no. 3, pp. 334-347, Mar. 2006.

11. M. Khabbazian and V.K. Bhargava, Efficient Broadcasting in Mobile Ad Hoc Networks, IEEE Trans. Mobile Computing, vol. 8, no. 2, pp. 231-245, Feb. 2009.

12. W. Peng and X. Lu, On the Reduction of Broadcast Redundancy in Mobile Ad Hoc Networks, Proc. ACM MobiHoc, pp. 129- 130,2000.

13. I. Stojmenovic, M. Seddigh, and J. Zunic, Dominating Sets and Neighbor Elimination- Based Broadcasting Algorithms in Wireless Networks, IEEE Trans. Parallel and Distributed Systems, vol. 13, no. 1, pp. 14-25, Jan. 2002.

14. M. Khabbazian and V.K. Bhargava, Localized Broadcasting with Guaranteed Delivery and Bounded Transmission Redundancy, IEEE Trans. Computers, vol. 57, no. 8, pp. 1072-1086, Aug. 2008.

15. Y. Xu, J. Heidemann, and D. Estrin,Geography-Informed Energy Conservation for Ad Hoc Routing, Proc. ACM MobiCom, 2001.

16. Y. Chen and J.L. Welch, Location-Based Broadcasting for Dense Mobile Ad Hoc Networks, Proc. ACM Intl Symp. Modeling, Analysis and Simulation of Wireless and Mobile Systems, pp. 63- 70,2005.

17. A. Keshavarz-Haddad, V. Ribeiro, and R. Riedi, DRB and DCCB: Efficient and Robust Dynamic Broadcast for Ad Hoc and Sensor Networks, Proc. IEEE Fourth Ann. Comm. Soc. Conf. Sensor, Mesh and Ad Hoc Comm. and Networks (SECON 07), pp. 253- 262, 2007.

18. C.T. Zahn, Black Box Maximization of Circular Coverage, J. Research of the Natl Bureau of Standards B., vol. 66, pp. 181-216, 1962.

19. L. Barrie´re, P. Fraigniaud, and L. Narayanan, Robust Position- Based Routing in Wireless Ad Hoc Networks with Unstable Transmission Ranges, Proc. Fifth Intl Workshop Discrete Algorithms and Methods for Mobile Computing and Comm. pp. 19-27, 2001.

20. Y. Cai, K. Hua, and A. Phillips, Leveraging 1-Hop Neighborhood Knowledge for Efficient Flooding in Wireless Ad Hoc Networks, Proc. IEEE Intl Performance, Computing, and Comm. Conf. (IPCCC 05), pp. 347-354, 2005.

21. P. Wan, K. Alzoubi, and O. Frieder, Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks, Proc.IEEE INFOCOM, vol. 3, pp. 1597-1604, 2002.

3.1 Author Detail

Mohammed Siraj. B received his B.E degree in Information Science and Engineering from Anjuman Engineering College,Karnataka and now studying M.E degree in Computer Science and Engineering at Jay Shriram Group of Institutions.

Dr.S.Rajalakshmi received her B.E degree in Computer Science and Engineering from Mahendra Engineering College in 2003. M.E degree in Computer Science and Engineering from Muthayammal Engineering College in 2007. PhD in Computer Science and Engineering at Anna University Chennai 2012. her Area of Interest is Data Mining, Knowledge Engineering, Artificial Intelligence & Sensor Networks. She has 9 years of Teaching Experience and 5 years in Research.