Localized Broadcasting In Wireless Ad-Hoc Networks With Trust Detection

Localized Broadcasting In Wireless Ad-Hoc Networks With Trust Detection

Geethu Chandran 1, Jenopaul. P 2

Department of Electronics and Communication

P.S.N College of Engineering and Technology Tirunelveli, India

AbstractBroadcasting, one of the fundamaental operations of the wireless ad-hoc networks, can be implemented using two approaches ie static and dynamic.In broadcasting a node disseminates a message to all other nodes within the network.Usually in static approach the forwarding or non-forwarding status of the node is determined by a globally known priority function and local topology information.The static approach can achieve a constant approximation factor to optimal solution only if position information is available which is not possible in all cases.This paper shows that constant approximation to optimal solution can be obtained using connectivity information only.The status of each node is determined on-the-fly ie while the broadcasting process is being done.This local broadcast algorithm can achieve both full delivery and constant approximation to the optimal solution.The security issues can be solved by comparing the expected and perceived packet delivery ratios.

Keywords Mobile ad hoc networks, distributed algorithms, broadcasting, connected dominating set, constant approximation

1. INTRODUCTION

   Wireless 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 an 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 ne ighbors 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,

   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 subgraph 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. 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

   Figure2:Construction of connected dominating set G 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.

2. 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.

3. MODEL OF THE NETWORK

   We assume that the network consists of a set of nodes V,V= N. Each node is equipped with omnidirectional 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.

4. 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 seects 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 self-pruning 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.

5. 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 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 self-pruning condition called the coverage condition. To evaluate the coverage

   receive it, finally. Every time u receives a copy of message m it updates Listcov u (m) as already been explained. If w = u (i.e., u is selected by v to forward the message), node u updates Listcov (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 Listcov u (m) as it needs to select one of its neighbors from the updated list (if it is not empty) to forward the message.

   u

   u

   Definition1 (coverage condition). We say the coverage condition for node u is satisfied at time t if Listcov u (m) = at time t.

   u

   u

   Algorithm 1 shows our proposed hybrid broadcast algorithm. When a node u receives a message m, it creates a list Listcov (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).

   Algorithm 1. The proposed hybrid algorithm executed by u

   u

   u

   condition, every node u maintains a list Listcov

   (m)

   1: Extract the ids of the broadcasting node and the

   for every unique message m. Upon receiving a selected

   u

   u

   message m for the first time, Listcov

   (m) is created

   node from the received message m

   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,

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

   4: Return

   5: end if

   u

   u

   6: if u is receiving m for the first time then

   it is at a maximum of 2 hops away from u. Having

   7: Create and fill the list Listcov

   (m)

   ids of v and w (included in the message), node u updates Listcov u (m) by removing all nodes in

   8: end if

   u

   u

   9: Update the list Listcov (m)

   Listcov 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

   10: Remove the information the previous node had added to

   message

   11: if Listcov u (m) ; then

   12: Select an id from Listcov u (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 {(_Listcov u (m) ; in this case*)} 15: if u was selected then

   16: Schedule the message 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

   The proposed algorithm obeys the following statements:

   1. u discards a received message m if it has broadcast

      m before.

   2. If u is selected to forward the message, it schedules a broadcast (regardless of the coverage condition) and never removes the messages from the queue in future. However, u may change or remove the selected nodes id from the scheduled message every time it receives a new copy of the message and updates Listcov u (m).

   3. Suppose u has not been selected to forward the message by time t and the Listcov 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).

   4. If Listcov u (m) then u selects a node from Listcov u (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 Listcov u (m)

   = it does not select any node to forward the

   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 broadcastin nodes inside any disk DO,R/2 centered at an arbitrary point O and with a radius R/2 is at most 32.

   Proof. All nodes inside DO,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 wi DO,3R/2, 1 i k, we have

   message. This is the only case where a broadcasting node does not select any of its neighbors to forward the message.

   i, j i : wiwj R

   ————–(1)

6. 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.

Following, we find an upper bound on k. By the minimality of k, there must exist k – 1 nodes wi DO,3R/2, 1 i k -1, such that

i, j i : wiwj R —————–(2)

Consider k -1 disks D1; . . .;Dk-1 with radius R/ 2 centered at wi, 1 i k – 1, respectively. By (2), D1,,Dk-1 are non overlapping disks. Also, every disk Di, 1 i k – 1, resides in DO,2R that is the disk centered at O with radius 2R.It is because, the center of every Disk Di, 1 i k – 1, is inside DO,3R/2. Thus, by an area argument, we get

(k-1)((R/2)2) (2R)2 —————(3)

Hence, k 17.

ui

ui

We first prove that the number of broadcasting nodes inside DO,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 DO,R/2 for which the coverage condition is satisfied. Consequently, the total number of broadcasting nodes inside DO;R/2 is bounded by 2k -2 32. By contradiction, suppose that there are more than k _ 1 broadcasting nodes inside DO;R2 for which the coverage condition is not satisfied. Consider the first k broadcasting nodes be u1, . . . , uk ordered chronologically based on their broadcast time, and a1, . . . , ak the corresponding selected neighbor. Thus, for every i, 1 i k, we have ai Listcov ui(m), where Listcov (m) is the list of node ui at the time it broadcasts the message. Since u1, . . . , uk are all in DO,R/2 and for every i, 1

i k, uiai R, we get

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.

SAlg 224 × SMCDS. ———–(5)

SMCDS. 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 SMCDS, because SMCDS is a dominating set.

i,1 i k : ai DO,3R / 2

————–(4)

VII.IMPLEMENTING STRONG COVERAGE CONDITION

uj

uj

uj j

uj j

Thus, by the definition of k, there are two nodes ai, aj,i < j such that aiaj R. The node ui is broadcast before uj and is a neighbor of it.Hence, uj is aware of uis selected neighbor ai and removes aj from Listcov (m) as soon as it receives the message from ui. This is a contradiction because aj Listcov (m) at the time u broadcasts.

It remains to prove that the number of broadcasting nodes inside DO,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 satisfied. Let v1, . . . , vk DO,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 , b , . . . ,b be

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 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:

u u

u u

Suppose, for each unique message m, every node u maintains and updates an extra list Liststru (m). Similar to Listcov (m), Liststr (m) is created and

1 2 k

the nodes that selected v1, . . . , vk to forward the message. Therefore, for every i, 1 i k, we have bi DO,3R/2. Also, for every i,1 i k and every j, 1 j k and j i, we get bi bj, 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 bibj R. This is a contradiction because bi and bj are

bj

bj

neighbors and bj receives the bj broadcast message, thus vj Listcov (m) as vi and vj 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 SMCDS be a MCDS and SAlg be the set of broadcasting nodes using Algorithm 1. Let u be any node in Proof. All the nodes within the

filled with the ids of us neighbors upon the first

reception of message m. Also, every time u receives m, it updates Liststru (m) as follows: Let v be the broadcasting node and w u the selected node by v. Node u first removes the nodes in Liststru

(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 Liststru (m) that are neighbors of w. To further reduce the number of redundant

Figure 3:Packet delivery ratio versus time

g

Figure5:A broadcasting instance from the proposed system

that used in the proof of Lemma 2, it can be proven that this extension of the algorithm also achieves a constant approximation factor.

Theorem 7. Suppose Alg-str is a modified version of Algorithm 1 in which each node maintains two

u

u

lists Listcov

(m) and Liststru

(m) and selected nodes

Figure4:PDRs of existing and modified systems

transmissions, a selected node can abort broadcasting m under the following strong coverage condition.

Definition 2 (strong coverage condition). It can be said that the strong coverage condition is satisfied for node u at time t ifListstru (m) = at time t.

Note that the strong coverage condition is only used by selected nodes to check whether they need to broadcast. Other nodes make a decision based on the previously defined coverage condition (a weaker condition). The following theorem stats that the full delivery is guaranteed coverage condition is satisfied. Using a similar approach to

can avoid broadcasting under the strong coverage condition. Full delivery can be guaranteed using Alg-str.

VIII. EXPERIMENTAL RESULTS

Figure 6:Comparison of throughput

Figure7:Packet drop versus time

Figure 8:Comparison of packet drop versus time

Figure 9:Throughput versus time

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 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.

In this system a 1150 x 800 m2 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

The figure illustrates a broadcasting instance from the proposed systemThe 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.

VIII. CONCLUSIONS

In this paper, the capabilities of local broadcast algorithms in reducing the total number of transmissions that are required to achieve full deliverywas 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.

REFERENCES

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

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

2. Wang Lin-zhu; Fan Ya-qin; Yang Yang; Shan Min ,Heuristic Algorithm Based On Flooding Structure InWireless Ad Hoc Networks,IEEE International Conference on Information Engineering, pp.243-246,2010

3. Al Amin, M.T.; Barua, S.; Vhaduri, S.; Rahman, A Load Aware Broadcast in Mobile Ad Hoc Networks,IEEE International Conference on Communications,pp:1-5,2009

4. Khabbazian,M.; Bhargava, V.K., Reducing Broadcast

   Redundancyin Wireless Ad HocNetworks,

   GLOBECOM,pp:769-774,2007

5. Zhong-Yi Liu; Jin-Guo Zhou; Tong Zhao; Wei Yan An Opportunistic Approach to Enhance the Geographical Source Routing Protocol for VehicularAd Hoc Networks,IEEE Vehicular Technology Conference,pp:1-5,2009

6. Revathi, S.; Rangaswamy, T. R Efficient route discovery using stable connected Dominating Set for mobile ad hoc networks, IEEE World Congress on Information and Communication Technologies(WICT),pp:763- 767,2012

7. Kheyrihassankandi, J.; Singh, Y.P.; Chin Kuan Ho A distributed algorithm for constructing minimum connected dominating set in mobile wireless network,IEEE International Conference on Computer and Communication(ICCCE), pp:396-401,2012

8. Shenyong Gao; Ying Zhang , An improved distributed approximation algorithm for minimum connected dominating set,IEEE International Conference on Natural Computation,pp:1019- 1022,2012

9. Guodong Wang; Gang Wang ,An Energy- Aware Geographic Routing Algorithm for Mobile Ad Hoc NetworkIEEE International Conference on Wireless Communication, Networking and Mobile Computing, pp:1-4, 2009