Assignment 1: GPSR¶
Since |
27.11 |
Till |
19.12 23:59 CET |
Points |
15 |
Write a TinyOS app that sends sensor readings to different motes in a network using GPSR Greedy Perimeter Stateless Routing. The app should run under TOSSIM.
- The app uses 3 components:
- SophisticatedSensor
It provides two split-phase interfaces: one to read sensor reading, one to read address and location of a mote to which this reading should be sent. Since it is a very sophisticated sensor, it is not known how long it takes to acquire this information and if each time these processes succeed. However, the reading and the address are related to each other: the n-th requested reading should be sent to a node with the n-th requested address (counting since boot).
- ReadingsStore
It should be passed readings that other motes send to this mote.
- Location
It provides location of this mote: longitude and latitude on a grid.
Every 5 seconds the app queries SophisticatedSensor for a reading and an address of a recipient. When they are both available, it sends the reading to the recipient. If SophisticatedSensor fails to provide the reading and/or the address, the app disregards available information skipping this round. When the recipient receives the reading, it passes the reading and the address of the sender to its ReadingsStore.
Proper interfaces, components and their exemplary implementations are provided in A1.tgz. Note that an evaluation of your solution may employ different implementations of these components (but satisfying the same interfaces).
- The evaluation of you solution will mainly assess:
packet delivery success rate: how many readings are transmitted successfully to their recipients,
latency: how long it takes for the information to travel from sender’s SophisticatedSenor to recipent’s ReadingsStore,
throughput: both of a single mote and a network as a whole.
Well working solutions implementing only the greedy routing will receive 8 points. Well working solutions implementing the greedy perimeter routing with graph planarization will receive 15 points.
- You can assume that:
only motes with IDs from 0 to 999 can be in a simulated network,
all links between motes are symmetric in terms of their gain,
motes do not move during simulation (i.e. their locations are static).
- You should consider cases in which:
there is a noise present within the network,
links do not have gain resulting directly and only from spatial location of motes,
motes can be turned on and off.
- Submit your solution by sending a <your-login-on-students>.tgz archive by e-mail with topic: “[DS2019] Solution 1”. The archive should contain:
source of your app,
a README file with a brief description of your solution (main ideas, created components, etc.) and optionally additional information concerning building, running and evaluating your solution.
Please do not include any unnecessary files.
Mind that you are allowed to talk about your ideas with your colleagues, but you are not allowed to share your source (any part in any form).
Updates & clarifications¶
Last update: 28.11 08:40
Although the app should query SophisticatedSensor every 5 seconds, the component is not guaranteed to provide information within that time, as well as it does not support canceling running operations. Hence, let the reading and the address be valid only until the next 5 seconds mark. If it takes more time for SophisticatedSensor to respond to the query, the reading and the address should be disregarded skipping the round(s) and the app should query SophisticatedSensor again at the following 5 seconds mark. Summarizing, a message is sent only when both a valid reading and a valid address are provided by SophisticatedSensor before the next 5 seconds mark.
You can assume that gain of links is not reconfigured during a simulation.
Evaluation¶
The evaluation is based on test simulations (see their descriptions below). In each simulation selected mote(s) is sending 100 readings to another mote. Simulations last 1100 seconds: during first 30s motes boot at randomized times, during subsequent 300s SophisticatedSensors are withheld (to warm up the network), and after that the values and locations are provided. The meyer-heavy.txt noise is used.
The evaluation assesses mainly packet delivery ratio (PDR) – latencies were satisfactory in all tested solutions. Each simulation was run multiple times. The approximated median result was assessed.
Solutions implementing only the greedy routing that perform acceptably well in applicable tests receive 8 points. Solutions implementing the greedy perimeter routing with graph planarization are given mini-points from each test: from 0 (doesn’t work) to 3 (works very well). The sum is scaled to the 7 final points (above the 8 points), and the result is rounded (i.e. round(8 + (mini-points/18)*7)). Finally, some penalty points may be substracted for other flaws found in the solution.
Test 1¶
Two motes send messages to each other. Good link gain.
Test 2¶
12 motes are placed in a S-shape path (greedly routable). Both endpoints are sending messages to each other. Good links gains.
Test 3¶
Motes are located as in Test 2. Links gains are calculated based on distances between motes (using JTossim) – each mote has a few neigbours with different links qualities. Both endpoints send messages to each other.
In this test a realtive (not an absolute) scale is applied: solutions with the highest PDRs receive 3 mini-points.
Test 4¶
Motes are located as in Figure 2 in GPSR Greedy Perimeter Stateless Routing. Mote x sends messages to mote d. Good links gains.
Test 5¶
The setup is as in Test 4. However, after 125 seconds mote w is turned off. Then, after subsequent 125s mote w is turned on but mote y is turned off. Then, after subsequent 125s mote y is turned back on. The test is also repeated in the other way (first mote y, then mote w). The worse result is assessed. Good links gains.
Test 6¶
Motes are located as in Figure 3.8 in Geographic Routing for Wireless Networks. The test is also repeated with a symmetrically reflected setup. The worse result is assessed. Good links gains.