## 4 D2D Group Communication Scheme with Bidirectional and InCrentental A-Star (BICA*) Routing
### Path Selection Algorithm
``` Input:\(Start\), Goal, \(S\)
1: Initialize \(U_{start}\leftarrow\varnothing\); \(U_{goal}\leftarrow\varnothing\)
2:for each node \(s\in S\)do
3:\(s_{Start}\leftarrow-\infty\); \(s_{Sgoal}\leftarrow-\infty\); \(s.rhs_{Start}\leftarrow-\infty\); \(s.rhs_{goal}\leftarrow-\infty\)
4:end
5:\(Start.rhs_{start}\gets 0\); \(Goal.rhs_{start}\gets 0\)
6:\(Start.key_{start}\leftarrow[0,0]\); \(Start.key_{goal}\leftarrow[0,0]\)
7: Insert Start into the priority queue \(U_{start}\)
8: Insert Goal into the priority queue \(U_{goal}\)
9:while true do
10:while\(\left(U_{start}.top\
eq Goal\text{\bf\ or\ }U_{goal}.top\
eq Start\right)\) or \(\left(Goal.rhs_{start}\
eq Goal.g_{start}\text{\bf\ or\ }Start.rhs_{goal}\
eq Start.g_{goal}\right)\)do
11:\(pop_{start}\leftarrow\) Pop the top node of the queue \(U_{start}\)
12:\(pop_{goal}\leftarrow\) Pop the top node of the queue \(U_{goal}\)
13:if\(pop_{start}=pop_{goal}\)then
14:break\(/\)/Rendezvous from opposite directions
15:end
16:if\(pop_{start}.g_{start}>pop_{start}.rhs_{start}\)then
17:\(pop_{start}.g_{start}\gets pop_{start}.rhs_{start}\)
18:for all node \(s^{\prime}\) which is a successor of \(pop_{start}\)do
19: Update information of node \(s^{\prime}\) by NodeInformationUpdate(\(\cdot\))
20:end
21:else
22:\(s.s_{Start}\leftarrow-\infty\)
23:for each node \(s^{\prime}\) which is a successor of \(pop_{start}\) and \(pop_{start}\) itself do
24: Update information of node \(s^{\prime}\) by NodeInformationUpdate(\(\cdot\))
25:end
26:end
27:if\(pop_{goal}.g_{goal}>pop_{goal}.rhs_{goal}\)then
28:\(pop_{goal}.g_{goal}\gets pop_{goal}.rhs_{goal}\)
29:for each node \(s^{\prime}\) which is a successor of \(pop_{stg_{start}}\)do
30: Update information of node \(s^{\prime}\) by NodeInformationUpdate(\(\cdot\))
31:end
32:else
33:\(s.g_{goal}\leftarrow-\infty\)
34:for each node \(s^{\prime}\) which is a successor of \(pop_{goal}\) and \(pop_{goal}\) itself do
35: Update information of node \(s^{\prime}\) by NodeInformationUpdate(\(\cdot\))
36:end
37:end
38:end
39:while some edge's cost has changed do
40: Update the cost of changed nodes
41: Update information of changed nodes by NodeInformationUpdate(\(\cdot\))
42:end
43:endIt is worthwhile to point out that during the process of path construction, _rhs_ and \(g\) values will be the same if there is no topology change. On the other hand, the _rhs_ value will be updated by Line 3 of Function 1 and leads to different _rhs_ and \(g\) values. A node with inconsistent _rhs_ and \(g\) values will be placed into the priority queue. Function 1 calls Function 2 for the evaluation and updating of \(key(s)=[k_{1}(s);\;k_{2}(s)]\). Here, we have two examples to illustrate the concepts of BICA*. For the sake of clarity, we assume smaller key values are preferred. Figure 8 is an example of the bidirectional search of BICA*. Figure 8 shows the commencing of the search. On the right of Figure 8, the search begins at the upper right corner and ends at the lower-left corner. On the left of Figure 8, the search begins at the lower-left corner and ends at the upper-right corner. Figure 8 shows the result of the first expansion. The upper right corner has two direct neighbors with key values [6:1] and [5:1]. The search procedure compares \(k_{1}\) first and then \(k_{2}\) to decide which node should be expanded. Therefore, it expands downward, as shown in Figure 8. Similarly, the lower-left corner expands upright. As the bidirectional search proceeds to the state in Figure 8d, on the right, two nodes are having the same \(k_{1}\) value [6:3] and [6:1]. Since the \(k_{1}\) values are the same, we expand the node with smaller \(k_{2}\) values. So, the node with the key value [6:1] is expanded in Figure 8e. After five expansions, searches from both directions converge at the circled node in Figure 8f and accomplish the bidirectional search. Figure 9 shows how BICA* helps to deal with topological change. For the sake of clarity, we consider a unidirectional search from the upper right to the lower left.