How to find a point in 3d space for the placement of main node quickly so that it minimized the distance between the other randomly placed points connected to the node in star connection?
I am asking this question with respect to wireless sensor networks where you need to place the main node so that the distance between all other random nodes is minimized and the longevity of the network is improved.
If I randomly choose a point and try to minimize the distance from all other nodes then I may end up with large search space.Is there any better algorithm that can give me the right points quickly.
Can I use Dijkstra algorithm in this case and if yes how?
I would say with Interpolation techniques, but it might work or can be applied in this context? Just a guess that could make you think on that!
Cheers.
I think you could use a genetic algorithm to minimize the sum of the distances between the main node and all the other nodes. It is very simple to implement in any language.
You can quickly test if it works with your problem with Mathematica, which implements Differential Evolution (http://mathworld.wolfram.com/DifferentialEvolution.html) in its NMinimize[] command.It works fine and it is reasonably fast.
Also Matlab has an external package (http://it.mathworks.com/matlabcentral/fileexchange/18593-differential-evolution) that implements DE, but I have never used it.
One interesting aspect is that you say 3-d. If you are measuring distance by say euclidean we have min SUM_ j [(X-xj)^2 + (Y-yj)^2 + (Z-zj)^2 ] ^0.5 .....
where P= (X,Y,Z) the desired "one - median" and (xj,y,j,zj) are the coordinates of the jth random point
you can weight the points, and of course you can use other metrics
this is a variant on the Weber problem. the first order conditions give a set of simultaneous equations that can be solved iteratively (Weiszfeld Procedure). ... see Love Morris and Wesolowsky and other texts for a strong algorithm
one implementation idea -- if you simply want to know if P_1 or P_2 is better you can save yourself the "square root" , as the distance ordering is invariant under that operator
I'd be interested to know the size of the data, and if you get this to work, add some follow up here.
Since you are considering a star network where all random nodes will have a connection to the node of interest, then placing the node at the centroid of the set of random nodes will minimize the distance between itself and all other nodes.
The centroid minimizes the the sum of SQUARED distances. The Weber (one-median) minimizes the sum of distances. The centroid is certainly a good easy-to-calculate starting point for the later, but it does not solve the first order necessary conditions for a minimum of the distance problem. The Weber problem problem is convex and a good candidate for the Weiszfeld iterative procedure. A little care is also needed in case the P = (X,Y,Z) comes close to coinciding with an existing random point. I'd be happy to send the math if you like...
It is better if you can obtain the theoretical mean-optimum-location , then optimize your actual placement in concentric search strips centred at the theoretical mean-optimum-location.
Example, if you have a homogeneous realization of a Poison point process inside a sphere, accordingly the the mean-optimum-location is the centre of that sphere. So you can do the following:
1- Place your (Sink) in the centre of the sphere -> calculate the "total cost"
2- Search for the best location in the concentric spherical-shells of thickens Delta_R -> record the cost of each location.
3- stop after a certain number of iterations or when your "total cost" becomes progressively increasing.
4- Obtain the sink point that corresponds to the minimum cost
IMHO two cents worth of conjecture.I recall long back a Russian Mir publication that stated for setting a machine with many variables the fastest way was to pick a random set and test the cost function. Something along these lines is used in design of experiments.Perhaps this purely random process may be fastest at least statistically.
Cheers
(With apologies for the symbols....)
Let di be the straight line distance between pi and Q. pi = (xi,yi,zi), and Q = (X,Y,Z).
di = SQRT( ((X - xi)^2 + e) + ((Y - yi)^2 + e) + ((Z - zi)^2 + e) )
which is the euclidean distance from the single facility location Q to the fixed demand location pi, and the small constant e is introduced if necessary to ensure continuity in the δ(di)/δX derivatives. [The small constant e prevents the denominator of the following expressions from going to zero even if Q coincides with any pi.]
By hypothesis, Q is the solution to the problem MIN T = Σi wi di. Therefore, Q satisfies the following conditions: δT/δX = 0, δT/δY = 0, δT/δZ = 0. (The weights can be = 1 w.l.g.)
Σi wi ((X - xi)/di) = 0 (1)
Σi wi ((Y - yi)/di) = 0 (2)
Σi wi ((Z - zi)/di) = 0 (3)
In the usual location model, Q is unknown, and therefore equations (1) (2) and (3) have to be solved by an iterative scheme, as discussed in Love, Morris and Wesolowsky (1988, 14-15). In essence (X, Y, Z ) cannot be isolated in equations (1) (2) and (3) because of the dependence of di on the location of the facility.... So a simple scheme is to iterate from a first guess of Q and improve until (1) - (3) are satisfied.
If the distance is Euclidean, this problem is classical and well-known.
If the main node does not need to belong to the random nodes, then it is the "spatial median" of the points, which is solved by Weiszfeld's algorithm.
If the main node needs to belong to the random nodes, then the main node is called "central feature" (in GIS terminology). It can be obtained by simply using clustering and triangle inequality to give an upper bound of the minimum sum of distances repeatedly to eliminate the impossible candidates.
- Badges
- Science topic