We have n clients and k-base stations, say each client has to be connected to a base station that is located at a distance say 'r'. now the base stations doesn't have allocation for more than L clients.

To begin, let us produce a network which consists of edges and vertex

Network (N) = (V,E)

where V = [S, cl-l, - - - - cl-n, bs-l - - - - - - bs-k, t]

given that cl-l, - - - - - cl-n represents nodes for the clients

also we have that bs-l, - - - - - bs-k represents the nodes for base station

Also

E = [ (s, cl-i), (cl-i,bs-j), (bs-j,t)]

(s, cl-i) = have capacity for all cl-i (clients)

(cl-i,bs-j) = have capacity for all cl-i clients & bs-j (stations)

⇒ using Fond Fulkorson algorithm we find the max flow in N

⇒ connecting cl-i clients to bs-j stations

like (cl-i, bs-j) = 1

if f(cl-i, bs-j) = 0

⇒ say any connection were to produce a valid flow, then

if cl-i (clients) connected f(s,cl-i) = 1 (o otherwise)

if cl-i (clients) connected to bs-j(stations) f(cl-i,bs-j) = 1 (o otherwise)

f(bs-j,t) = no of clients (cl-i) connected to bs-j

⇒ on each node, the max flow value (f) is longer than the no of clients that can be connected.

⇒ create the connection between the client and base station i.e. cl-l to base bs-j iff f(cl-i, bs-j) = 1

⇒ when considering the capacity, we see that any client cannot directly connect to the base stations, and also the base stations cannot handle more than L clients, that is because the load allocated to the base statsion is L.

from this, we say f is the max no of clients (cl-i) that can be connected if we find the max flow, we can thus connect the client to the base stations easily.

cheers i hope this helps

5 0

3 years ago