## 4 Proposed Protocol: Probing of Devices
#### Theoretical Probing Protocol Analysis  
This section presents the probing overhead comparison of HRS, MRS-ST-BL and MRS-SD-BL. The probing overheads of each of the schemes are compared by calculating the average number of messages exchanged before user data transmission for each of them. The average probe number (\(p\)) can be used to quantify the average time taken for probing. The less the time spent for probing in a scheme, the higher the throughput can be achieved by the scheme. Figure 2 shows the exchange of messages between a source, candidate relay nodes and a destination in MRS-ST-BL and MRS-SD-BL. Similar messages are also exchanged in HRS. In all these schemes, during the D2D initiation phase, a source sends a D2D request message to a BS. The BS sends a D2D reply back to the source. During the probing phase, each candidate relay nodes are probed to learn about physical link conditions. Probing of a candidate relay node requires exchange of 4 messages: from source to relay, relay to source (for SNR value from \(s\) to \(r\)), relay to destination, destination to source (for SNR value from \(s\) to \(d\), and SNR value from \(r\) to \(d\)). HRS also requires similar message exchange while probing. Therefore, the average number of messages exchanged in MRS-ST-BL, MRS-SD-BL and HRS before D2D communication establishment are  
\[M=2+4\times p, \tag{7}\]  
which shows that the number of messages exchanged is proportional to the number of devices being probed. The graphical illustration of average number of probes for these schemes are in Section 5.3.2. Now we calculate the number of nodes probed, by first defining the node density and number of nodes in a circular region. Using width of a network \(W\) and \(n_{total}\) number of devices in the network, node density \(n_{density}\) can be calculated as  
\[n_{density}=n_{total}/W^{2}. \tag{8}\]  
Within a circular region of radius \(R\), the average number of devices that can be a relay are  
\[n_{circle}=R\times n_{total}/W^{2} \tag{9}\]  
Let \(x\) be the fraction of devices which are friends of source and \(y\) be the fraction of friend devices whose social trust values are above the social threshold. Its value can be calculated using the social distribution discussed in Section 2. In HRS, the number of devices having social trust above social threshold are  
\[n_{\text{HHS}}=x\times y\times\frac{R\times n_{total}}{W^{2}} \tag{10}\]  
which is the same as the average number of devices to be probed, \(p_{\text{HHS}}\). In MRS-ST-BL, the number of devices above the social threshold are  
\[n_{\text{MRS-ST-BL}}=x\times y\times n_{circle} \tag{11}\]Among the devices above social threshold, it will filter the devices having battery level above battery threshold (\(B_{thres}\)). Let \(z\) be the fraction of devices having battery level above \(B_{thres}\). Then the number of devices within circular region having battery level above \(B_{thres}\) are  
\[n_{\text{MRS-ST-BL}}=x\times y\times z\times n_{circle} \tag{12}\]  
At most \(l\) devices are probed in MRS-ST-BL. \(n_{\text{MRS-ST-BL}}\) devices are arranged with their social trust in descending order. Then, the average number of devices to be probed are  
\[p_{\text{MRS-ST-BL}}= \begin{cases}l&\text{if }l<n_{\text{MRS-ST-BL}};\\ n_{\text{MRS-ST-BL}}&\text{otherwise}.\end{cases}  \tag{13}\]  
In MRS-SD-BL, friends having battery level above battery threshold (\(B_{thres}\)) are initially filtered as  
\[n_{\text{MRS-SD-BL}}=x\times z\times n_{circle} \tag{14}\]  
At most \(l\) devices are probed in MRS-SD-BL. Therefore, the filtered devices are arranged according to distance from the midpoint in ascending order. At most \(l\) devices nearest to the midpoint are filtered again as  
\[n_{\text{MRS-ST-BL-problem}}= \begin{cases}l&\text{if }l<n_{\text{MRS-SD-BL}};\\ n_{\text{MRS-ST-BL}}&\text{otherwise}.\end{cases}  \tag{15}\]  
Then, the average number of devices above the social threshold is equal to average number of devices to probed in MRS-SD-BL.