Re: [Server-devel] [OLPC Networking] RSSI value questions
On Wed, 2008-04-02 at 17:05 -0400, John Watlington wrote: > > At 2.4 GHz, the interference between multiple paths makes > signal level measurement pretty useless for determining position. > If you do this to a number of spatially distributed access points, > you can improve the estimate... This is how the Bluetooth Location > service works... > Actually, you can do a decent idea of location based on signal strength *iff* you have a lot of *known* receiving stations and lots of *known* measurements. Jamey Hicks and Andy Christian at HP's CRL (our lab that got shutdown upstairs), were able to do quite decently. But I don't think it is remotely practical for our use. - Jim -- Jim Gettys One Laptop Per Child ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: [Server-devel] [OLPC Networking] RSSI value questions
I realized after chatting with Ben that my assessments were wrong about this being a feasible project for the summer. The main issue is still that the radios dynamically adjust their gain to increase RSSI between nodes that are farther apart. I do have ideas that may be possible to overcome this, but some experimentation would be needed. Depending on how often the gain is adjusted and in what ways, inferring the gain may be possible. According to the link below, the setbcnavg command can be used to "set the weighting factor for calculating RSSI," but I'm not sure how this affects connectivity between nodes. If setting the value as high as possible or as low as possible causes nodes to disappear from a radio's "view," then direction is easy to discover by having all XOs step through the values and recording which nodes come back within view and when. I think this would provide direction, unless the command doesn't affect connectivity. I'll post the rest of my thoughts later, as I need to finish some other work. Unfortunately, I don't have the equipment necessary to test out any other theories, nor do I feel I have the technical knowledge to see this project through, so I'm afraid this is where I get off the bus. Thanks for all of your input. http://wiki.laptop.org/go/Wireless_Driver_README - Crawford ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: [Server-devel] [OLPC Networking] RSSI value questions
I'm not very concerned about FUD (fear, uncertainty, and doubt) being spread by providers of a competing operating system. The inclusion of GPS data into the system would be purely optional and currently and the XOs do not have GPS capabilities. A software implementation COULD be put in the system that would contact a server that uses the XO's IP to identify the country and possibly the city a machine is connecting from, but since the software is open-sourced, it would be easy to remove from the system. Regardless of all this, what I'm proposing is also completely optional an available for anyone to use if they so choose. My application would not be contacting systems outside of the network that the machines are running on, so any worries concerning privacy and control would be meaningless. Thanks for your concern, though, and I appreciate any suggestions you may have that would comfort people's fears concerning privacy, especially when it comes to the program's use outside of the US. - Crawford ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: [Server-devel] [OLPC Networking] RSSI value questions
Michael - Do you think the patent you're referring to would be a significant roadblock in implementing this system using wifi signal strength measurements? The few patents that I've seen (though I haven't been actively searching) seem to be designed with a system that has a "plurality of receiving stations with known locations" in mind, which wouldn't affect things here, considering this would be a system with purely unknown locations. To everyone reading - I agree that the XS isn't necessary, though it would allow for more applications, security being one that was pointed out earlier. Also, by attaching a GPS antenna to the server, an approximate GPS location could be assigned to nodes within the network. I think my initial question regarding whether or not the hardware is currently capable of implementing this system overall is a definitive "Yes," so I should be completing my proposal this evening. I'll post it to the three mailing lists we've been having this discussion on. Please feel free to rip it to shreds, provide constructive criticism, or wish me luck as you see fit :) - Crawford ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: [Server-devel] [OLPC Networking] RSSI value questions
On Fri, 4 Apr 2008, John Watlington wrote: > A guiding design principle for any XO activity is that it be designed > to work without a school server. Learning doesn't stop at the school gate! > > The only thing special about an XS (or any access point) is that we can > know (absolutely) where it is. Whatever system is designed should > allow arbitrary peers to declare that they know where they are (and > should handle the fact that some of them either lie or have a very hazy > idea of where they are...) Perhaps an XS Active Antenna or Access Point > is simply an example of a certifiably trusted position beacon. > > I still prefer the idea of using audio, a la Acoustic Measure by Ben or > a three-D, multiple device version: > http://web.media.mit.edu/~vmb/papers/AES05.pdf > (longer version at http://web.media.mit.edu/~vmb/papers/DaltonMS.pdf) > Research into less intrusive methods (using ambient noise, or sounds > generated by the systems while doing other tasks, as the > basis for obtaining the location information) is needed. you could take three laptops and have them do acoustic measures from each other and then work out from that. I don't think it's worth trying to deal with system lieing about their location (at least not for the first cut) one thing to keep in mind is that each measurement has an error band accociated with it, so as you get secondary positions and work out from there the locations become less precise. one question about the XO hardware. are the two antennas directly connected inside the machine, or is there some way (possibly requiring a firmware modification) to find the difference between a given signal between the two antennas? David Lang > Cheers, > wad > > On Apr 4, 2008, at 4:39 AM, Oliver Mattos wrote: > >> why exactly is an XS needed at all - what about just a mesh of laptops with >> no XS. I agree then there are NO refrence points at all, so orientation >> and world-position of the generated map can't be determined, but the rest >> of the info still remains useful. The XS is simply another node - there is >> no reason it should be required. >> >> In terms of an algorithm for calculating positions from a series of metrics >> with no known points, the best I can think of is successive approximation. >> Basicly, place all the nodes randomly on a map, attach "virtual springs" >> between nodes that have connectivity, where the springs ideal length is >> determined by the signal strength/other metric, and springgyness is >> determined by the metrics margin of error, and then do a physics simulation >> of where they all end up when released. Using that algorithm, multiple >> types of metric can be used to generate the same map. >> >> After generating the map once, future generations would require many fewer >> iterations of the physics simulation, therefore less processing time even >> for big meshes, so it would probably be possible to update the map in real >> time as new results come in. >> >> There are quite a few optimisations for the above, for example "replusion" >> springs with a negative force could be used for nodes that are currently >> close together on the map but have no connectivity. - that would provide >> much more accurate mapping in sparse meshes where some laptops have 2 or >> fewer neighbors. >> >> On Fri, Apr 4, 2008 at 7:06 AM, Ryan Crawford Comeaux >> <[EMAIL PROTECTED]> wrote: >> Just to address a few other issues/questions raised... >> >> If there is only one antenna on a server, then as long as 3 other nodes are >> considered relatively stationary, I think their 2D locations can be deduced >> from each node's measurements of the other 4. An easy to use interface can >> allow the user to orient the generated map with respect to whatever >> reference point they like; ideally, the final program would allow for a >> floor plan of the building to be displayed underneath the topological >> mapping. >> >> With respect to granularity of different measurements, I think inaccurate >> measurements can be averaged over time, since some would necessarily be >> more accurate than others, allowing for a more accurate map as time passes. >> >> Ben stated that the dynamic gain isn't available in user space. I'm just >> wondering if there's a way to passively determine the gain and if this >> would even be helpful in determining location. Any ideas? I'm not so >> experienced in RF tech that I can come up with how knowing the gain would >> be useful, but if it is useful, then I think it'd be easy enough to figure >> out some sort of indicator that's relative to the fluctuations in whatever >> measurements the gain affects. Again, let me know if I'm that kid out in >> left field wearing his glove on his head and facing away from the bases... >> >> I feel pretty optimistic about the feasibility of this kind of project. >> There seem to be a few good measurement techniques to go by, as well >> different metho
Re: [Server-devel] [OLPC Networking] RSSI value questions
A guiding design principle for any XO activity is that it be designed to work without a school server. Learning doesn't stop at the school gate! The only thing special about an XS (or any access point) is that we can know (absolutely) where it is. Whatever system is designed should allow arbitrary peers to declare that they know where they are (and should handle the fact that some of them either lie or have a very hazy idea of where they are...) Perhaps an XS Active Antenna or Access Point is simply an example of a certifiably trusted position beacon. I still prefer the idea of using audio, a la Acoustic Measure by Ben or a three-D, multiple device version: http://web.media.mit.edu/~vmb/papers/AES05.pdf (longer version at http://web.media.mit.edu/~vmb/papers/DaltonMS.pdf) Research into less intrusive methods (using ambient noise, or sounds generated by the systems while doing other tasks, as the basis for obtaining the location information) is needed. Cheers, wad On Apr 4, 2008, at 4:39 AM, Oliver Mattos wrote: > why exactly is an XS needed at all - what about just a mesh of > laptops with no XS. I agree then there are NO refrence points at > all, so orientation and world-position of the generated map can't > be determined, but the rest of the info still remains useful. The > XS is simply another node - there is no reason it should be required. > > In terms of an algorithm for calculating positions from a series of > metrics with no known points, the best I can think of is successive > approximation. Basicly, place all the nodes randomly on a map, > attach "virtual springs" between nodes that have connectivity, > where the springs ideal length is determined by the signal strength/ > other metric, and springgyness is determined by the metrics margin > of error, and then do a physics simulation of where they all end up > when released. Using that algorithm, multiple types of metric can > be used to generate the same map. > > After generating the map once, future generations would require > many fewer iterations of the physics simulation, therefore less > processing time even for big meshes, so it would probably be > possible to update the map in real time as new results come in. > > There are quite a few optimisations for the above, for example > "replusion" springs with a negative force could be used for nodes > that are currently close together on the map but have no > connectivity. - that would provide much more accurate mapping in > sparse meshes where some laptops have 2 or fewer neighbors. > > On Fri, Apr 4, 2008 at 7:06 AM, Ryan Crawford Comeaux > <[EMAIL PROTECTED]> wrote: > Just to address a few other issues/questions raised... > > If there is only one antenna on a server, then as long as 3 other > nodes are considered relatively stationary, I think their 2D > locations can be deduced from each node's measurements of the other > 4. An easy to use interface can allow the user to orient the > generated map with respect to whatever reference point they like; > ideally, the final program would allow for a floor plan of the > building to be displayed underneath the topological mapping. > > With respect to granularity of different measurements, I think > inaccurate measurements can be averaged over time, since some would > necessarily be more accurate than others, allowing for a more > accurate map as time passes. > > Ben stated that the dynamic gain isn't available in user space. > I'm just wondering if there's a way to passively determine the gain > and if this would even be helpful in determining location. Any > ideas? I'm not so experienced in RF tech that I can come up with > how knowing the gain would be useful, but if it is useful, then I > think it'd be easy enough to figure out some sort of indicator > that's relative to the fluctuations in whatever measurements the > gain affects. Again, let me know if I'm that kid out in left field > wearing his glove on his head and facing away from the bases... > > I feel pretty optimistic about the feasibility of this kind of > project. There seem to be a few good measurement techniques to go > by, as well different methods to compute the data. If the XOs > pitch in and tell the server where they think other nodes and > themselves are, relative to each other, that would provide another > set of input to include when averaging out measurements. > > For those of you that would like some light reading on the topic of > modeling this information and computing it, here are a couple of > papers that attempt to do similar things with GSM signals and > neural networks: > > http://ieeexplore.ieee.org/iel5/9603/30336/01394788.pdf? > isnumber=30336&prod=CNF&arnumber=1394788&arSt=+133&ared= > +136&arAuthor=Debono%2C+C.J.%3B+Buhagiar%2C+J.K. > http://ieeexplore.ieee.org/iel5/4222741/4222742/04222782.pdf? > arnumber=4222782 > > - Crawford > >
Re: [Server-devel] [OLPC Networking] RSSI value questions
Just to address a few other issues/questions raised... If there is only one antenna on a server, then as long as 3 other nodes are considered relatively stationary, I think their 2D locations can be deduced from each node's measurements of the other 4. An easy to use interface can allow the user to orient the generated map with respect to whatever reference point they like; ideally, the final program would allow for a floor plan of the building to be displayed underneath the topological mapping. With respect to granularity of different measurements, I think inaccurate measurements can be averaged over time, since some would necessarily be more accurate than others, allowing for a more accurate map as time passes. Ben stated that the dynamic gain isn't available in user space. I'm just wondering if there's a way to passively determine the gain and if this would even be helpful in determining location. Any ideas? I'm not so experienced in RF tech that I can come up with how knowing the gain would be useful, but if it is useful, then I think it'd be easy enough to figure out some sort of indicator that's relative to the fluctuations in whatever measurements the gain affects. Again, let me know if I'm that kid out in left field wearing his glove on his head and facing away from the bases... I feel pretty optimistic about the feasibility of this kind of project. There seem to be a few good measurement techniques to go by, as well different methods to compute the data. If the XOs pitch in and tell the server where they think other nodes and themselves are, relative to each other, that would provide another set of input to include when averaging out measurements. For those of you that would like some light reading on the topic of modeling this information and computing it, here are a couple of papers that attempt to do similar things with GSM signals and neural networks: http://ieeexplore.ieee.org/iel5/9603/30336/01394788.pdf?isnumber=30336&prod=CNF&arnumber=1394788&arSt=+133&ared=+136&arAuthor=Debono%2C+C.J.%3B+Buhagiar%2C+J.K . http://ieeexplore.ieee.org/iel5/4222741/4222742/04222782.pdf?arnumber=4222782 - Crawford ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: [Server-devel] [OLPC Networking] RSSI value questions
On Thu, Apr 3, 2008 at 8:55 PM, <[EMAIL PROTECTED]> wrote: > On Thu, 3 Apr 2008, Michail Bletsas wrote: > > Let's not forget that you need some fixed reference points. > > In commercial systems, the locations of the access points are well > > known. > > In ad-hoc networks the best that you can hope for is a topological map. > > > > the assumption was that the measurements are being done from fixed points. > either the school server antenna locations, or the known locations of > specific assistant laptops. > > without known locations you can't do much. > > David Lang > Suppose you have your initial fixed points with known locations (server antennas and any standalone repeaters). Wouldn't you be able to identify "temporarily" stationary points that, after deducing their locations, could be deemed additional "listening stations"? Once a node is identified as such, any additional measurements it provides can be deemed credible and then used to determine the locations of less stationary nodes. As David said, some commercial solutions require calibration by walking a node around the premises. I think this has been shown to be fairly accurate for a single AP's coverage area without having to add additional APs to the network. Most of the comments have been along the lines of using single measurements to identify distances of separation. I think a better solution would be to include the mesh's routing table, packet arrival times, etc. along with RSSI measurements. If you generate one or more likely maps from each and then average them out, I suspect you'd get a fairly accurate estimation of where everybody is. Coupled with preloaded measurements from around the premises, a viable solution seems likely. Is the XS capable of installing/"pushing" applications onto XOs automatically? If so, that allows for a very easy way to let the XOs participate in the process without bothering users, as well as distributing some of the number-crunching to take make things easier for the XS app. Am I displaying complete naivety here about everything involved or does any of this stuff make sense to you guys? -Crawford ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: [Server-devel] [OLPC Networking] RSSI value questions
On Thu, 3 Apr 2008, Michail Bletsas wrote: > Let's not forget that you need some fixed reference points. > In commercial systems, the locations of the access points are well known. > In ad-hoc networks the best that you can hope for is a topological map. the assumption was that the measurements are being done from fixed points. either the school server antenna locations, or the known locations of specific assistant laptops. without known locations you can't do much. David Lang > M. > > > > [EMAIL PROTECTED] wrote on 04/02/2008 01:45:14 AM: > >> Ryan, >> >> Like Ben said, inducing the physical layout of the network from metrics >> such as RSSI will give you poor results for various reasons. What >> "Space" did was to average arrival rates from direct neighbors over a >> "long" period of time (anywhere between 1 and 10 seconds) to avoid >> highly temporal effects like multipath and noise. Even so, the result is > >> only a rough layout of the network. If you'd like to achieve better >> accuracy I thing you should combine other ideas like sound measurements, > >> as Ben suggested. >> >> Pol >> >> > > ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: [Server-devel] [OLPC Networking] RSSI value questions
Let's not forget that you need some fixed reference points. In commercial systems, the locations of the access points are well known. In ad-hoc networks the best that you can hope for is a topological map. M. [EMAIL PROTECTED] wrote on 04/02/2008 01:45:14 AM: > Ryan, > > Like Ben said, inducing the physical layout of the network from metrics > such as RSSI will give you poor results for various reasons. What > "Space" did was to average arrival rates from direct neighbors over a > "long" period of time (anywhere between 1 and 10 seconds) to avoid > highly temporal effects like multipath and noise. Even so, the result is > only a rough layout of the network. If you'd like to achieve better > accuracy I thing you should combine other ideas like sound measurements, > as Ben suggested. > > Pol > > ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: [Server-devel] [OLPC Networking] RSSI value questions
On Thu, 3 Apr 2008, Aaron Huslage wrote: > How do currently available commercial wireless topology mappers do this? > I don't have direct experiance (the brother of a friend goes around installing these things, so my knowledge is third hand) but my understanding is that they deploy their access points and they triangulate the location of the wireless devices with a minimum of three access points deployed (more if more coverage is needed). I know that calibration is needed (something like walking the building with a known laptop after it's setup) radio direction finding to get a bearing from two antennas is not bleeding edge technology. It can require specialized hardware, but not always. David Lang ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: [Server-devel] [OLPC Networking] RSSI value questions
On Apr 2, 2008, at 5:05 PM, John Watlington wrote: > > On Apr 2, 2008, at 4:00 PM, Martin Langhoff wrote: > >> On Wed, Apr 2, 2008 at 3:38 PM, <[EMAIL PROTECTED]> wrote: >>> the problem with trying to use sound is that it requres a clear >>> path from >>> the servers to the laptops, something I would not expect to see >>> very much. >>> it's also very sensitive to the direction the laptops are pointing. >> >> Absolutely, and the XS doesn't have mics, even less directional >> mics ;-) > > It's in that hole on the left hand side of the screen... It has been pointed out that I've gotten to old to tell the difference between XO and XS.I have no defence... We could make the XS beep, and triangulate its location from the laptop locations... >> The 802.11 signal will also have dirty paths in some directions. >> Strategic antenna location and signal timing is the only way I can >> see >> this working. It would be fantastic to have a simple thing to demo >> physics and maths based on such triangulation. > > At 2.4 GHz, the interference between multiple paths makes > signal level measurement pretty useless for determining position. > If you do this to a number of spatially distributed access points, > you can improve the estimate... This is how the Bluetooth Location > service works... > > wad ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: [Server-devel] [OLPC Networking] RSSI value questions
On Apr 2, 2008, at 4:00 PM, Martin Langhoff wrote: > On Wed, Apr 2, 2008 at 3:38 PM, <[EMAIL PROTECTED]> wrote: >> the problem with trying to use sound is that it requres a clear >> path from >> the servers to the laptops, something I would not expect to see >> very much. >> it's also very sensitive to the direction the laptops are pointing. > > Absolutely, and the XS doesn't have mics, even less directional > mics ;-) It's in that hole on the left hand side of the screen... > The 802.11 signal will also have dirty paths in some directions. > Strategic antenna location and signal timing is the only way I can see > this working. It would be fantastic to have a simple thing to demo > physics and maths based on such triangulation. At 2.4 GHz, the interference between multiple paths makes signal level measurement pretty useless for determining position. If you do this to a number of spatially distributed access points, you can improve the estimate... This is how the Bluetooth Location service works... wad ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: [Server-devel] [OLPC Networking] RSSI value questions
To be honest I very much doubt the hardware in the wireless adaptors could measure time in single digit nanoseconds, and even if they could it would probably require a change in the over the air signal to use more bandwidth (spectrum) for a "pulse" to get better time resolution, which in turn would require hardware modification. I would think the sound and signal strength meter are better metrics. Remember although signal strength is a bad indicator by itself, it can be much improved with 2 aerials and the large number of possible pairs to measure signal strength between in a well linked mesh. On Wed, Apr 2, 2008 at 3:14 PM, Martin Langhoff <[EMAIL PROTECTED]> wrote: > On Wed, Apr 2, 2008 at 4:27 AM, <[EMAIL PROTECTED]> wrote: > > trying to work from signal strength won't work well, but you may be > able > > to triangulate based on the arrival time of the signal at various > > locations. > > > > there are companies that do this commercialy with 3+ access points > > The recommended configuration for mid-to-high-end school servers has 3 > active antennaes attached, and our recommendation is that they are > placed well apart. They can be up to 10m apart due to USB cable lenght > limits, and Wad mentioned 2m minimum recommended distance. If the > distance is enough (in relation to the granularity of timers in the > antennaes) then telling the XS about relative location of the > antennaes could provide enough info. > > Having said that, I suspect that being able to do any of the above is > somewhat far ahead in time ;-) > > cheers, > > > > m > -- > [EMAIL PROTECTED] > [EMAIL PROTECTED] -- School Server Architect > - ask interesting questions > - don't get distracted with shiny stuff - working code first > - http://wiki.laptop.org/go/User:Martinlanghoff > ___ > Networking mailing list > [EMAIL PROTECTED] > http://lists.laptop.org/listinfo/networking > ___ Server-devel mailing list [EMAIL PROTECTED] http://lists.laptop.org/listinfo/server-devel