# I. INTRODUCTION

ireless ad hoc networks are now being used to support wireless networks that can be established without the help of any fixed infrastructure. Wireless devices in ad hoc networks are usually termed as nodes. One of their important characteristic is their limited transmission ranges. Therefore, each node can directly communicate with only those within its transmission range (i.e., its neighbors) and requires other nodes to act as routers in order to communicate with out-of range destinations. One of the fundamental operations in wireless ad hoc networks is broadcasting, where a node transmits a message to all other where each node on receiving a message transmits nodes in the network. This can be achieved through the traditional where a node on receiving a message sends it to all its neighbors only for once. However, flooding can entail a large number of redundant transmissions, which can lead to significant waste of constrained resources such as bandwidth and power. In general, it is not necessary for every node to forward/transmit the message in order to process of flooding, Author ? ? : Department of Electronics and Communication, P.S.N College of Engineering and Technology. E-mails : geethuc87@gmail.com, jenopaul1@rediffmail.com Figure 1 : A mobile ad-hoc network 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. If the nodes in the DS form a connected sub graph then it is called a Connected Dominating Set (CDS). A CDS is hence formed by a source node along with its forwarding nodes. By using only the nodes in the set to forward the message CDS can be used for broadcasting. 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. from unidirectional graph G (based on both local topology and broadcast state information). In the static approach, the distinctive 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 neighborhood. Hence, local algorithms can provide scalability as the constructed CDS can be efficiently updated. The existing local algorithms in this category use a priority function known by all nodes in order to determine the status of each node. Using only local topology information and a globally known priority function, based on the static approach the local broadcast algorithms cannot guarantee a good approximation factor to the optimum solution (i.e., MCDS). On the other hand, in the dynamic approach, the status of each node (hence the CDS) is determined "on-the-fly" during the broadcast progress. Using the dynamic approach, the constructed CDS may vary from one broadcast instance to another even when the whole network topology and the source node remain unchanged. As a result, the broadcast algorithms based on the dynamic approach typically have small maintenance cost and are expected to be robust against node failures and changes in network topology.


# II. SECURITY IN WIRELESS AD-HOC NETWORKS

The wireless ad-hoc networks are easily prone to attacks from malicious nodes that can result in loss of information. The expected and the perceived packet delivery ratios can be compared and in case of abnormalities we can check for the presence of malicious nodes. If the perceived packet delivery ratio is lesser than the expected ratio then we can assume that the packets are being lost. Selfish nodes are those nodes which do not broadcast the received packets thus leading to the failure of communication. By comparing Fig 3 : Minimum Connected Dominating Set the expected and the perceived PDFs the selfish nodes can be easily detected and isolated. By preventing the selfish nodes from assuming forwarding status, the communication process can be preserved.


# III. MODEL OF THE NETWORK

We assume that the network consists of a set of nodes V,â?"?Vâ?"?= N. 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. We can 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 ? V and v ? 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. 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.

Practically speaking, 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.


# IV. BROADCASTING IN THE DYNAMIC APPROACH

Using the dynamic approach, the status (forwarding/ non forwarding) of each node is determined "on-the-fly" as the broadcasting message propagates in the network. Usually in neighbor-designating broadcast algorithms, each forwarding node selects its own subset of its neighbors to forward the packet and in self-pruning algorithms each node determines its own status based on a self-pruning condition after receiving the first or several copies of the message. It was proved that selfpruning broadcast algorithms are able to guarantee both full delivery and a constant approximation factor to the optimum solution (MCDS). However, the proposed algorithm in uses position information in order to design a strong self-pruning condition. In the last section, it was observed that position information can simplify the problem of reducing the total number of broadcasting nodes. Moreover, acquiring position information may not be possible in some applications. In this section, 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 using only the connectivity information.


# V. THE PROPOSED LOCALIZED BROADCAST ALGORITHM

Suppose each node has a list of its 2-hop neighbors (i.e., nodes that are at most 2 hops away). This can be achieved in two rounds of information
( D D D D D D D D )
Year exchange. In the first round, each node broadcasts its id to its 1-hop neighbors (simply called neighbors). Thus, at the end of the first round, each node has a list of its neighbors. During the second round, each node transmits its id together with the list of its neighbors. The proposed broadcast algorithm is a hybrid algorithm, combining both neighbor designating and self-pruning algorithms and so every node that broadcasts the message may select some of its neighbors to forward the message. In the proposed broadcast algorithm, each broadcasting node selects at most one of its neighbors. A node should broadcast the message if it is selected for forwarding. Other nodes which are not selected have to decide whether or not to broadcast by themselves. This decision is made based on a selfpruning condition called the coverage condition. To evaluate the coverage condition, every node u maintains a list List cov u (m) for every unique message m. Upon receiving a message m for the first time, List cov u (m) is created and filled with the ids of all neighbors of u and then updated as follows: Suppose u receives m from its neighbor v and assume that v selects w ? u to forward the message. Note that w may not be a neighbor of u. However, since w is a neighbor of v, it is at a maximum of 2 hops away from u. Having id's of v and w (included in the message), node u updates List cov u (m) by removing all nodes in List cov u (m) that are a neighbor of either v or w. This update can be done because u has a list of its 2-hop neighbors. Since w will eventually broadcast the message, by updating the list, u removes those neighbors that have received the message or will receive it, finally. Every time u receives a copy of message m it updates List cov u (m) as already been explained. If w = u (i.e., u is selected by v to forward the message), node u updates List cov u (m) by removing only neighbors of v from the list. Note that in this case, u must broadcast the message. However, u has to update List cov u (m) as it needs to select one of its neighbors from the updated list (if it is not empty) to forward the message.

Definition 1 (coverage condition). We say the coverage condition for node u is satisfied at time t if List cov u (m) =? at time t. Algorithm 1 shows our proposed hybrid broadcast algorithm. When a node u receives a message m, it creates a list List cov u (m) if it is not created yet and updates the list as explained earlier. Then, based on whether u was selected to forward or whether the coverage condition is satisfied, u may schedule a broadcast by placing a copy of m in its MAC layer queue. The sources of delay in the MAC layer can be divided into two. Firstly, a message may not be at the head of the queue so it has to wait for other packets to be transmitted. Secondly in contention based channel access mechanisms such as CSMA/CA, to avoid collision, a packet at the head of the queue has to wait for a random amount of time before getting transmitted.

In this paper, we assume that a packet can be removed from the MAC layer queue if it is no longer required to be transmitted. Therefore, the broadcast algorithm has access to two functions to manipulate the MAC layer queue. Among the two functions, the first function is the scheduling/placing function, which is used to place a message in the MAC layer queue. We assume that the scheduling function handles duplicate packets, i.e., it does not place the packet in the queue if a copy of it is already in the queue. The second function is used to remove a packet from the queue (it does not do anything if the packet is not in the queue). and never removes the messages from the queue in future. However, u may change or remove the selected node's id from the scheduled message every time it receives a new copy of the message and updates List cov u (m). 3. Suppose u has not been selected to forward the message by time t and the List cov u (m) becomes empty at time t after an update. Then at time t, it removes the message from the MAC layer queue (if the message has been scheduled before and is still in the queue). (m) ?? to forward the message and adds the id of the selected node in the message. The selection can be done randomly or based on a criteria. For example, u can select the node with the minimum id or the one with maximum battery life-time. 5. If u has been selected to forward and List cov u (m) = ? it does not select any node to forward the message. This is the only case where a broadcasting node does not select any of its neighbors to forward the message.


# VI. Analysis of the Proposed Broadcast Algorithm

In this section, it can be proved that the proposed broadcast algorithm guarantees full delivery as well as a constant approximation to the optimum solution irrespective of the forwarding node selection criteria and the random delay in the MAC layer. In order to prove these properties, assume that nodes are static during the broadcast that the network is connected and there is no loss at the MAC/PHY layer. Note that even flooding cannot guarantee full delivery without these assumptions.

Theorem 5 : Algorithm 1 guarantees full delivery Proof :

Every node broadcasts a message at most once. Therefore, the broadcast process eventually terminates. By contradiction, assume that node d has not received the message by the broadcast termination. Since the network is connected, there is a path from the source nodes (the node that initiates the broadcast) to node d. Clearly, we can find two nodes u and v on this path such that u and v are neighbors, u has received the message and v has not received it. The node u did not broadcast the message since v has not received it. Therefore, u has not been selected to broadcast; thus, the coverage condition must have been satisfied for u. As the result, v must have a neighbor w, which has broadcast the message or was selected to broadcast. Note that all the selected nodes will ultimately broadcast the message. This is a contradiction because, based on the assumption, v should not have a broadcasting neighbor.


# Lemma 2:

Using Algorithm 1, the number of broadcasting nodes inside any disk D O,R/2 centered at an arbitrary point O and with a radius R/2 is at most 32.


# Proof:

All nodes inside D O,R/2 are neighbors of each other, thus they receive each others messages. The broadcasting nodes can be divided into two types based on whether or not the coverage condition was satisfied for them just before they broadcast the message. Recall that the coverage condition may be satisfied for a broadcasting node if the node has been selected to forward the message. It is because a selected node has to broadcast the message irrespective of the coverage condition. Consider two disks centered at O with radii R/2 and 3R/2, respectively. Suppose k is the minimum number such that for every set of k nodes w i ? D O,3R/2 , 1 ? i ? k, we have
R wiwj i j i ? ? ? : ,
Following, we find an upper bound on k. By the minimality of k, there must exist k -1 nodes w
i ? D O,3R/2 , 1 ? i ? k -1, such that R wiwj i j i > ? ? : , Consider k -1 disks D 1 ; . . .;D k-1 with radius R/ 2 centered at wi, 1 ? i ? k -1, respectively. By (2), D 1 ,?,D k-1 are non overlapping disks. Also, every disk D i , 1 ? i ? k -1, resides in D O , 2R that is the disk centered at O with radius 2R.It is because, the center of every Disk D i , 1 ?i ? k -1, is inside D O,3R/2
. Thus, by an area argument, we get
(k-1)(?(R/2) 2 ) ? ?(2R) 2

# Hence, k ? 17

We first prove that the number of broadcasting nodes inside D O,R/2 for which the coverage condition is not satisfied is at most k -1. We then prove the same upper bound for the number of broadcasting nodes inside D O,R/2 for which the coverage condition is satisfied. Consequently, the total number of broadcasting nodes inside D O;R/2 is bounded by 2k -2 ? 32. By contradiction, suppose that there are more than k _ 1 broadcasting nodes inside D O;R2 for which the coverage condition is not satisfied. Consider the first k broadcasting nodes be u 1 , . . . , u k ordered chronologically based on their broadcast time, and a 1 , . . . , a k the corresponding selected neighbor. Thus, for every i, 1 ? i ? k, we have a i ? List cov ui (m), where List cov ui (m) is the list of node ui at the time it broadcasts the message. Since u 1 , . . . , u k are all in D O,R/2 and for every i, 1 ? i ? k, â?"?u i a i â?"?? R, we get
2 / 3 , : 1 , R O i D a k i i ? ? ? ?
Thus, by the definition of k, there are two nodes a i , a j ,i < j such that â?"?a i a j â?"? ? R. The node u i is broadcast before u j and is a neighbor of it.Hence, u j is aware of u i 's selected neighbor a i and removes a j from List cov uj (m) as soon as it receives the message from u i . This is a contradiction because a j ? List cov uj (m) at the time u j broadcasts.

It remains to prove that the number of broadcasting nodes inside D O,R/2 for which the coverage condition is satisfied is at most k _ 1. By contradiction, suppose that there are at least k broadcasting nodes inside DO;R2 for which the coverage condition is . . ,b k be the nodes that selected v 1 , . . . , v k to forward the message. Therefore, for every i, 1 ? i ? k, we have b i ? D O,3R/2 . Also, for every i,1 ? i ? k and every j, 1? j ? k and j ? i, we get b i ? b j , because each node can select a maximum of one other node to forward. By the definition of k, there must exist two nodes bi and bj, i < j such thatâ?"? b i bjâ?"? ? R. This is a contradiction because b i and b j are neighbors and b j receives the b j broadcast message, thus v j List cov bj (m) as v i and v j are neighbors.

Corollary 1 :

Let u be any node in the network. Using the proposed Algorithm, the number of broadcasting nodes within the transmission range of u is at most 224.


# Proof :

Let S MCDS be a MCDS and S Alg be the set of broadcasting nodes using Algorithm 1. Let u be any node in Proof. All the nodes within the transmission range of u (including u) are inside a disk with radius R. A disk with radius R can be covered with at most seven disks with radius R/2 . Thus, by Lemma 2, the number of broadcasting nodes within the transmission range of u is at most 7 × 32 = 224.


# Theorem 6 :

Algorithm 1 has a constant approximation factor to the optimal solution (MCDS). Moreover, the approximation factor is at most 224.
â?"?S Alg â?"?? 224 × â?"?S MCDS(5)
S MCDS . By Corollary 1, the number of broadcasting nodes within the transmission range of u is at most 224. Note that every broadcasting node is within the transmission range of at least one node in S MCDS , because S MCDS is a dominating set.


# VII.


# Implementing Strong Coverage Condition

As proven, the proposed broadcast algorithm guarantees that the total number of transmissions is always within a constant factor of the minimum number of required ones. However, the number of transmissions may be further reduced by slightly modifying the broadcast algorithm. As explained earlier, in the Suppose, for each unique message m, every node u maintains and updates an extra list List str u (m). Similar to List cov u (m), List str u (m) is created and filled with the ids of u's neighbors upon the first reception of message m. Also, every time u receives m, it updates List str u (m) as follows: Let v be the broadcasting node and w ? u the selected node by v. Node u first removes the nodes in List str u (m) that are neighbors of v. If the priority of w (e.g., its id) is higher than u, it also removes the nodes in List str u (m) that are neighbors of w. To further reduce the number of redundant transmissions,  It can be said that the strong coverage condition is satisfied for node u at time t ifList str u (m) =? at time t. Note that the strong coverage condition is only used by selected nodes to check whether they need to proposed algorithm, a selected node has to broadcast the message even if its coverage condition is satisfied. Nevertheless, in some cases, a selected node can avoid broadcasting. For example, a selected node u can abort transmission (by removing the message from the queue) at time t if by time t and based on its collected information, all its neighbors have received the message. This idea can be implemented as follows:

broadcast. Other nodes make a decision based on the previously defined coverage condition (a weaker condition). The following theorem states that the full delivery is guaranteed coverage condition is satisfied. Using a similar approach to g that used in the proof of a selected node can abort broadcasting m under the following strong coverage condition.

Lemma 2, It can be proven that this extension of the algorithm also achieves a constant approximation factor.    This paper is aimed on implementing a secured broadcasting algorithm based on the dynamic approach. The existing system uses connectivity information to broadcast a message by forming a connected dominating set. But the disadvantage with the existing system is that it does not guarantee a secure means of broadcasting. The presence of selfish nodes in the network can disrupt smooth communication between the nodes. In this paper the Figure 7 : Packet drop versus time existing algorithm is modified so as to identify the selfish Fig: 3 A broadcast instance from the proposed system. nodes in the network and they are prevented from being a part of the connected dominating set.In this way, we can prevent the disruption of communication in the network.


# Experimental Results

In this system a 1150 x 800 m 2 sized rectangular network with 40 mobile nodes is used for carrying out the simulation purpose. Two ray ground propagation with a wireless channel is set up. A priority queue model is set up with a maximum queue size of 300 packets. Each node is assumed to have an initial energy of 100 joules which decreases with each transmission and reception of packets. Each node is equipped with an omnidirectional antenna. The simulation of the proposed system is done using NS-2.35 network simulator.


# Global Journal of Computer Science and Technology

Volume XIII Issue VIII Version I 


# Year

The figure illustrates a broadcasting instance from the proposed system. The source is broadcasting a message using the nodes in the connected dominating set namely, the nodes 8,9,10 and 38.The selfish nodes in the network had been identified as 2,13,15,26,31 and 35.These nodes are prevented from forming a part of the connected dominating set after their identification so as to improve the quality of communication.

In figure, the packet delivery ratio of the proposed system is shown. The x-axis shows the time, while the y-axis shows the packet delivery ratio. It can be shown from the figure that the packet delivery ratio increases linearly and attains a constant value at around 4000 unit of time. Around 1000 packets are delivered in a unit of time after the graph attains the constant value. The linearly increasing portion of the graph indicates the time taken for the formation of the connected dominating set. After the formation of the connected dominating set, the packet delivery ratio remains constant. Figure shows the comparison of the packet delivery ratio of the existing and proposed systems. In the existing system, the packet delivery ratio drops at certain instants due to the inclusion of selfish nodes in the network which is prevented in the proposed system.

The throughput of the proposed system is graphically shown in the figure. The time is plotted in the x-axis while throughput is plotted in the y-axis. The graph increases linearly for most of the parts but at certain points it increases rapidly. The graph attains a maximum value of 10,00,000. The figure shows the comparison for throughput of the two systems. In the existing system also, the graph follows the same pattern as that of the modified system but the maximum attained value is only 40,000.

The comparison of the packet drop values also show that the modified system is far more advantageous than the existing system. From the graph, it can be shown that the packet drop is almost negligible for the modified system throughout the broadcasting process. The graph is plotted with time on x-axis while packet drop on the y-axis. The comparison of the two systems show that the packet drop values increase and decrease alternatively in the existing systems.The packet drop reaches the zero value only at some instants.At some instants, it reaches the maximum value of upto 62,000 packets which adversely affects the broadcasting process.


# IX.


# Conclusions

In this paper, the capabilities of local broadcast algorithms in reducing the total number of transmissions that are required to achieve full delivery was investigated. As proven, local broadcast algorithms based on the static approach cannot guarantee a small sized CDS if the position information is not available. It was shown that having relative position information can greatly simplify the problem of reducing the total number of selected nodes using the static approach. In fact, it can be shown that a constant approximation factor is achievable using position information. But by using the dynamic approach, it was shown that a constant approximation is possible using (approximate) position information. This paper shows that local broadcast algorithms that are based on the dynamic approach do not require position information to guarantee a constant approximation factor.
2![Figure 2 : Construction of connected dominating set G'](image-2.png "EFigure 2 :")
14![The proposed hybrid algorithm executed by u Global Journal of Computer Science and Technology Volume XIII Issue VIII Version I If List cov u (m) ?? then u selects a node from List cov u](image-3.png "Algorithm 1 :E 4 .")
![v 1 , . . . , v k ? D O,R2 be the first k broadcasting nodes, arranged chronologically based on their broadcast time. Note that a broadcasting node must have been selected (by another node) to forward the message if its coverage condition is fulfilled. Let b 1 , b 2 , .](image-4.png "")
3![Figure 3 : Packet delivery ratio versus time](image-5.png "Figure 3 :")
4![Figure 4 : PDRs of existing and modified systems Definition 2 (strong coverage condition).It can be said that the strong coverage condition is satisfied for node u at time t ifList str u (m) =? at time t. Note that the strong coverage condition is only used by selected nodes to check whether they need to proposed algorithm, a selected node has to broadcast the message even if its coverage condition is satisfied. Nevertheless, in some cases, a selected node can avoid broadcasting. For example, a selected node u can abort transmission (by removing the message from the queue) at time t if by time t and based on its collected information, all its neighbors have received the message. This idea can be implemented as follows:](image-6.png "Figure 4 :")
![Journal of Computer Science and TechnologyVolume XIII Issue VIII Version I](image-7.png "Global")
5![Figure 5 : A broadcasting instance from the proposed system](image-8.png "Figure 5 :")
6![Figure 6 : Comparison of Throughput](image-9.png "Figure 6 :")
89![Figure 8 : Comparison of packet drop versus time](image-10.png "Figure 8 :Figure 9 :")
			© 2013 Global Journals Inc. (US)
		
		
			

				


* 
	
		Computers and Intractability: A Guide to the Theory of NP-Completeness
		
			MGarey
		
		
			DJohnson
		
		
			1990
			W.H. Freeman & Co
		
	




* 
	
		Unit Disk Graphs
		
			BClark
		
		
			CColbourn
		
		
			DJohnson
		
	
	
		Discrete Math
		
			86
			
			1990
		
	




* 
	
		
		
			WangLin-Zhu
		
		
	




* 
	
		
	
	
		Fan Ya-qin
		
	




* 
	
		
		
			YangYang
		
		
	




* 
	
		Heuristic Algorithm Based On Flooding Structure In Wireless Ad-Hoc Networks
		
			ShanMin
		
	
	
		IEEE International Conference on Information Engineering
				
			2010
			
		
	




* 
	
		A Load Aware Broadcast in Mobile Ad Hoc Networks
		
			AlAmin
		
		
			MTBarua
		
		
			SVhaduri
		
		
			SRahman
		
	
	
		IEEE International Conference on Communications
				
			2009
			
		
	




* 
	
		Reducing Broadcast Redundancyin Wireless Ad Hoc Networks
		
			MKhabbazian
		
		
			VKBhargava
		
	
	
		GLOBECOM
				
			2007
			
		
	




* 
	
		
		
			Zhong-YiLiu
		
		
	




* 
	
		
		
			Jin-GuoZhou
		
		
	




* 
	
		
		
			TongZhao
		
		
	




* 
	
		An Opportunistic Approach to Enhance the Geographical Source Routing Protocol for Vehicular Ad Hoc Networks
		
			WeiYan
		
	
	
		IEEE Vehicular Technology Conference
				
			2009
			
		
	




* 
	
		Efficient route discovery using stable connected Dominating Set for mobile ad hoc networks
		
			SRevathi
		
		
			TRangaswamy
		
	
	
		IEEE World Congress on Information and Communication Technologies (WICT)
				
			2012
			
		
	




* 
	
		A distributed algorithm for constructing minimum connected dominating set in mobile wireless network
		
			JKheyrihassankandi
		
		
			YPSingh
		
		
			Chin Kuan
		
		
			Ho
		
	
	
		IEEE International Conference on Computer and Communication (ICCCE)
				
			2012
			
		
	




* 
	
		
		
			ShenyongGao
		
		
	




* 
	
		An improved distributed approximation algorithm for minimum connected dominating set
		
			YingZhang
		
	
	
		IEEE International Conference on Natural Computation
				
			2012
			
		
	




* 
	
		An Energy-Aware Geographic Routing Algorithm for Mobile Ad Hoc Network
		
			GuodongWang
		
		
			; GangWang
		
	
	
		IEEE International Conference on Wireless Communication, Networking and Mobile Computing
				
			2009