IMO the 2.5 times better than the CC1K default stack comes from a time when the stack was broken (which was unfortunately my fault)
If you check out the current CVS (or if you check out my changes to the beta/CC1000Radio stack), I have a feeling you'll find that the success rate is better. Although CSMA can fail in the case of the hidden node problem (and the current implementation in fact does), I think there's some cool things that can be done for CSMA to detect that. Perhaps I'm just not a fan of writing off CSMA so quickly ;) If you have 4 motes sending Chirps with no multihop, then it's not clear that the hidden node problem will manifest itself. I will try a few different configs on Monday with the new CSMA and let you know the results. -Joe -----Original Message----- From: Lin Gu [mailto:[EMAIL PROTECTED] Sent: Thursday, September 11, 2003 11:57 AM To: Joe Polastre Cc: [EMAIL PROTECTED]; [EMAIL PROTECTED] Subject: Re: [Tinyos] Collision-free MAC protocol Hi, Joe: Thanks for the feedback. The main purpose of TDMA-based MAC is to provide reliable packet transmission, and the experiments I did were not designed to measure throughput -- the four motes sending 2.5 'Chirp' messages/sec are not sending at their maximum rate, so the result does not translate directly to the throughput performance. You have made a very good point that the throughput will decrease when TDMA is used. This is natural because, in SPRIME, each mote can use no more than 1/4 of the bandwidth in a 4-mote network (Actually, in PRIME there is a mechanism to collect and use idle time slots). But the total throughput of the 4 motes should still use most of the channel bandwidth. I will do further experiments to assess this and possibly modify/improve the current implementation if it does not do well on this metric. The main purpose of TDMA MAC is to increase the 'success rate' of packet delivery. I actually believe your argument that CSMA does a very good job when the network has two motes. But when the number of motes increases, especially, when there are hidden- terminals, CSMA's performance may degrade. The experiment with 4 motes' sending 'Chirp' messages confirms this. The similar experiment with 4 motes using TDMA scheme did very well on this performance metric. Other goals of designing a TDMA MAC include providing predictability, facilitating flexible energy-saving schemes, enabling resource reservation and QoS aware scheduling, and so on. Of course, there is still a long way to go before we see these happening. Cheers, lin On Thu, Sep 11, 2003 at 03:48:02AM -0700, Joe Polastre wrote: > If my calculations are correct, 1 packet every 400ms is 2.5 packets per > second or 1120 bits/sec including preamble -- 580 bits/sec if you just > count the data payload. > > The CSMA layer checked into beta/CC1000Radio achieves 12.1kbps (~30 > packets/sec) with one node and 15.7kbps effective data rate (~35 > packets/sec) with two nodes. The calculated data rate is near 100% > success packet reception and utilizes 82% of the available data > bandwidth of the channel. > > My CSMA can be compiled by including the beta/CC1000Radio and > beta/CALADC directories in your search path when compiling using the -I > directive. > > -Joe > > -----Original Message----- > From: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] On Behalf Of Lin Gu > Sent: Wednesday, September 10, 2003 11:16 PM > To: [EMAIL PROTECTED] > Subject: [Tinyos] Collision-free MAC protocol > > Hi, > > I am pleased to inform you that our group has designed a TDMA-based > MAC protocol, named "PRIME", and has added an implementation of it to > the 'contrib' directory as tinyos-1.x/contrib/prime. > > This is a collision-free MAC protocol. In the test with the > 'Chirp' program on 4 Mica2 motes sending packets at 1 packet/400ms, > the packet delivery success rate is 95%, 2.5 times higher than > the current CSMA-based MAC protocol. > > Actually, the current implementation is a simplified version of the > PRIME protocol (The full implementation was programmed and tested on > Mica, not Mica2 motes). Thus it's called SPRIME. Though not as flexible > as the full implementation, SPRIME is likely to still suffice for most > of applications. > > I am including a README file at the end of this email. You are welcomed > to find the up-to-date version of this file in tinyos-1.x/contrib/prime. > More documentation and a setup program that install/uninstall SPRIME > will be added as soon as I can. > > Comments and suggestions will be much appreciated, and I will be more > than glad to provide support if you'd like to try the protocol with > your applications. > > Best regards, > > lin > -- > Lin Gu > Department of Computer Science > University of Virginia > > > ----------------------------------------------------------- > The README file -- for interested readers > ----------------------------------------------------------- > > > > PRIME Protocol > > > Introduction > ============ > > PRIME (Period Reservation and Inter-Master Estimation) protocol is a > collision-free MAC protocol. It automatically detects interfering nodes > in a network and uses TDMA to coordinate network transmission, so as > to avoid collision. > > SPRIME is a simplified version which supports static time-slot > (super-slot, > in PRIME terminology) assignment. Though not as flexible as PRIME, it > still achieves good performance -- in a test with "Chirp" program on 4 > motes, the packet delivery success rate is 95%, compared with a success > rate of 26.5% with CSMA. > > > Files > ===== > > To facilitate interested developpers to try and test, a working version > including all the supporting files is included in this directory. The > following files and directories are main part of the SPRIME > implementation. > > README This file > tos/system/GenericCommPRIME GenericComm configuraiton file that uses > SPRIME > tos/system/SPRIME.nc SPRIME component > tos/system/MsgPool.nc Message pool (memory mangement) > apps/Benchmark/Chrip.SPRIME Chirp applicaiton, using SPRIME protocol > apps/Benchmark/Chirp Chirp application, using the originial > CSMA MAC that comes with TinyOS > > More documentation will be added as soon as I can. > > > Configuration > ============= > > Right now the default configuration of SPRIME is a 4-mote, consecutive > ID configuration. The parameters are defined as macros in SPRIME.nc. > (TODO: a configuraiton file will be used instead of macros in the > program). > > > Installation > ============ > > Copy the 'prime' directory and set the 'TOSDIR' environment variable to > the 'tos' directory in the 'prime' directory. (TODO: a setup program > will > be provided later to configure the existing TinyOS to switch between > using SPRIME and the original CSMA MAC protocol) > > > Test configuration and results > ============================== > > A simple test has been done to assess the performance of SPRIME. Four > motes, mote 0-3, are uploaded with Chirp application and put close to > each other. > > To run the tests, cd to apps/Benchmark/Chirp or > apps/Benchmark/Chirp.SPRIME and use the usual TinyOS build method > > make mica2 install.<mote id> > > to build and upload program. > > To compute the packet delivery rate, use a 'GenericBase' program to > listen > to the packets (you may want to modify the GenericBaseM.nc file to tally > > the packets received). > > Right now, the Chirp programs send 160 packets at the rate of 1 > packet/400ms. > The reference result is as follows > > CSMA MAC SPRIME > -------- ------ > success rate 26.5% 95% > > So the success rate is increased by 258%. > > > History > ======= > > To improve the network performance on the MAC layer, we originally seek > to apply piggybacked acknowledgement to improve reliability. It develops > > to "AMConform", which is a reliable one-hop communication protocol > supporting > most of the functionality in traditional data-link level communication > -- > sliding window control, duplicate removal, queuing, piggybacked > acknowledgement, and re-transmission for unicast communication. The > platform > is TinyOS 0.6 on Mica mote. > > In our experiment and development for tracking demo, the reliable data- > link level component does improve the performance dramatically (But at > least half of the enhancement seems to come from the buffering > functionality). The retransmission introduces delay and impose a burden > on the network when the bandwidth is in shortage. It still does not > handle > the wireless communication well because it does not consider > hidden-terminal, > asymmetric channel, wide interference range, and so on... Retransmission > > also consumes energy. > > As a result, in 2002, PRIME protocol is designed to provide predictable > bahavior without incurring much computation, bandwidth and energy cost. > It's main features include hidden-terminal and interference detection > and > TDMA scheduling. The development is based on TinyOS 0.6 on Mica motes. > > To make the PRIME protocol work with TinyOS-1.x and NesC, the code is > modified early this year (2003) and the functionality is trimmed to make > > it easier to be ported to programs where AMStandard is used, hence the > SPRIME protocol. > > Acknoledgements > =============== > > The current PRIME/SPRIME implementation is based on TinyOS. Thanks to > all > the people from Berkeley and other groups for helping me in various > development issues. > > > Support and bug report > ====================== > > Please feel free to contact me for questions, bug reports, suggestions, > or > just talking. > > Lin Gu > Computer Science Department > Univ. of Virginia > [EMAIL PROTECTED] > Tel: 434-249-3158 > > ******************************************************************** > Sept 10, 2003 > > > > > _______________________________________________ > Tinyos mailing list > [EMAIL PROTECTED] > http://mail.Millennium.Berkeley.EDU/mailman/listinfo/tinyos > > _______________________________________________ > Tinyos mailing list > [EMAIL PROTECTED] > http://mail.Millennium.Berkeley.EDU/mailman/listinfo/tinyos _______________________________________________ Tinyos-users mailing list [EMAIL PROTECTED] http://mail.Millennium.Berkeley.EDU/mailman/listinfo/tinyos-users
