CSI6900 Supervisor Information Form Assignment help
Topics covered:
Project requires student to learn existing neighbor discovery schemes in Wireless sensor and ad hoc networks, perform literature review of recent articles, and Simulate two or more solutions, and compare them.
Problem:
Find efficient methods of performing adjacent neighbor discovery in static ad hoc networks, such as sensor networks. A message sent by one node A is received by all nodes located inside a circle with center A and radius R, where R is transmission radius (unit disk graph model). Nodes are placed at random in an area, and are initially not aware of nodes in the neighborhood. If node A sends its ID message, and node B receives message from only A (no collision), B recognizes the edge AB. Node that sends message is not able to recognize collision (that is, the signal from its own transceiver is so strong that receiver of transmitting node cannot hear or even recognize the existence of any (other signal). Time is divided into slots, and it is assumed that sensors are synchronized in time.
We will consider a variant of the problem where initialization begins in the same slot by all sensors (that is, time to begin neighbor discovery is set in advance to all sensors to the same slot).
Existing solutions:
There exist few papers on the problem, but only one has good results, and will be used in this project. [MB] M.J. McGlynn, S.A. Borbash, Birthday protocols for low energy deployment and flexible neighbor discovery in ad hoc wireless networks, Proc. MobiHoc, Long Beach, CA, October 2001.
Paper [MB] considers different starting slots by each sensor, and methods for saving energy during neighbor discovery process over longer time. These components will not be part of this project. They propose some variants of birthday protocols. We will consider only variant with all sensors being active, that is, in transmitting or receiving mode in each time slot. Their algorithm overestimated the average number of neighbors N of each sensor by a number N’, fixed and equal to all sensors, and then applies simple scheme. Each sensor chooses a random number, and with probability 1/N’ transmits the message, so with probability (N’-1)/N’ does not transmit the message. K= number of sensors placed in a square area of size MxM. N= average node degree, can be estimated as (K-1)*(area of circle with radius R)/(area of square MxM). Choose K= 100, 200, 500, 1000 Choose N’= 2,3,4,5,6,7,8,9,10, 15, 20, 30, 40, 50, 60, 70, 80, 90, 99, 150, 199, 300, 400, 499, 600, 700, 800, 900, 999 (N’<K). Node placement = each node chooses at random x and y coordinates in interval (0,M)= random unit disk graph. Alternative algorithm to apply for the same problem, and for comparison: [SSMN] David Simplot-Ryl, Ivan Stojmenovic, Aleksandar Micic, Amiya Nayak, A hybrid randomized protocol for RFID tag identification, Sensor Review, 26(2), 2006, 147-15. (on www.site.uottawa.ca/~ivan). The algorithm to apply from [SSMN] is the one where nodes transmit with probability 1/N, but where N is not fixed. It depends on the status on channel for each node.
The algorithm [SSMN] is designed for single-hop networks (complete graph, each node can hear all other nodes). The way N is modified in [SSMN] after each round shall be applied (basically doubling N if collision detected by non-transmitting node, reducing in half if silence detected by non-transmitting node, reducing by 1 if node transmitted in given round, no change if non-transmitting node hears only one neighbor and discovers than an edge). Thus each node has its own value for N in each round, while in [SSMN] N’ is fixed and equal to all nodes. Try to modify this update scheme if better algorithm is obtained from experimental results, that is, to add third scheme. May be the change scheme for N is not best possible.
What to measure: Number of rounds needed by both algorithms before T% of edges are discovered. Take T=10%, 20%, 30%, 40%, 50%, 60%, 70%, 80%, 90%, 99%. Each edge AB needs to be discovered twice: by A and by B. Only the first discovery of each particular edge is to be counted. Second and other repeated discoveries of same edge are not taken into account.
