# Improving Traffic Load Distribution Fairness in Mobile Social Networks
## 3 Research Background
### Social-Based Routing Algorithms  
Social-based routing schemes typically define a utility metric for each node when making routing choices. Clearly, a higher utility reflects a higher chance of the node to deliver a message. The method forwards the message to the contacted node with a higher utility in each contact. This best next-hop heuristic forwarding \(p_{ij}^{f}\) can be described as  
\[p_{ij}^{f}=\begin{cases}1,&U_{i}<U_{j}\\ 0,&U_{i}>U_{j}\end{cases} \tag{2}\]  
Nevertheless, the utility-based routing algorithms in mobile social networks have some drawbacks as follows:  
* Hill-climbing heuristic forwarding is a pure greedy approach that sends the message to the nodes with the highest utility at each contact (hop). [PERSON] et al. (2011) used a Markov model to show that under this forwarding technique, the probability of a message reaching the greatest utility node(s) is one, implying that messages will always find the highest utility nodes in mobile social networks. Furthermore, in the following we show mathematically that the forwarding heuristic, which is biased towards higher value nodes, guides the routing algorithm to send the bulk of network traffic through the highest utility node(s) as follows. We first assume a routing strategy that determines the next-hop nodes in a random manner. The message forwarding is therefore a random walk over the graph \(G(V,E)\) mentioned above, with the transition probability matrix \(P\), where its element \(p_{ij}\) is defined in (1). Under this random forwarding, \(p_{ij}\) is equal to the inverse of node \(i\)'s degree \(d_{i}\), or \(p_{ij}=1/d_{i}\). In a steady state traffic flow, the chance to find a message \(m\) in node \(j\), which also equals to \(j\)'s traffic load, can be computed as the first eigenvector of the distribution matrix \(\Pi^{T}\), with \(\pi_{ij}=p_{ij}\cdot(\sum_{j}p_{ij})^{-1}\). Then, it is easy to see that the eigenvector for distribution matrices of networks with a non-random (heterogeneous) connectivity distribution such as mobile social networks will be skewed towards the highly connected nodes (hub nodes) under this random scheme. Eventually, this confirms the natural traffic load imbalance in the social networks. Further, if the forwarding strategy is not random, but biased towards connectivity (i.e., favouring nodes with a higher degree), the probability of hub nodes receiving relay traffic increases and the traffic load distribution becomes more unbalanced. Furthermore, using simulation in the Reality mobility scenario ([PERSON] et al., 2017) we illustrate in Figure 3 (left) the node degree vs. node traffic load when the hill-climbing heuristic forwarding is applied on the network (here, node traffic load is defined as the total relay messages carried by a node). The graphic depicts a few the highest degree nodes handle a big portion of traffic, yet most of network nodes only process a small one. This quickly depletes the hub nodes' constrained resources such as power and storage. For instance, we show in Figure 3 (right) the  
Figure 2: (**left**) the node degree distribution in the Reality mobility scenario, and (**right**) when it is plotted in a log-log scale. The almost linear of the plot of the node degree in the log-log scale verifies that the node degree is power-law distributed.  
buffer occupancy changes of illustrative hub node and non-hub node in Reality. Clearly, the buffer occupancy in the hub node is regularly saturated, whereas the buffer queue on the non-hub node is normally low during the experiment.
* In mobile social networks, node utility can change over time, and a low utility node at the present time could become a good relay in the future. Most conventional utility-based forwarding algorithms, however, often ignores this. Furthermore, the studies in [18; 19] showed that node popularity in human-based networks varies over time and has a periodic pattern. Considering this, when TraLDA calculates node popularity, these features will be taken into account.