Continuous Neighbor DISCOV ERY Algorithm for Wireless Network

Continuous Neighbor DISCOV ERY Algorithm for Wireless Network

Continuous Neighbor DISCOV ERY Algorithm for Wireless Network

*A.Mehamooda Begum #P.D.Chidhambara Rao, Asst. Prof. KTM College of Engineering KTM College of Engineering

Keywords: Synchronization, Neighbor discovery algorithm, nodes, sensor network.

1. INTRODUCTION

   The nodes have an equal and constant transmission range and bidirectional communication. Most of the nodes discover each other and enter the continuous neighbor discovery state before the simulation begins.

   There are two states

   1. Init state

   2. Normal state.

   In the Init state, node is active for a long time and it has no information about its surroundings. It searches for its neighbors and changing the state from init to normal state. Mostly Sensor Networks are static

   and the node connection changes dynamically. In large areas, network has a mesh structure. Some of them act as routers, which forward the messages from one to other nodes. The communication hardware is in turn on and off state to minimize the energy consumption.

   Fig.1. Transmission of

   HELLO messages in Init and Normal states When two neighboring nodes are in active they will communicate each other.

   In the connected segment, hidden nodes are detected within a certain probability P and a certain time period T with reduced expended on the detection. In a continuous neighbor discovery algorithm that determines the frequency with which every node enters the HELLO period. The simplest estimation algorithm is good enough for hidden nodes in the segment.

   Graph having Gmax, and Gmin. All possible paths are find within the graph Gmax. Finding the routes in two stages.

   Topology Formation

   Packet Routing

   Directional antennas are used to detect the neighbor nodes in static wireless network. At each time slot, sensors either transmits or receives HELLO messages in a random direction from other nodes and determine the pattern of transmission directions.

   Neighbor discovery algorithm classified into two groups,

   1. Direct-Discovery Algorithm

   2. Gossip Based Discovery algorithm.

   Deriving analytical bounds for the decay probability for the gossip-based algorithm and helps in determine parameters. When the nodes dynamically adjusting their beam widths. So the beam width varying algorithms maximize the number of neighbors discovered.

   Direct-Discovery Algorithms: A node must receive at least one successful transmission from its neighbor in order for it to discover that neighbor. When a node successfully receives from a neighbor, it records the Angle-Of-Arrival (AOA) information along with the identity of the neighbor or record the neighbor information. The AOA or location information of the neighbors is essential. Once discovering of neighbor is completed. It provide either AOA or location information is imposed by neighbor discovery algorithms.

   The HELLO protocol, inspired by ALOHA. Each node is in listening or talking. The initiation of transmission of HELLO message decide the node randomly. When the HELLO is collide with the messages then it is discovered and determine the HELLO transmission frequency and the duration of the neighbor discovery process.

   The infrastructure is dynamically created and maintained in the wireless communication. To enable communications, hosts cooperate together to provide several complex services. All these high level services usually rely on a neighbor discovery protocol.

   In order to reduce the network congestion and increase the performances, three hello protocols are proposed. In the AODV routing protocol is used to examine the electiveness of hello messages for the monitoring of link status. Several factors influence the utility of hello messages are determined, and a variety of approaches for improving the accuracy of these messages are evaluated. The proposed probabilistic radio propagation model used increase performance. We develop small hello protocols that adapt parameters depending on the configuration of the network.

   The random protocols are used for energy efficiency and robustness that discovery in comparison to deterministic or scheduling algorithms. The time is slotted; the nodes are synchronized in one of the following two states: listening or talking. However, this model as well as the studied protocols does not take into account the energy consumption. A polling based MAC protocol that addresses the problem of neighbor discovery with directional antennas. This protocol uses a polling strategy wherein a node polls its discovered neighbors periodically. This enable the node to adjust its antenna weighting coefficients in order to track its neighbors.

2. IMPLEMENTATION

   1. Detecting All Hidden Links Inside a Segment

      If the new node is discovered in the segment, it sends special SYNC message to all segment members, and asking them to

      wake up and periodically broadcast a bunch of HELLO messages.

      Node u has four hidden links to nodes in. The degree of u in S is degs (u). When u is discovered by one of its four neighbors in S. It allows two neighboring nodes and to discover each other if they belong to a connected segment.

   2. Detecting a Hidden Link Outside a Segment:

      Node wakes up randomly, every T (u) seconds on the average, for a fixed period of time H. During this time, it sends several HELLO messages and listens for possible HELLO messages.

      T(u)=T(1) , if node is in the Init state

      T(u)=T (u) if node is in the Normal state

      By the correlation of random variables and the fact that Var(Z)=Var(Z),

      Corr (Z , Z ) = cov ( Z , Z ) / Var(Z)

      = ( Z Z ) E ( Z ) E ( Z ) .

      E( ZZ ) = cov ( Z , Z ) + E ( Z ) E ( Z )

      = C Var ( Z ) + E ( Z ) E ( Z )

      Substituting into (2)

      MER2

      =E(Z2)+E(Z2)-2(CVar(Z)+E(Z)E(Z))

      =E(Z2)+E(Z2)2CVar(Z) 2 E( Z ) E( Z )

      = 2 E ( Z2 ) 2 E ( Z ) 2 2 C Var ( Z )

      = 2 Var ( Z ) 2 C Var ( Z )

      = ( 2 2 C ) Var ( Z )

      For the third estimation approach for linear prediction problem. degs (v) is estimated as

      Z=CZ+(1-C)f MER3= E ( ( Z – Z ) 2 )

      N

   3. Estimating the In-Segment Degree of A Hidden Neighbor:

      In the continuous neighbor discovery scheme, new node u is divided among all the nodes. Node u is assumed to not yet be connected to the segment, and it is in the Init state. Three methods are presented.

      The MER is defined as E((Z-Z)2). Since u and v are two neighbors in the same graph, Z and Z have the same distribution. Let us denote the correlation between Z and Z, corr(Z,Z) by C. The average graph degree by f. Clearly E(Z)=E(Z)=f .

      MER1 = E( (Z-Z)2)

      = E( (Z f ) 2) = Var(Z) (1)

      we have Z=Z, hence

      MER2 =E( (Z – Z ) 2 )

      = ( y x ) 2 P ( Z = x , Z = y )

      = ( y2 -2xy + x 2 ) P ( Z = x , Z = y)

      =E(Z2) + E(Z2)2E(ZZ) (2)

      = E (( C Z + ( 1 C ) f Z ) 2 )

      MER3 =(C 2+ 1)E(Z2)+( 2C -C2 1 ) f 2 – 2C ( C Var ( Z ) + f 2 2 C ( CVar ( Z ) + f 2)

      = ( C 2 + 1 ) Var ( Z ) 2 C2 Var ( Z )

      = ( 1 C 2) Var ( Z )

      Method	degs(v)	MER
      1	F	Var(Z)
      2	Z	(2-2C)Var(Z)
      3	CZ+(1-C)f	(1-C2)Var(Z)

      The orrelation between the degrees of neighboring nodes and on the variance of node degree. C=corr(Z,Z).

   4. Running New Routing Protocol

      If the routing protocol involves a different packet format. Depending on the packet type, the trace may log additional information. Analyze the trace file and record the packets and compute Number of data packets sent to the host and received

      total number of routing packets and also find time.

      Fig.2 Flow diagram for running MANET protocols in ns-2

3. DESIGNING OF SYSTEM i.Existing System

   Software design is the first of the three

   technical activities design, code generation and test. It focuses all four major areas of concern:

   1. Data Design

   2. Architectural Design

   3. Interface Design

   4. Code Design

   When the node is in Init state referred as initial neighbor and their detection is referred as continuous neighbor discovery in Normal state.

   Limitations:

   In the Init state, a node is in active for long time and no information about its surroundings to detect new neighbors.

   Then establish a path to the gateway and contribute to the operation of the network and maintain it continuously.

   1. Proposed system:

      Finding of the hidden wireless link which uses two message types:

      1.) SYNC messages for synchronization between all segment nodes.

      2.) HELLO messages for detecting new neighbors.

      Continuous neighbor discovery algorithm used to find the frequency with which every node enters the HELLO period.

   2. Procedural Design

      System design either logical or physical design.

      Logical design is followed by physical design. This design consists of following steps:

      Design physical system

      Plan system implementation

      Design is concerned with identifying function, data streams, Specifying relationships among the functions, maintaining a record of design decisions.

   3. Design Issues

      In the design of system abstraction is the first step. The total system is modularized into the following modules.

      Network module

      Channel Access module

      Control Message Access module

      Control Channel Jamming module

      Node Capture Attack Module

   4. Module Description:

      The modules included here are:

      Hidden node deployment

      Topology Creation.

      • Neighbor Discovery Model Hidden Node Deployment:

        It issue a special SYNC message to all segment members and wake up and periodically broadcast a bunch of HELLO messages. All the nodes wake up periodically .almost at the same time. for a short period, every wireless link between the segment's members will be detected.

        A random wake-up approach is used to minimize the possibility of repeating collisions between the HELLO messages of nodes in the same segment. The HELLO transmission time is shorter, the probability that two neighboring nodes will be active at the same time.

        1. Topology Creation

           Server accepts requests for data from client and returns the result to the client. Clients and servers communicate over a computer network on separate hardware.

        2. Neighbor Discovery Model:

        The initiations of transmission of HELLO message decide the node randomly. When the HELLO is collide with the messages then it is discovered and determine the HELLO transmission frequency and the duration of the neighbor discovery process..

   5. An Efficient Continuous Neighbor Discovery Algorithm

   If a hidden node is discovered by one of its segment neighbors after a very short time

   If the node u is in neighbor discovery state:

   It wakes up every TI seconds and avg time period equal to H, and broadcasts HELLO messages.

   The nodes of segment S will discover u within a time period T with probability P. Each node v in the segment S is in topology

   maintenance state, wakes up every TN(v), seconds for a period of time equal to H.

   • In order to discover each other, u and v are in an active period that overlaps by , 0<<1.

   If node u wakes up at time t, node v should wake up between t-H(1- ) and t+H(1- ). The length of valid time interval is 2H(1- ).

   Since the average time interval between two wake-up periods of v is TN(v), during a specific HELLO intervals of u and the probability of discovering u and v nodes each other i.e. 2H(1- )/TN(v).

   Let n be the number of in-segment neighbors of u.

   When u wakes up and sends HELLO messages, neighbors is awake at least once i.e. 1-(1-2H(1- )/TN(v))n.

   Consider a division of the time axis of u into time slots of length H.

   The node u is awake in a given time slot is H/TI, and the time slot is given as

   P1= H/TI(1-(1-2H(1- )/ TN(v))n).

   Denote by D the value of T/H. Then, the node discovered within at most D slots is P2=1-(1- P1)D.

   P2=1-(1- P1)D P ,P1 1-(1-P)1/D H/TI(1-(1-2H(1- )/ TN(v))n) 1-(1-P)1/D

   TN(v)2H(1-)/(1-(1-TI/H(1-(1-P)1/D)()1/n

   We can estimate the value but don't know the exact value.

4. RESULTS

   In a large sensor network, with nodes distributed randomly and uniformly over the area. The nodes have an equal and constant transmission range and bidirectional communication. Most of the nodes discover each other and enter the continuous neighbor discovery state before the simulation begins.

   Fig.3. Simulation model consists of 100 sensor nodes. Hidden node will be detected with P within a T. r chosen to be 300.

   Fig.4. Hidden neighbor detection for the case of uniform distribution.

5. CONCLUSION & FUTURE WORK

   If the sensor nodes are static, continuous neighbor discovery is crucial. If the nodes in a connected segment work together and hidden nodes are guaranteed to be detected within a certain probability and a certain time period, with reduced expended on the detection.

   If every node connected to a segment estimates the in-segment degree of its possible hidden neighbors. Continuous neighbor discovery algorithm that determines the frequency with which every

   node enters the HELLO period. When the hidden nodes are concentrated around some dead areas, the third algorithm is used in the average degree of all the nodes in the segment. In-network aggregation or compression techniques are important strategies in the area of sensor networks to actively reduce the transmit energy consumptions.

6. REFERENCES

1. R. Madan and S. Lall, An energy- optimalalgorithm for neighbor discovery in wireless sensor networks, Mobile Netw. Appl., vol. 11, no.3, pp. 317326, 2006.

2. M. J. McGlynn and S. A. Borbash, Birthday protocols for low energydeployment and flexible neighbor discovery in ad hoc wirelessnetworks, in Proc. 2nd ACMMobiHoc, New York, 2001, pp. 137145.

3. D. Baker and A. Ephremides, The architectural organization of a mobileradio network via a distributed algorithm, IEEE Trans. Commun.,vol. COMM-29, no. 11, pp. 16941701, Nov. 1981.

4. A. Keshavarzian, E. Uysal-Biyikoglu, F. Herrmann, and A. Manjeshwar,Energy- efficient link assessment in wireless sensor networks,in Proc. IEEE INFOCOM, 2004, vol. 3, pp. 17511761.