(4) (25%) In order to transmit a message to a receiver, the sender consumes energy Enx(d)...

 

Transcribed Image Text:

(4) (25%) In order to transmit a message to a receiver, the sender consumes energy Enx(d) = c d J/bit, where d is the Euclidean distance between the sender and the receiver, c is a constant, and a is a constant between 2 and 4 depending on the wireless environment. Assume that the energy consumption at the receiver is ignored. Given three nodes A, B, C placed at the vertexes of a triangle in a two-dimensional plane, A has two choices to send messages to C: one is that A sends messages directly to C, the other is that A sends messages to B and B relays the messages to C. Assume that di is the distance between A and B, d2 is the distance between B and C, d3 is the distance between A and C, and ZBAC =0. (4.1). Prove that the first choice consumes more energy than the second choice under the following conditions: (a) di d* cos(0), if a=2 (b) Xa -1> (1+X² -2X*cos(0))a2 where X = d3/d₁, if 2<a< 4. (Note that the above fact is used as a criterion in energy efficient routing protocol design) * [15% for CSC 569] (4.2). Consider the following simple greedy algorithm that tries to find a minimal energy route from a source node to a destination node: a node always selects the nearest node as its next hop until the destination node is reached. To avoid loop, a node that has already been included in the path will not be considered again. When a node has several neighboring nodes with the same smallest distance, the node randomly selects one nearest neighbor to break the tie. As shown in the following figure, node S wants to send messages to node D that is on the circle centered at S with radius 1+e (e is an arbitrarily small positive value). Assume that there are other five nodes falling either within the circle or on the circle. Assume that a-2 and c=1. Prove that the above greedy algorithm may find a path from S to D with the total energy cost of 6 J/bit, which manifests the ineffectiveness of the algorithm. 1+ɛ (4) (25%) In order to transmit a message to a receiver, the sender consumes energy Enx(d) = c d J/bit, where d is the Euclidean distance between the sender and the receiver, c is a constant, and a is a constant between 2 and 4 depending on the wireless environment. Assume that the energy consumption at the receiver is ignored. Given three nodes A, B, C placed at the vertexes of a triangle in a two-dimensional plane, A has two choices to send messages to C: one is that A sends messages directly to C, the other is that A sends messages to B and B relays the messages to C. Assume that di is the distance between A and B, d2 is the distance between B and C, d3 is the distance between A and C, and ZBAC =0. (4.1). Prove that the first choice consumes more energy than the second choice under the following conditions: (a) di d* cos(0), if a=2 (b) Xa -1> (1+X² -2X*cos(0))a2 where X = d3/d₁, if 2<a< 4. (Note that the above fact is used as a criterion in energy efficient routing protocol design) * [15% for CSC 569] (4.2). Consider the following simple greedy algorithm that tries to find a minimal energy route from a source node to a destination node: a node always selects the nearest node as its next hop until the destination node is reached. To avoid loop, a node that has already been included in the path will not be considered again. When a node has several neighboring nodes with the same smallest distance, the node randomly selects one nearest neighbor to break the tie. As shown in the following figure, node S wants to send messages to node D that is on the circle centered at S with radius 1+e (e is an arbitrarily small positive value). Assume that there are other five nodes falling either within the circle or on the circle. Assume that a-2 and c=1. Prove that the above greedy algorithm may find a path from S to D with the total energy cost of 6 J/bit, which manifests the ineffectiveness of the algorithm. 1+ɛ

Answer rating: 100% (QA)

41 a Proof Given End cd Jbit where d is the Euclidean distance between the sender and the receiver c is a constant and a is a constant between 2 and 4 depending on the wireless environment Assume di d... View the full answer