TELE8083 IOT Networks
Questions:
Your task is to design a routing scheme for the IoT network depicted in and determine what the appropriate transmit probabilities should be on each link in the network. There are seven links in the network labeled `1, `2, . . . `7 which will sometimes be referred to below by the link labels, and sometimes by node numbers. For example, link `1 can also be referred to as link (1, 2) since it is the link from node 1 to node 2. The set of links is denoted by L. There are six nodes in the network,labeled 1, 2, . . . 6.
Time is slotted, and each node can transmit packets independently on outgoing links. Random access is used, so each node makes a random decision to transmit a packet on an outgoing link, independently in each slot, and independently of decisions made by other nodes (the transmission process is completely decentralized). The probability a node uses on a given outgoing link is fixed, but to be determined by you, in order to meet certain long-run rate targets for different flows.
A packet transmission can fail in two different ways. One way is if the receiver node (the node on the receiving end of the link) is transmitting at the same time. If the receiver node is transmitting, it cannot be receiving, so the transmission will fail. The other way is by a collision. A collision occurs when two packet transmissions occur on two different links that share the same receiver. So,
for example, if nodes 2 and 3 transmit to node 4 in the same time-slot, their transmissions will collide at node 4, and hence fail. However, packets transmitted on links `2 and `3 can go at the same time without colliding, since the receiver nodes are different in that case. destination
4 6
1 0.16 0.18
source 2 0 0.07
3 0 0.09
The traffic demand between the nodes is given in Table 1. Fi,j is the flow rate in packets/slot that is to be delivered from node i to node j (if possible). From the table, F1,4 = 0.16, F1,6 = 0.18, F2,6 = 0.07, F3,6 = 0.09, and the rest of the flow rates between other pairs of nodes are zero, and not in the table.The topology of the network implies that the traffic can be routed in different ways. For example, the flow from 1 to 4 could be routed via links `1 and `3, or by links `2 and `4. The flow from node 1 to node 6 could be routed via links `2, `5, `7, or links `2, `4, `6, or links `1, `3, `6. You need to decide the routing, but a flow must go via one route, not be split over multiple routes. For the flow from 1 to 4, for example, which might be routed via node 3, a packet is first sent by random access on link `2 to node 3, and, once successfully received at 3, it is then sent on link `4, again by random access, to node 4.
Depending on your routing choice, a number of flows may share the same link. The traffic demand matrix, and your routing decisions, will determine the overall rate of successful transmissions per slot needed on a given link (typically a number much less than 1). The needed flow rate on a link `, f` packets/slot, is given by the sum of the rates of each flow that shares the link `. These values will depend on how you route the traffic.
To obtain a flow rate of f` on link ` you will need to determine the packet attempt rate q` on link `.To do this, you will also need to determine the packet success probability p` on link `. The packet success probability, the packet attempt rate, and the flow rate on link ` are related by the equation:f` = q` ∗ p` (1) The packet success probability on a link, depends on the probability that the receiver node is busy transmitting, and the probability of a collision. The node transmission probability at a node i is given where the sum is over all links (i, j) that originate at node i. The success probability on a link (i, j) is given by
p(i,j) = (1 − Qj ) ∏
k : (k, j) ∈ L
k 6 = i
(1 − Qk) (3)
This equation can be explained by noting that 1 − Qj is the probability that the receiver node j is not busy transmitting, and the other product term is the probability that all the other links that have node j as a receiver are not actively transmitting a packet to node j in the same time-slot. You will note that equations (1)-(3) depend on each other. Together, they form a set of fixed point equations to solve for p and q. If we assume that f is given (it will itself depend on routing decisions that you choose) then one way to solve for p and q is to solve the equations iteratively. Starting with p` = 1 for all links `, you can solve (1) for qi,j for each link (i, j). Then you can obtain Qis from equation (2) and a new set of p(i,j) values from (3). If you keep iterating this calculation (using, for example, Matlab) then the sequence of p`s will decrease, and the sequence of q`s will increase. If they converge to a limit it will solve the equations above.
If the traffic demands are too high, or if your routing choices are suboptimal, the sequences might not converge to valid probabilities. This occurs when any of the the Qi values increases above 1. Otherwise, it will coverge to a set of q` probabilities that will meet the flow rate targets.
Your task in this project is to determine if the flow rates given in Table 1 are achievable or not. If they are achievable, determine a routing of packets for each flow that enables these flow rates to be achieved, and give the corresponding values for p` and q` for each link ` in the network, and also give the Qn values for each node n in the network. If the rates are not achievable, explain how you came to that conclusion. Please submit all your reasoning as well as the answers. If you have written code,please submit the code also.
