Consider a wireless network where n2 = 81 nodes are located on a rectangular gri
ID: 3670953 • Letter: C
Question
Consider a wireless network where n2 = 81 nodes are located on a rectangular grid as depicted in Fig. 1. Assume time is divided into slots, and at each time-slot a node can either transmit or receive information (but not both). Moreover, at each time slot, a node can successfully transmit one bit of information (using a directional antenna) to one of its distance-1 neighbors. A transmission from a node u to a node v is successful if and only if, no other of the neighbors of v transmit information to it during the same time slot; otherwise, if at least two of the neighbors of v try to transmit simultaneously to v, all transmissions towards v fail because of interference.
(a) A schedule of M time slots defines which nodes are going to transmit during each of the M time slots. Find a schedule so that after M time slots (where M is a parameter you want to minimize) each node has exchanged one bit with each one of its neighbors. What is the value of M?
(b) Suppose that source S at the middle of the network would like to send a bit x1 to all nodes in the network as fast as possible. Clearly, to be fast, we want spatial reuse, i.e., at each time slot to have as many as possible of the nodes who have received the bit x1, transmit this information to one of their neighbors. What is the minimum number of time-slots you would need to achieve this task, and how does your scheme work?
Figure 1: Rectangular grid with 81 nodesExplanation / Answer
1.
The solution to this problem can be given by edge coloring. The chromatic number is 4. We divide edges into four set for each color. Bits can be transferred/received simultanously over same color set. As each edge will be use twice for transferring and then receiving so 4 * 2 = 8 time slots are required.
2.
Answer is 10. Number rows from top to bottom (1-9) and number columns from left to right (1-9). In first time slot S which is at (5, 5) transmits bit to (4, 5). In next time slot it transmits bit to (6, 5). In next i.e. third time slot bit at (4,5) and (6, 5) is simultanously transferred to (3, 5) and (7, 5) respectively. At the end of 5th time slot each node in 5th column will have x1 bit.In 6th time slot all the nodes in 5th column will transfer to 4th column. In 7th time slot all the nodes in 5th column will transfer to 6th column. Now in 8th time slot 4th column nodes will transfer bit to 3rd column and 6th column bits will transfer to 7th column. Similar operation will occur for next two columns.