Tree-Based Neighbor Discovery in Urban Vehicular Sensor Networks

Abstract

In urban vehicular sensor networks, vehicles equipped with onboard sensors monitor some area, and the result can be shared to neighbor vehicles to correct their own sensing data. However, due to the frequent change of vehicle topology compared to the wireless sensor network, it is required for a vehicle to discover neighboring vehicles. Therefore, efficient neighbor discovery algorithm should be designed for vehicular sensor networks. In this paper, two efficient tree-based neighbor discovery algorithms in vehicular sensor networks are proposed and analyzed. After suggesting detailed scenario and its system model, we show that the expected value of neighbor discovery delay has different characteristics depending on neighbor discovery algorithms. An interesting observation of our result is that M-binary tree-based neighbor discovery shows better performance than M-ary tree-based neighbor discovery in the parking lot scenario, which is a counterintuitive result. We analyze why such result appears extensively.

1. Introduction

In recent years, wireless sensor networks (WSNs) [1], especially urban vehicular sensor networks [2], have inspired research and industry interests in various applications such as traffic engineering, environment monitoring, and civic and homeland security. A typical sensor network includes hundreds to thousands of sensor nodes, each of which is equipped with various kinds of sensors. In general, sensor nodes have stronger resource constraints than nodes in typical wireless ad hoc network, for example, battery power, memory, computation capability, and communication technology. However, vehicular sensor networks have different characteristics to typical sensor network. First, there is no battery constraint. Therefore, in vehicular sensor networks, communication between vehicles with less delay is one of the most important issues, compared to typical wireless sensor networks.

Especially, since vehicular sensor networks may have no infrastructure controlling the network environment, it is required for vehicles to autoconfigure the environment for establishing a communication network. For example, if sensor-occupied vehicles arrive at the same area, each vehicle would not know which other vehicles are in its transmission range, implying that the vehicle needs to discover its neighboring vehicles. Since information obtained during the discovery process is required by many network protocols, neighbor discovery of each vehicle in the vehicular sensor network is an important configuration process.

Currently, explicit neighbor discovery may not be performed in typical ad hoc networks [3], a superset of vehicular sensor network. That is, it is assumed that all transmissions are listened to by neighboring nodes in the medium access control layer level. This assumption is not suitable for practical vehicular sensor network implementation, because when many vehicles are in the one-hop transmission range, the delay of neighbor discovery increases dramatically. In addition, the delayed result for neighbor discovery process can be outdated since the neighboring vehicles move too fast to depart the transmission range. Therefore, an efficient neighbor discovery scheme for vehicular sensor networks is required, implying that average delay minimization of neighbor discovery schemes in vehicular sensor networks is an important problem.

Recently, numerous studies on neighbor discovery for wireless networks have been proposed in the literature [4– 6]. These studies mainly focus on applications of mobile robot networks, and the IEEE 802.11 network provides robot intercommunication, which is very similar to vehicle-to-vehicle communications in vehicular sensor networks. However, these approaches cannot be applied into the vehicular sensor networks without modification, because if there are many groups of vehicles, the performance of the network may be reduced significantly due to interference and collisions. Furthermore, the network load cannot be controlled by a group of nodes in general [5].

In Santos et al. work [4], an adaptive TDMA protocol for mobile autonomous nodes is proposed. This protocol is an adaptive TDMA protocol with new self-configuration capabilities according to the current number of active group members. This protocol operates over IEEE 802.11 networks in infrastructure and adhoc mode. However, it does not support a dynamic number of nodes. The improved protocol proposed in [5] has dynamic reconfiguration of the TDMA round, which supports changes of the number of nodes. But it is not suitable to assumption, because each node in a group maintains a state machine and the whole member information of the group.

Arai et al. [6] proposed an adaptive reservation-TDMA (AR-TRMA) MAC protocol, which focuses on real-time communication among nodes in a heterogeneous environment by using a reservation mechanism. This protocol supports dynamic time slot allocation schemes during node intercommunication. Furthermore, this protocol considers the packet collision avoidance method in the joining procedure, using the battery voltage level and ID of each node. However, when a packet collision occurs, the protocol uses fixed-size minislots to resolve the collision. This scheme suffers from lack of scalability, because it may not support dynamic situations of vehicular sensor network which include a situation that a large number of nodes and groups move around frequently.

With this motivation, we have studied tree-based neighbor discovery schemes in vehicular sensor networks, which guarantee the discovery of whole neighbors in each leader vehicle. In this study, our objective is to reduce the average delay of tree-based neighbor discovery. According to our study, the delay depends on the tree construction scheme. We focus on M-ary and M-binary tree-based neighbor discovery, because these algorithms have simplicity and optimality, respectively.

In summary, our contributions are twofold. First, we apply tree algorithm variations to neighbor discovery in vehicular sensor networks. To the best of our knowledge, our study is the first work applying tree algorithms to neighbor discovery in vehicular sensor networks. Second, we show that the M-Binary tree-based scheme with optimal M and N is suitable for the neighbor discovery process.

The reminder of this paper proceeds as follows. Our model for sensor-equipped vehicles is described in Section 2. The proposed join schemes are described in Section 3. In Section 4, determining the number of groups in each neighbor discovery process is discussed, and the performance results are also shown. Our conclusion is given in Section 5.

2. System Model

First of all, we explain our system model assumptions. We assume that numerous vehicles are uniformly distributed in a working field (e.g., road), and each vehicle may move freely. Though this assumption is not suitable for some vehicle sensor network applications, many mobile sensor network applications in dense-area monitoring scenario allow this assumption. It is also assumed that the carrier sensing range is twice the transmission range.

In this model, vehicles are classified into leaders and followers. The leader vehicle (LV) is the vehicle managing and controlling a group of vehicles. The other vehicles in the group are called follower vehicles (FVs) or members of the group. A vehicle which is not a follower vehicle and can communicate with a leader vehicle in onehop is called a neighboring vehicle. Note that follower vehicles do not need to identify other vehicles except for the leader vehicle, and a leader vehicle has the number of required vehicles for performing a cooperative sensing task.

A group following a leader vehicle uses TDMA with a channel distinct from the default channel when communication among nongroup members or between a member and nonmember is required. Because the TDMA frame structure guarantees a delay bound and transmission opportunities, each member of the group has a chance to transmit its packet fairly. Figure 1 shows an example of a TDMA frame.

Figure 1

An example of TDMA frame structure.

Each of the TDMA frames has several periods: beacon period, joining period, request/leave period, control period, and data period. LV notifies the beginning of a frame by beacon message broadcasting in a beacon period. Acknowledgment of the previous frame is also contained in the beacon message. In a joining period, LV requests its neighbor vehicles to join the group under the number of required vehicles via the proposed schemes. Note that neighboring vehicles which are already joined as follower vehicles do not participate in the joining period. In Figure 1, vehicle A is the follower vehicle which participated in the joining period before, and vehicles B and C are neighboring vehicles which are identified as follower vehicles after the joining period. After joining period, each follower vehicle can request a chance of data transmission or notify the leave itself in request/leave period. LV broadcasts a control message containing the follower vehicles data period schedules during the control period, and each of the follower vehicles can send its own data according to the schedule. This TDMA frame structure can be modified or redesigned given the application scenario and the system requirements.

In this system model, neighbor discovery is performed in the joining period. Depending on the neighbor discovery scheme, the time interval of the joining period may be variable, which causes a significant delay. Therefore, a joining scheme to minimize the total expected delay in the period is required. In this paper, it is called the delay-minimized neighbor discovery (DMND), and in the next section, two tree-based DMNDs are discussed.

Generally, the number of neighboring vehicles of LV affects the performance of DMND in our model. Therefore, LV may estimate and use this information to improve the performance. When LV has no follower vehicles, one of the easiest estimation techniques is to use the field size, the transmission range, and the total number of vehicles in the uniformly distributed working field

$\begin{array}{c}{N}_{\text{Neighbor}}=\lfloor \frac{N_{\text{Tot}}\cdot \left(\pi {\rho }_{\text{TX}}^2\right)}{S_{\text{Field}}}\rfloor \end{array},$

(1)

where ${\rho }_{\text{TX}}$ is the transmission range of LV, $N_{\text{Tot}}$ is the total number of vehicles in the working field, and $S_{\text{Field}}$ is the area of the field.

The other method that can be applied to estimate $N_{\text{Neighbor}}$ is found in [7], and this can be utilized via the default channel. But further discussion on the estimation method is not considered in this paper.

3. Tree-Based DMNDs

We mainly focus on minimization of the expected delay in order to identify a required number of vehicles from a greater number of neighbor vehicles. The two kinds of tree-based DMNDs proposed are based on various splitting methods. The first one applies M-ary tree splitting for grouping collided vehicles, while the second one combines M-ary and binary tree splitting methods to improve the associated delay performance. The latter requires an algorithm to decide the value of M affecting the performance of the method, and we will derive the optimal $M(M^{*})$ which minimizes the average of total delay. Some notations for the description of the proposed DMNDs are as follows. M is used to denote the number of children nodes (branches) in a tree diagram, and N and k are the numbers of neighbor and required vehicles, respectively.

3.1. M-Ary Tree-Based DMND (MT-DMND)

In M-ary tree-based DMND, after LV sends a query, which includes the state information of the previous slot, each neighboring vehicle determines its joining operation using this information. If the state of the previous slot is “C (collision slot),” each of the vehicles which sent an ACK in the slot randomly chooses an integer in the interval $[0,M-1]$ and concatenates the number onto the end of its ID. Then, if its new ID satisfies the requirements of LV, which is included in the query, the vehicle sends an ACK with its new ID. In case that the state is “S (success slot),” the vehicle which sent an ACK with its ID in the previous slot recognizes itself as a follower vehicle of LV. Each of the other neighboring vehicles that did not send an ACK do send one if its ID satisfies the requirements of LV. If the state is “I (Idle slot)” and the ID of a neighboring vehicle satisfies the requirements of LV, the vehicle sends an ACK with its ID.

On the other hand, in M-ary tree-based DMND, the operation of LV is as follows. First, at the beginning slot of a joining period, LV sends a query requesting an anonymous ID. Then LV waits for a time slot to receive an ACK and recognize the state of the time slot. Based on the state, LV sends another query and waits for a time slot. This procedure repeats until LV identifies k follower vehicles. The policy that LV queries the IDs of neighboring vehicles in the procedure is conceptually similar to “depth-first-search (DFS)” algorithm. When LV recognizes that the state of the previous slot is “C,” it concatenates 0 to $M-1$ to the respective queried ID and stacks M IDs into the candidate list. Then it pops an element of the list and sends a query with the element. When the state of the previous slot is “S,” it identifies the vehicle which sent the ACK in the previous slot as a follower vehicle. Then it pops an element of the list, and sends a query. When the state of the previous slot is “I,” it only pops an element of the list and sends a query. Therefore, LV can construct an M-ary tree by the result of M-ary tree-based DMND, as shown in Figure 2.

Figure 2

The M-ary tree-based DMND (when $M=3$ ).

3.2. M-Binary Tree-Based DMND (M-BT-DMND)

M-binary tree-based DMND is a modification of M-ary tree-based DMND designed to reduce excessive collisions and idle slots. It is based on M-binary tree construction, just as 2-ary tree-based DMND is based on M-ary tree construction. An M-binary tree is a tree that each node has at most 2 nodes, except that the root node has at most M nodes. Therefore, LV and its neighboring vehicles choose either 0 or 1 for concatenation, except when LV sends a query with an anonymous ID. After LV sends a query with an anonymous ID and a collision slot has occurred, LV and its neighboring vehicles choose an integer in the interval $[0,M-1]$ . Figure 3 shows a typical example of M-binary tree-based DMND. Note that there is no node with only one child, because the “S” and “I” nodes have no children and the “C” node always has 2 or more children. Though further improvement of this scheme can be achieved based on this observation, we do not consider it further due to the complexity of the analysis.

Figure 3

The M-binary tree-based DMND (when $M=5$ ).

4. Simulation Results

4.1. Simulation Environments

Some simulation experiments were performed to compare DMNDs. To validate each simulation result, we use the values of the IEEE 802.11 FHSS system parameters listed in Table 1 as in [8]. Note that Short Interframe Space (SIFS) is a fixed-size time period between frame transmission used for IEEE 802.11 nodes to detect the correct channel idle. As comparison targets, p-persistent DMNDs [9] with or without query are also simulated. Note that p is optimally chosen by the simulation with the precision of 0.001. We performed 1000 trials for each scheme, and the delay results are averaged over each scheme for the given (fixed) parameters. In addition, when we use query in a DMND, since success/collision slot needs one query (with 2-bit payloads for 3 slot types), 2 SIFSs, and 1 ACK message (with 32-bit ID), it takes about 532 μs, while the idle slot that includes one query and one $aSlotTime$ takes 388 μs. It implies that the ratio of the collision slot time to idle slot time equals to 1.371. We denote this ratio to α. α is one of the most important factors in this simulation result, because α determines the overhead ratio in DMNDs. On the other hand, when we do not use query in a DMND, we use $aSlotTime$ for the idle slot and 495 μs for the success/collision solt, according to [9].

Table 1

FHSS System Attributes (Parameters) and Additional Parameters Used to Obtain Numerical Results.

Parameters	Default value
$aSlotTime$	50 μs
DIFS (DCF Interframe Space)	128 μs
SIFS (Short Interframe Space)	28 μs
MAC Header	272 bits
PHY Header	128 bits
Management frame (w/o payload)	28 bytes
ACK frame	14 bytes
MAC Header	272 bits
MAC Header	272 bits

4.2. Optimal Value of M.

As mentioned, each of our DMNDs has triple parameters $(M,N,k)$ . However, since N is given within the joining period of a frame and k is determined by the task given to LV and the number of follower vehicles identified by LV, M is a tunable parameter in many cases. Therefore, consideration should be given to finding the optimal value of M to minimize the total average delay. Figures 4– 7 show the average total delay in case of M-ary and M-binary tree-based DMND with fixed N and k, respectively.

Figure 4

Total average delay of M-ary tree-based DMND (MT-DMND) with fixed k ( $k=25$ ).

Figure 5

Total average delay of M-ary tree-based DMND (MT-DMND) with fixed N ( $N=60$ ).

Figure 6

Total average delay of M-binary tree-based DMND (M-BT-DMND) with fixed k ( $k=25$ ).

Figure 7

Total average delay of M-Binary tree-based DMND (M-BT-DMND) with fixed N ( $N=60$ ).

Figure 4 shows the delay of MT-DMND for M and N, where the number of required vehicles for a task, k, is fixed to 25. For a given task and value of M, as shown in the figure, the number of neighboring vehicles does not affect the delay. This result is quite different to the depth-first-search (DFS) of M-ary tree. In DFS problem, each node has a distinct key and when a key is given, the objective of this problem is to search the node with the same key. It is popular for DFS to have a time complexity of $O(|N|+|E|)$ where $|N|$ is the number of nodes in the tree and $|E|$ is the number of edges. Therefore, the total delay of DFS can be considered as a linear function of $|N|+|E|$ .

However, in case of MT-DMND, the total delay can be calculated approximately. It is not a linear function of $|N|+|E|$ though the procedure is similar to that of DFS. Given N neighboring vehicles, suppose that LV should identify k follower vehicles with MT-DMND. The total delay of the procedure is denoted by $d_M(N,k)$ . We cover only the case that $N\gg k>1$ . In this case, root node is a collision node when this fact is recognized, each vehicle concatenates a random integer $[0,M-1]$ uniformly to its ID. Assuming a uniform random distribution of integers, M subtrees of the root node have almost the same number of nodes. Then, the following equation is approximately satisfied:

$\begin{array}{c}{d}_M(N,k)\approx d_{\text{Coll}}+d\left(\frac{N}{M},k\right)\end{array},$

(2)

where $d_{\text{Coll}}$ is the collision delay in the root node.

Because (2) is a recursion formula, we find a number r such that $N/M^r=k\mathrm{\hspace{0.17em}\hspace{0.17em}}(r\ge 1)$ ,

$\begin{array}{cc}\hfill d_M(N,k)& \approx r\times d_{\text{Coll}}+d_M(k,k)\hfill \\ \hfill & ={\log }_M\left(\frac{N}{k}\right)\times d_{\text{Coll}}+d_M\left(k,k\right),\hfill \end{array}$

(3)

where $d_M(k,k)$ is the total delay of the procedure given k neighboring vehicles and k required follower vehicles.

In this context, for a considerably large $k,\mathrm{\hspace{0.17em}\hspace{0.17em}}{\log \hspace{0.17em}}_M(N/k)$ can be ignored. Therefore, in this case, N has little effect on the total delay of MT-DMND. This is unique characteristic of MT-DMND, which identifies only a fraction of all neighboring vehicles. We can conclude that in MT-DMND, when we choose the value of M, the characteristic of the task is more important than the number of neighboring vehicles.

On the other hand, for a given task (i.e., fixed k), the value of M has a considerable effect on the total delay, as shown in Figure 4. The explanation for this has already been described in the previous section: the number of idle and collision slots is important. If M increases, the number of collision slots decreases. But, if M is very large, the number of idle slots is so large that the delay increases. Therefore, we can determine the optimal value of M by considering the trade-off between the number of collision and idle slots. In the figure, the optimal value of M is 3, since we assume that the value of α in our protocol is 1.371. Note that a different α may lead to a different optimal value of M. Furthermore, it is observed in the figure that when M increases, the effect of the number of idle slots on the total delay is approximately linear.

Figure 5 shows the total average delay of MT-DMND for M and k when the number of neighboring vehicles N is fixed to 60. In this figure, the total delay increases linearly when the number of required vehicles k increases. It shows that if k increases, the respective number of collision and idle slots increases linearly. Especially, the slope of the delay for k is the minimum value in case that M is equal to 3, implying that the optimal value of M is not changed, even though the value of k is changed. Therefore, in M-ary tree-based DMND, the calculation of optimal value of M to minimize delay does not depend on N or k, but depends on the given MAC protocol parameters such as α.

Figures 6 and 7 show the total average delay of M-BT-DMND when k is fixed to 25 and N is fixed to 60, respectively. A comparison of Figures 4 and 6 shows that the number of neighboring vehicles N has a considerable effect on the optimal value of M in M-BT-DMND, compared to the case of MT-DMND. Furthermore, in many cases, M-BT-DMND has a smaller delay than MT-DMND. Therefore, this characteristic is a motivation of $M^{*}$ -binary tree-based DMND, which is a dynamic version of M-binary tree-based DMND. In the next section, the details of the scheme are discussed.

4.3. Performance Comparison

In this section, we compare DMNDs. First, Figure 8 shows (N is fixed to 60) the average total delay for k, where $M=4$ and $M=8$ . In this figure, when M is 8, M-BT-DMND has a smaller delay than MT-DMND, but when M is 4, MT-DMND has a smaller delay than M-BT-DMND. This shows that choosing a suitable value of M has a considerable effect on the performance of each scheme. Especially, it justifies the calculation of optimal value of M.

Figure 8

Performance comparison of MT-DMND and M-BT-DMND with $M=\mathrm{4,8}$ .

Figure 9 shows the average total delay for N with fixed $k\mathrm{\hspace{0.17em}\hspace{0.17em}}(k=25)$ when each of 3T-DMND, 32-BT-DMND, 64-BT-DMND, $M^{*}$ -BT-DMND, p-persistent DMND with query, and p-persistent DMND without query is performed, respectively. $M^{*}$ -BT-DMND is a dynamic scheme for N that selects the optimal value of M. However, in this simulation, the range of M is given to $\{2,2^2,2^3,\dots ,2^{12}\}$ to reduce its complexity. As shown in this figure, the delay of $M^{*}$ T-DMND (i.e., 3T-DMND) is generally longer than that of $M^{*}$ -BT-DMND, and the performance of p-persistent DMND with or without query is worse than tree-based DMNDs. That is, though p is optimally selected, tree-based schemes can show better performance, depending on the system parameters. Furthermore, as we discussed, the optimal value of M in M-BT-DMND depends on N. Therefore, we can conclude that the performance of MT-DMND is stable, while that of M-BT-DMND is dynamic with respect to N. That is if the estimation of $N_{\text{Neighbor}}$ is correct, $M^{*}$ -BT-DMND is more effective than other DMNDs, because it has a smaller delay. But, if the estimation error of $N_{\text{Neighbor}}$ is large, MT-DMND may have better performance.

Figure 9

Performance comparison of DMNDs with $k=25$ .

Figure 10 shows the average total delay for k with fixed $N\mathrm{\hspace{0.17em}\hspace{0.17em}}(N=15)$ when each of 3T-DMND, 16-BT-DMND, 32-BT-DMND, 64-BT-DMND, p-persistent DMND with query, and p-persistent DMND without query is performed, respectively. As shown in this figure, when M is similar to N, M-BT-DMND has better performance. However, p-persistent DMND with query may have better performance, when N and k are very small (e.g., $k=5$ ). It is similar to the result in [9]. Note that p-persistent DMND without query has the worst performance generally, in both Figure 9 and Figure 10. It is because p-persistent DMND without query experiences too many collision, though p is optimally selected.

Figure 10

Performance comparison of DMNDs with $N=15$ .

5. Conclusion

We have discussed the joining scheme of the TDMA MAC protocol for vehicular sensor networks. This paper proposed two joining schemes for minimizing the total delay of the joining period: MT-DMND and M-BT-DMND. Based on analyses of the proposed DMNDs and p-persistent DMNDs, we found that MT-DMND has better performance when M is fixed to 3 among MT-DMNDs, while in M-BT-DMND, the optimal value of M depends on the number of neighboring vehicles, N. Furthermore, when we choose M optimally, M-BT-DMND has the best performance than MT-DMND and p-persistent DMNDs. Therefore, when it is hard to estimate the number of neighbors and stability is important, MT-DMND is suitable, while for a small estimation error when quick joining is required, M-BT-DMND with dynamic M calculation is suitable. As a future work, we will study and analyze a scheme to solve the problem that arises from the estimation error.