From e2b6cb3eecf554e47bc44eb65b9ba5af43ca51f0 Mon Sep 17 00:00:00 2001 From: scipio Date: Mon, 21 May 2007 21:35:54 +0000 Subject: [PATCH] Improved accuracy of acknowledgement delivery by considering SNR curves. Currently, ack reception is based on the same SNR/PRR curve as packet delivery. This is pessimistic, due to the fact that acks are shorter than packets. I need to measure the ARR/SNR curve to put it something more accurate. Also, currently TOSSIM does not model false positives, something I will be adding shortly. --- apps/tests/TestSimComm/README | 14 ++++- apps/tests/TestSimComm/test-asym.py | 49 ++++++++++++++++ tos/lib/tossim/CpmModelC.nc | 87 +++++++++++++++++++++++----- tos/lib/tossim/GainRadioModel.nc | 3 +- tos/lib/tossim/TossimPacketModelC.nc | 2 +- 5 files changed, 137 insertions(+), 18 deletions(-) create mode 100644 apps/tests/TestSimComm/test-asym.py diff --git a/apps/tests/TestSimComm/README b/apps/tests/TestSimComm/README index 9e7d2df1..30e4d7a1 100644 --- a/apps/tests/TestSimComm/README +++ b/apps/tests/TestSimComm/README @@ -1,4 +1,4 @@ -TestTimer, 5/17/07 +TestTimer, 5/22/07 This application tests the TOSSIM radio model by setting up a simple hidden terminal case. It checks whether packets collide correctly and @@ -10,8 +10,9 @@ There are three test cases: test-equal.py: Tests whether two nodes that are hidden terminals cause collisions. The two nodes have equal signal strengths, so a -collision should corrupt both packets. If one packet is lost, -the other should be too. +collision should corrupt both packets. If one packet is lost due to +a collision, the other should be too. Note that packets can be +lost in the absence of collisions due to external interference. test-unequal.py: Tests whether two nodes that are hidden terminals cause collisions. The two nodes have signal strengths that differ @@ -21,5 +22,12 @@ from node 1 is lost, the packet from node 3 should be as well. However, a loss from node 3 does not imply a loss from node 1, as it is stronger. +test-asym.py: Tests whether asymmetric links can have high delivery +rates but low acknowledgement rates. Checks that acknowledgements +follow SNR curves properly. In this test, both 1 and 3 have high +quality links (-60 dBm) to node 2, but the reverse links (2 to 1 and +2 to 3) are much worse (-80 dBm). You should see packet deliveries +like test-equal.py but few acknowledgements. + Philip Levis diff --git a/apps/tests/TestSimComm/test-asym.py b/apps/tests/TestSimComm/test-asym.py new file mode 100644 index 00000000..a84c4544 --- /dev/null +++ b/apps/tests/TestSimComm/test-asym.py @@ -0,0 +1,49 @@ +from TOSSIM import * +import sys +import time + +t = Tossim([]) +r = t.radio(); + +t.addChannel("TestComm", sys.stdout) +t.addChannel("SNRLoss", sys.stdout) + +#t.addChannel("Acks", sys.stdout) +#t.addChannel("Gain", sys.stdout) +#t.addChannel("CpmModelC", sys.stdout) +#t.addChannel("AM", sys.stdout) + + +start = time.time(); +m1 = t.getNode(1) +m2 = t.getNode(2) +m3 = t.getNode(3) + +# Set up a hidden terminal problem, where 1 and 3 +# are closely synchronized, but cannot hear each other. +m1.bootAtTime(345321); +m2.bootAtTime(82123411); +m3.bootAtTime(345325); +r.add(1, 2, -60.0); +r.add(2, 1, -80.0); +r.add(3, 2, -60.0); +r.add(2, 3, -80.0); + +noise = open("meyer-short.txt", "r") +lines = noise.readlines() +for line in lines: + str = line.strip() + if (str != ""): + val = int(str) + m1.addNoiseTraceReading(val) + m2.addNoiseTraceReading(val) + m3.addNoiseTraceReading(val) + +m1.createNoiseModel() +m2.createNoiseModel() +m3.createNoiseModel() + +for i in range(0, 1000000): + t.runNextEvent(); + + diff --git a/tos/lib/tossim/CpmModelC.nc b/tos/lib/tossim/CpmModelC.nc index e6f097c4..5e6b61e1 100644 --- a/tos/lib/tossim/CpmModelC.nc +++ b/tos/lib/tossim/CpmModelC.nc @@ -59,6 +59,7 @@ implementation { sim_time_t start; sim_time_t end; double power; + double reversePower; bool lost; bool ack; message_t* msg; @@ -68,8 +69,14 @@ implementation { receive_message_t* outstandingReceptionHead = NULL; receive_message_t* allocate_receive_message(); + void free_receive_message(receive_message_t* msg); sim_event_t* allocate_receive_event(sim_time_t t, receive_message_t* m); + bool shouldReceive(double SNR); + bool checkReceive(receive_message_t* msg); + double packetNoise(receive_message_t* msg); + double checkPrr(receive_message_t* msg); + double timeInMs() { sim_time_t ftime = sim_time(); int hours, minutes, seconds; @@ -131,10 +138,52 @@ implementation { return (signalStr - noise); } + double arr_estimate_from_snr(double SNR) { + double beta1 = 1.3687; + double beta2 = 0.9187; + double SNR_lin = pow(10.0, SNR/10.0); + double X = fabs(SNR_lin-beta2); + double PSE = 0.5*erfc(beta1*sqrt(X/2)); + double prr_hat = pow(1-PSE, 23*2); + dbg("CpmModelC,SNRLoss", "SNR is %lf, ARR is %lf\n", SNR, prr_hat); + if (prr_hat > 1) + prr_hat = 1; + else if (prr_hat < 0) + prr_hat = 0; + + return prr_hat; + } + + int shouldAckReceive(double snr) { + double prr = arr_estimate_from_snr(snr); + double coin = RandomUniform(); + if ( (prr != 0) && (prr != 1) ) { + if (coin < prr) + prr = 1.0; + else + prr = 0.0; + } + return (int)prr; + } + void sim_gain_ack_handle(sim_event_t* evt) { - if (outgoing != NULL && requestAck && sim_mote_is_on(sim_node())) { - signal Model.acked(outgoing); + // Four conditions must hold for an ack to be issued: + // 1) Transmitter is still sending a packet (i.e., not cancelled) + // 2) The packet requested an acknowledgment + // 3) The transmitter is on + // 4) The packet passes the SNR/ARR curve + if (requestAck && // This + outgoing != NULL && + sim_mote_is_on(sim_node())) { + receive_message_t* rcv = (receive_message_t*)evt->data; + double power = rcv->reversePower; + double noise = packetNoise(rcv); + double snr = power - noise; + if (shouldAckReceive(snr)) { + signal Model.acked(outgoing); + } } + free_receive_message((receive_message_t*)evt->data); } sim_event_t receiveEvent; @@ -155,14 +204,17 @@ implementation { return noise_hash_generation() < clearThreshold; } - void sim_gain_schedule_ack(int source, sim_time_t t) { + void sim_gain_schedule_ack(int source, sim_time_t t, receive_message_t* r) { sim_event_t* ackEvent = (sim_event_t*)malloc(sizeof(sim_event_t)); + ackEvent->mote = source; ackEvent->force = 1; ackEvent->cancelled = 0; ackEvent->time = t; ackEvent->handle = sim_gain_ack_handle; ackEvent->cleanup = sim_queue_cleanup_event; + ackEvent->data = r; + sim_queue_insert(ackEvent); } @@ -173,7 +225,7 @@ implementation { double X = fabs(SNR_lin-beta2); double PSE = 0.5*erfc(beta1*sqrt(X/2)); double prr_hat = pow(1-PSE, 23*2); - dbg("CpmModelC", "SNR is %lf, PRR is %lf\n", SNR, prr_hat); + dbg("CpmModelC,SNR", "SNR is %lf, PRR is %lf\n", SNR, prr_hat); if (prr_hat > 1) prr_hat = 1; else if (prr_hat < 0) @@ -227,6 +279,9 @@ implementation { } + /* Handle a packet reception. If the packet is being acked, + pass the corresponding receive_message_t* to the ack handler, + otherwise free it. */ void sim_gain_receive_handle(sim_event_t* evt) { receive_message_t* mine = (receive_message_t*)evt->data; receive_message_t* predecessor = NULL; @@ -250,7 +305,7 @@ implementation { } dbg("CpmModelC,SNRLoss", "Packet from %i to %i\n", (int)mine->source, (int)sim_node()); if (!checkReceive(mine)) { - dbg("CpmModelC,SNRLoss", " - lost packet from as SNR was too low.\n"); + dbg("CpmModelC,SNRLoss", " - lost packet from %i as SNR was too low.\n", (int)mine->source); mine->lost = 1; } if (!mine->lost) { @@ -265,7 +320,10 @@ implementation { // If we scheduled an ack, receiving = 0 when it completes if (mine->ack && signal Model.shouldAck(mine->msg)) { dbg_clear("CpmModelC", " scheduling ack.\n"); - sim_gain_schedule_ack(mine->source, sim_time() + 1); + sim_gain_schedule_ack(mine->source, sim_time() + 1, mine); + } + else { // Otherwise free the receive_message_t* + free_receive_message(mine); } // We're searching for new packets again receiving = 0; @@ -274,12 +332,11 @@ implementation { receiving = 0; dbg_clear("CpmModelC,SNRLoss", " -packet was lost.\n"); } - free(mine); } // Create a record that a node is receiving a packet, // enqueue a receive event to figure out what happens. - void enqueue_receive_event(int source, sim_time_t endTime, message_t* msg, bool receive, double power) { + void enqueue_receive_event(int source, sim_time_t endTime, message_t* msg, bool receive, double power, double reversePower) { sim_event_t* evt; receive_message_t* list; receive_message_t* rcv = allocate_receive_message(); @@ -288,6 +345,7 @@ implementation { rcv->start = sim_time(); rcv->end = endTime; rcv->power = power; + rcv->reversePower = reversePower; rcv->msg = msg; rcv->lost = 0; rcv->ack = receive; @@ -329,15 +387,15 @@ implementation { } - void sim_gain_put(int dest, message_t* msg, sim_time_t endTime, bool receive, double power) { + void sim_gain_put(int dest, message_t* msg, sim_time_t endTime, bool receive, double power, double reversePower) { int prevNode = sim_node(); dbg("CpmModelC", "Enqueing reception event for %i at %llu with power %lf.\n", dest, endTime, power); sim_set_node(dest); - enqueue_receive_event(prevNode, endTime, msg, receive, power); + enqueue_receive_event(prevNode, endTime, msg, receive, power, reversePower); sim_set_node(prevNode); } - command void Model.putOnAirTo(int dest, message_t* msg, bool ack, sim_time_t endTime, double power) { + command void Model.putOnAirTo(int dest, message_t* msg, bool ack, sim_time_t endTime, double power, double reversePower) { gain_entry_t* neighborEntry = sim_gain_first(sim_node()); requestAck = ack; outgoing = msg; @@ -345,7 +403,7 @@ implementation { while (neighborEntry != NULL) { int other = neighborEntry->mote; - sim_gain_put(other, msg, endTime, ack && (other == dest), power + sim_gain_value(sim_node(), other)); + sim_gain_put(other, msg, endTime, ack && (other == dest), power + sim_gain_value(sim_node(), other), reversePower + sim_gain_value(other, sim_node())); neighborEntry = sim_gain_next(neighborEntry); } } @@ -370,5 +428,8 @@ implementation { receive_message_t* allocate_receive_message() { return (receive_message_t*)malloc(sizeof(receive_message_t)); } - + + void free_receive_message(receive_message_t* msg) { + free(msg); + } } diff --git a/tos/lib/tossim/GainRadioModel.nc b/tos/lib/tossim/GainRadioModel.nc index 688e07a2..8a3a40f8 100644 --- a/tos/lib/tossim/GainRadioModel.nc +++ b/tos/lib/tossim/GainRadioModel.nc @@ -41,7 +41,8 @@ interface GainRadioModel { message_t* msg, bool ack, sim_time_t endTime, - double gain); + double gain, + double reverseGain); command void setClearValue(double value); command bool clearChannel(); diff --git a/tos/lib/tossim/TossimPacketModelC.nc b/tos/lib/tossim/TossimPacketModelC.nc index 8e503ca6..981c65fc 100644 --- a/tos/lib/tossim/TossimPacketModelC.nc +++ b/tos/lib/tossim/TossimPacketModelC.nc @@ -254,7 +254,7 @@ implementation { evt->handle = send_transmit_done; dbg("TossimPacketModelC", "PACKET: Broadcasting packet to everyone.\n"); - call GainRadioModel.putOnAirTo(destNode, sending, metadata->ack, evt->time, 0.0); + call GainRadioModel.putOnAirTo(destNode, sending, metadata->ack, evt->time, 0.0, 0.0); metadata->ack = 0; evt->time += (sim_csma_rxtx_delay() * (sim_ticks_per_sec() / sim_csma_symbols_per_sec())); -- 2.39.2