Hi, Joe: I agree that CSMA is a good solution, especially because it has little overhead. Also, I would be most interested in knowing potential improvements on CSMA to detect hidden terminals.
I'll try to re-do the 4-mote test with the current TinyOS stack, in both one-hop range (clustered) and multi-hop configuration with hidden terminals. In one of my previous experiments, a linear configuration is used to produce hidden terminals -- 4 motes without external antennas were deployed in one straight line at a suitable distance with each other (the distance varies in different environments)... I appreciate your offering to do tests. After we get results, we can hopefully compare with each other's and maybe fine some interesting things out. Unfortunately, looking at my schedule, I may not be able to finish my tests very soon. I'll try to do it as soon as possible, though :P Cheers, lin On Fri, Sep 12, 2003 at 12:47:41AM -0700, Joe Polastre wrote: > 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 _______________________________________________ Tinyos-users mailing list [EMAIL PROTECTED] http://mail.Millennium.Berkeley.EDU/mailman/listinfo/tinyos-users
