http://www.programmersheaven.com/ Contains the latest posts from the thread 'Automated design of a wireless network' posted on the 'Algorithms' forum at Programmer's Heaven. en Copyright 2012 Programmers Heaven Wed, 23 May 2012 00:44:10 -0700 Wed, 23 May 2012 00:44:10 -0700 Argotic Syndication Framework 2007.3.0.1, http://www.codeplex.com/Argotic http://www.rssboard.org/rss-specification 360 http://www.programmersheaven.com/images/ph.gif http://www.programmersheaven.com/ 88 31 http://www.programmersheaven.com/mb/Algorithms/409978/409978/automated-design-of-a-wireless-network/ Hello!<br /> Help me please with the following problem:<br /> There is a set A of censors in 2-dim. space with known coordinates (x,y). Also there is the set B of points of potential location of wireless routers (WiFi/ZigBee/etc). Each censor must be connected with a wire with length not more than L to the closest router. The max. radius of the wireless connection (i.e. max distance between 2 neighbouring routers) = R. Surely, R is much larger than L. Also there is the limit of number of censors connected to one router. Each router must be able to communicate with at least one another router, so that all of them create a connected graph without isolated 'islands'. I need to find the subset of B where to place the routers so that the total number of routers is minimal.<br /> <br /> After search in Google I realized that this problem is called "facility location problem", but it has no restrictions about distance between facilities. It deals only with distances between a facility and clients. I think that at first I'll solve the facility location and then check the constraint about "connected graph" and if it's not satisfied, add more routers as graph bridges etc - is that right?<br /> The actual questions are:<br /> 1. Have you ever met software for automated design of networks, that computes the optimal locations for communication nodes on the same principles as I've described?<br /> 2. What literature, websites and keywords could you suggest?<br /> 3. In whole, what ideas arise, what algoritms and methods can help in such task?<br /> Thanks in advance.<br /> http://www.programmersheaven.com/mb/Algorithms/409978/409978/automated-design-of-a-wireless-network/ Sat, 28 Nov 2009 08:37:37 -0700 Algorithms