Hi, an algorithm often used to transform a uniform distribution to a gaussian one is the Box-Muller transformation [1], but it uses sin, cos, logarithm and square root functions, that are exceedingly slow on most sensor nodes. You may implement them as lookup tables, but it probably would took too much memory.
Another precise algorithm is the Ziggurat algorithm [2]. It is very fast and it requires only an implementation of the natural logarithm function, that you may approximate using its Taylor expansion. Refer to [3] for a discussion of an hardware-efficient implementation of the Ziggurat algorithm. A quick note on this algorithm that you'll understand only after understanding it (it will be much clearer after looking at Fig. 1 in [3]) : if you don't have strict requirements about randomness quality (which I guess you don't) it is perfectly acceptable to use a linear interpolation on the wedge or choosing with a 1/2 probability whether the random number is within the gaussian distribution or not. An easy approach that does not require any special function is exploiting the central limit theorem, that says when random data from an arÂbitrary distribution is summed over M samples, the probability distribution of the sum begins to approach a normal distribution as M increases. This approach will generate a distribution whose tails are not gaussian, but this is probably not an issue for your application. You can find a discussion of this approach at [4]. Finally, the streamlined approach: generate a set of random number that follow a gaussian ditribution and statically store them in your TinyOS application, then use the uniform random generator to choose a sample from the set and add a small noise to it to make it look more random. It is far from being mathematically correct but it should give a good illusion of a random gaussian measurements. Whatever approach you choose, remember that floating point operations are really slow on most sensor nodes, hence you should implement your generator using fixed point arithmetic. Regards, Giuseppe [1] http://mathworld.wolfram.com/Box-MullerTransformation.html [2] http://en.wikipedia.org/wiki/Ziggurat_algorithm [3] http://www.ee.cooper.edu/~stefan/pubs/conference/ersa2009.pdf [4] http://www.eetimes.com/design/embedded/4211153/DSP-Tricks--Generating- normally-distributed-random-data- On Thursday 10 March 2011 04:40:03 Anas wrote: > Hello, > > I have implemented a simple average filter, but I am required to > generate Random numbers in motes in order to simulate temperature > sensing. Currently, there is a Random() function in nesC which is used > in the BCP code but there is no version of that function for producing > Normally Distributed random numbers (like > in C) . > > Is that possible to do in nesC ? if so, I would appreciate it if you > show me how to implement this ? > > Thanks for your time, > > Anas > _______________________________________________ > Tinyos-help mailing list > [email protected] > https://www.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-help -- Giuseppe Cardone, Ph.D. Student DEIS-LIA - University of Bologna E-mail: [email protected] Web: http://lia.deis.unibo.it/Staff/GiuseppeCardone/ _______________________________________________ Tinyos-help mailing list [email protected] https://www.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-help
