# Blockchain-Empowered Fair Computational Resource Sharing System in the D2D Network +
## 5 Problem Formulation
### Response Delay Optimization  
In our work, we emphasize the importance of low task execution time towards a requester's OoE. In each task period, there is \(n=\frac{T}{M}\) time slots, and we define the expected completion time, \(t_{i}^{exp}\), for each requester \(p_{i}\) as follows:  
\[t_{i}^{exp}=\arg\min_{t}\sum_{\tau=1}^{t}\sum_{j=1}^{(h+1)}M_{i,j,t}^{exp}\geq \gamma_{i}, \tag{16}\]  
where \(i\in\{1,2,...,p\},j\in\{1,2,...,h\},t\in\{1,2,...,\frac{T}{M}\}\). Therefore, our optimization problem becomes:  
\[ \begin{split}\text{Minimize:}&\sum_{i=1}^{p}t_{i}^{ exp}\\ \text{Subject to:}&(7)-(11)\;(13)-(16).\end{split}  \tag{17}\]  
Calculation of the optimal computation assignment matrix \(M\) is similar to the famous knapsack problem that is NP-hard [27]. Here, the computational powers of helper devices are like knapsacks with different sizes, and the computational tasks from requesters are like items with different sizes. Solving for the optimal solution for the task scheduling resembles solving for an optimal solution for the knapsack problem: it is NP-hard. For effectiveness, especially considering the trend of an increasingly massive number of smart mobile devices in D2D networks, we proposed a light-weight heuristic algorithm to efficiently find the sub-optimal solution for the computation assignment matrix \(M\) illustrated in Algorithm 1. Note that we make substantial use of the linprog function [28] in MATLAB for calculating the computation assignment matrix \(M\) by transforming \(M\) element-wise intoa one-dimensional unknown vector \(\vec{x}\) with \(p\cdot(h+1)\cdot\frac{T}{\Delta t}\) entries from elements in \(M\). According to linprog [28], \(A\), \(b\) in Algorithm 1 represent the inequality constrains for \(\vec{x}\), and \(A_{eq}\), \(b_{eq}\) represent the equality constrains for \(\vec{x}\). The function get_linprog_parameter in Algorithm 1 is transforming the constraint functions in (17) from a matrix from to a one-dimensional vector form, which is basically a simple reshaping of the matrix. There is no upper bound for \(\vec{x}\), and the lower limit for elements of \(\vec{x}\) is zero. The maximum wait time of a requester is the longest time the requester can wait before she/he needs to compute the task result herself/himself. However, it is possible that the task can be completed much sooner than the maximum wait time. Each iteration of Algorithm 1 tries to find lower feasible task assignment solutions by halving (up to an integer value) a randomly-selected requester's maximum wait time. Since the duration of each task period is limited, the maximum wait time is up to the length of a task period. Therefore, the complexity of Algorithm 1 is subject to \(ln(p)\cdot O(linprog)\) where \(p\) is the number of requesters at the task period and \(O(linprog)\) represents the complexity of MATLAB's linprog function [28]. Unfortunately, MATLAB claims improvement on efficiency of linprog over time, but releases no detail about the complexity. [PERSON] in [29] claims that his algorithm on top of linprog may achieve polynomial complexity with the best known complexity bound on linear programming problems. ```
Input: Maximum wait vector \(\vec{\phi}\) Output: Modified maximum wait vector \(\vec{\phi}\) that corresponds to a sub-optimal solution for (17)
1 functionheuristicMaxWait(\(\vec{\phi}\))
2\([A,b,A_{eq},b_{eq}]:=\) get_linprog_parameter(\(\vec{\phi}\))
3\([x,feasible]:=\) linprog(\(\vec{0}\), \(A,b,A_{eq},b_{eq},\vec{0}\))
4 iffeasiblethen
5\(\mathcal{C}:=\{1,2,...,p\}\)
6 while\(\mathcal{C}\
eq\emptyset\)do
7 forrandom \(i\in\mathcal{C}\)do
8\(i:=\vec{\phi}_{i}\)\(\vec{\phi}_{i}:=\left\lfloor\frac{\vec{x}}{2}\right\rfloor\)\([A,b,A_{eq},b_{eq}]:=\) get_linprog_parameter(\(\vec{\phi}\))\([x,feasible]:=\) linprog(\(\vec{0}\), \(A,b,A_{eq},b_{eq},\vec{0}\))
9 iffeasiblethen
10\(\vec{\phi}_{i}:=\iota\)\(\mathcal{C}:=\mathcal{C}\backslash\{i\}\)
11
12 return\(\vec{\phi}\)
```  
**Algorithm 1**The algorithm to obtain \(\vec{\phi}\), which corresponds to a sub-optimal solution for (17).