## Algorithms

Moderators: None (Apply to moderate this forum)
Number of posts: 786

This Forum Only

Automated design of a wireless network Posted by IstariRadagast on 28 Nov 2009 at 8:37 AM
Hello!
Help me please with the following problem:
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.

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?
The actual questions are:
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?
2. What literature, websites and keywords could you suggest?
3. In whole, what ideas arise, what algoritms and methods can help in such task?

## Recent Jobs

Official Programmer's Heaven Blogs
Web Hosting | Browser and Social Games | Gadgets

Popular resources on Programmersheaven.com
Assembly | Basic | C | C# | C++ | Delphi | Flash | Java | JavaScript | Pascal | Perl | PHP | Python | Ruby | Visual Basic