Sage Journals: Discover world-class research

Abstract

In the cluster-based vehicular cyber-physical systems, the member cardinality is an important parameter for the cluster maintaining and updating. Also, it is widely utilized in the design of protocols for routing, medium access, activation scheduling, and topology control. However, the delay of the traditional member cardinality evaluation method is too large to satisfy the requirement of the high-dynamic vehicular cyber-physical systems. To tackle this problem, in this article, we propose a new member cardinality evaluation method that is based on the time slot occupation technique. The new method can improve the evaluation efficiency and obtain a high evaluation accuracy. Besides, we extend the method to further improve the performance. Finally, we analyze the proposed method considering the unreliability of the channel state. The mathematical analysis and simulation results demonstrate the performance of the proposed method.

Keywords

Vehicular cyber-physical systems member cardinality evaluation time slot occupation

Introduction and motivation

Vehicular cyber-physical systems (VCPS) have attracted considerable attention in the past few decades. They hold great potential in enhancing vehicle safety and can improve the traffic efficiency.^1,2 Clustering is the basic technique to implement the cooperative communication and computing in VCPS.³ Cluster head (CH) and cluster member (CM) are the two kinds of vehicle nodes in the cluster-based VCPS. The CH serves as the local coordinator for the CMs associated with it. The number of CMs in a cluster is denoted as the member cardinality. It is an important parameter for the cluster maintaining and updating. Also, in VCPS, it has been widely utilized in the design of protocols for routing, medium access, activation scheduling, and topology control.⁴^–⁶

In this article, we study the member cardinality evaluation method. Evaluating the member cardinality means we make a judgment on whether the member cardinality is larger or smaller than a given threshold. When vehicles move through an intersection or a fork such as the scene depicted in Figure 1, due to the different driving directions of vehicles, a larger change of member cardinality tends to arise. In order to help adjusting the communication and computing protocols in time, we need to evaluate the member cardinality as soon as possible. The traditional member cardinality evaluation method is based on checking the member list of the CH itself. The delay is more than 2 s which we will explain in section “System description and basic principle.” Since 2 s is too long for the high-dynamic VCPS, we need a more efficient evaluation method.

Figure 1.

Member cardinality change in the cluster-based VCPS.

To tackle this problem, in our previous conference paper,⁷ we proposed a time slot occupation-based member cardinality evaluation method. This article is an extended version of the conference paper. In this article, we further improve the member cardinality evaluation method using an adaptive time slot occupation technology. It is specifically designed for the cluster-based VCPS. By choosing suitable parameters for the proposed method, the CH can evaluate the member cardinality more efficiently and accurately.

Our contributions can be summarized as follows:

We analyze the validity and accuracy of the proposed method and show how to minimize the evaluation time by selecting appropriate parameters.

We propose an adaptive evaluation method which can further reduce the evaluation time and improve the evaluation accuracy.

We analyze the effects of the channel state for the proposed member cardinality evaluation methods.

The rest of this article is organized as follows. In section “Related work,” we summarize the related work. In section “System description and basic principle,” we present the system model and introduce the basic principles of the member change verification method. In section “Parameters determining method,” we describe the detailed method of how to determine reasonable parameters. In section “Adaptive member cardinality evaluation,” we present an adaptive evaluation method to further improve the performance of our method. In section “Considering the channel state,” we analyze the effects of the unreliability of the channel state. We evaluate the performance of our evaluation methods in section “Performance evaluation.” The conclusion is finalized in section “Conclusion.”

Related work

Several methods about member cardinality evaluation have been proposed in the past years. Most of these methods calculate the exact size of the member cardinality and compare it with the threshold to finish the evaluation process. Artimy⁸ propose a method that depends on mobility of pattern vehicles to calculate the vehicle cardinality. This method is based on the intuition that if the traffic is dense, the vehicle tends to stop with a great probability. Shirani et al.⁹ put forward a novel velocity-aware cardinality calculation method. It only uses the own velocity of a vehicle and its acceleration pattern. Umer et al.¹⁰ calculate the cardinality based on the fluid dynamic model considering the effect of road conditions. However, these traffic flow model–based methods that use their own vehicle information, such as speed, direction, or acceleration, always have a poor accuracy and cannot constrain their verification range in a cluster. They are not suitable for the cluster-based VCPS. Some other researches do the member cardinality calculation using the wireless communication technology. Panichpapiboon and Pattara-atikom^11,12 put forward a calculation method based on the communication hop counts in the vicinity of the probe vehicle. They estimate the vehicle density according to the number of vehicles in the vicinity of the probe vehicle. In Mao and Mao,¹³ based on a rigorous analysis of the joint distribution of the number of vehicles in each hop, a maximum likelihood estimator of the traffic density can be obtained. In Mertens et al.,¹⁴ a beacon-based vehicle cardinality calculation approach is proposed. By checking the neighbor list, the cardinality can be achieved. Rawat et al.¹⁵ propose an approach based on the quantity of collided packets. The intuition behind this approach is that when the traffic is more dense, the packet collision occurs more frequently. All these proposed methods can calculate the cardinality in a cluster. However, just like the traditional method, they all cannot satisfy the requirement of time efficiency in dynamic environments of VCPS.

System description and basic principle

In this article, we consider the cluster-based VCPS that all the communication between vehicle nodes follow IEEE 802.11p standard. The communication range of one node is 250–500 m, which is also the range of a cluster. In this article, we consider the classical vehicle cluster scene that there is only one CH in a cluster, and the member cardinality is 1–1000 within the cluster range.

When the member cardinality has a big change, the member cardinality needs to be evaluated as soon as possible. We define the threshold of the member cardinality as $M_{T}$ . The actual member cardinality is defined as $M_{a}$ . We introduce the traditional evaluation method as follows. In one cluster, CMs are required to transmit periodic HELLO beacons to indicate their identifications and present statuses to the CH. The period is defined as $T_{p}$ . The CH establishes and updates its member list based on these HELLO beacons. If one CM is currently in the member list of the CH, the CH does not receive the HELLO beacon from the CM after the period $T_{p}$ , considering the situation such as signal loss, the CH continues waiting for the next two periods instead of removing the CM from the member list immediately. After the next two periods, the CH still does not receive the HELLO beacon and then the CH judges that the CM has left the cluster and removes it from the member list. By checking the member list, the CH can evaluate the member cardinality. When the cardinality change is large, the period time will be even longer to reduce HELLO beacons overhead. The delay of the member cardinality evaluation is >2 s.

Different from the traditional method, we initiate the time slot occupation method to evaluate the member cardinality. Our time slot occupation method is depicted in Figure 2. At the beginning of the evaluation, the CH initiates the evaluation process by broadcasting a start signal on a dedicated control channel. This start signal contains the occupation probability p, the number of following time slots f, and some time synchronization messages. Then, the CH changes the work state to observe the channel. We define the time that the CH completes the initiation steps is $T_{1}$ . $T_{1}$ is <200 µs considering the transmission and reception status switch time of the CH and CMs. After receiving the start signal, CMs begin to participate in time slot occupation. They send tone signals on the physical layer. In each of the f slots, each CM sends a tone signal with probability p. The transmission of a tone signal does not need to include source coding nor channel coding nor any error correction. Tone signals from different CMs can superimpose on the channel. The duration of one time slot is 13 µs in 802.11p considering the channel delay.¹⁶ After f time slots, the CH finishes the member cardinality evaluation process. We define the time required to finish the f slots as $T_{2}$ . The duration of the whole evaluation process is defined as T. We have $T = T_{1} + T_{2}$ . From Figure 2, we can see that two kinds of time slots are observed by CH after the evaluation process:

Empty time slot (no CM transmits tone signal in this time slot);

Non-empty time slot (one or more CMs transmit tone signal in this time slot).

Figure 2.

The time slot occupation method.

Using the time slot occupation method, we convert the member cardinality evaluating into the counting of empty or non-empty time slots. Let $N_{0}$ denotes the total number of empty slots and $N_{c}$ denotes the total number of non-empty slots. The basic principle of our member cardinality evaluation is presented in Algorithm 1. $τ$ is a threshold about the number of empty slots which we discuss later. The core problem of the time slot occupation method is how to determine reasonable parameters. More details of the evaluation process and the parameters determining method are explained in the following sections.

Algorithm 1: Member cardinality evaluation in the cluster-based VCPS $(f, p, τ)$
1: CH broadcasts f, p, and time synchronization messages, then switches to observe the channel;
2: Each CM sends a tone signal with probability p in each of the time slots;
3: CH counts the number of empty time slots $N_{0}$ or the number of non-empty slots $N_{c}$ ;
4: if $N_{0} < τ$ or $N_{c} > f - τ$ then
5: CH judges that $M_{a} < M_{T}$ ;
6: else
7: CH judges that $M_{a} \geq M_{T}$ ;
8: end if

Parameters determining method

The empty slots and non-empty slots

There are two key parameters in the proposed member cardinality evaluation method: the occupation probability p to decide whether to send a tone signal or not in a slot for CMs and the number f to define how many time slots are used to make this evaluation. For the cluster-based VCPS, we need to choose f as small as possible to decrease the evaluation time. We use a variable $X_{i}$ to denote the state of slot i. In other words, $X_{i} = 1$ if no tone signal in slot i and $X_{i} = 0$ otherwise. With $M_{a}$ , the probability that one slot is empty is

P r [X_{i} = 1] = {(1 - p)}^{M_{a}}

(1)

The probability that one slot is not empty is

\Pr [X_{i} = 0] = 1 - {(1 - p)}^{M_{a}}

(2)

Then, we have

E [N_{0}] = f {(1 - p)}^{M_{a}}

(3)

E [N_{c}] = f {(1 - (1 - p))}^{M_{a}}

(4)

For a given p and f, $E [N_{0}]$ and $E [N_{c}]$ are both monotonic with respect to $M_{a}$ . From a purely mathematical viewpoint, we just need to consider one of these two slot types. In this article, for simplicity in calculating, we choose the empty slots to make further study.

The validity of the member cardinality evaluation

In this section, we consider the validity of the member cardinality evaluation. $E [N_{0}]$ is a monotonically decreasing function of the member cardinality. For a fixed p, if $f << M_{a}$ , no matter $M_{a} < M_{T}$ or not, all f slots will fill with tone signals with high probability, resulting in $N_{0} = 0$ . In such case, we cannot judge whether $M_{a}$ is greater or smaller than $M_{T}$ based on $N_{0}$ . Hence, for a member cardinality threshold $M_{T}$ and an occupation probability p, the number of time slots has a lower bound. It is obvious that when we can judge $M_{a} < M_{T}$ , we can also judge $M_{a} \geq M_{T}$ . We set the parameters to ensure that when $M_{a} < M_{T}$ , the evaluation is valid. Due to $E [N_{0}]$ monotonically decreases with the cardinality, that is, we just need to ensure the evaluation is valid when $M_{a} = M_{T}$ . For any p, $p \in (0, 1)$ , we can calculate the minimum number of slots $f_{lbound}$ . $f_{lbound}$ needs to ensure the situation that there is no empty slot occurring with probability less than $1 - θ$ . Generally, it needs to set $θ$ close to $100 %$ to ensure the validity of our evaluation. Following the classical result of Feller,¹⁷ according to the conditions above, if we want to achieve $θ > 99.9 %$ , we need to ensure that $E [N_{0}]$ is >5. Then, we have the following equation

f_{lbound} {(1 - p)}^{M_{T}} = 5

(5)

By solving this equation, we have the lower bound of the number of time slots

f_{lbound} = L (p, M_{T})

(6)

However, to ensure the validity of our evaluation, for any p, $p \in (0, 1)$ , we need to calculate the maximum number of slots $f_{ubound}$ . $f_{ubound}$ needs to ensure the situation that there is no non-empty slot occurring with probability less than $1 - γ$ . Also, according to the Feller,¹⁷ if we want to achieve $γ > 99.9 %$ , we need to ensure that $E [N_{c}]$ is >5. Then, we have the following equation

f_{ubound} (1 - {(1 - p)}^{M_{T}}) = 5

(7)

By solving this equation, we have the upper bound of the number of time slots

f_{ubound} = U (p, M_{T})

(8)

The accuracy of the member cardinality evaluation

In this section, we consider the accuracy of the member cardinality evaluation. We need to choose f and p carefully to ensure that Algorithm 2 has a high confidence to make a correct judgment. For the evaluation accuracy, we request that if

| \frac{M_{T} - M_{a}}{M_{T}} | \geq β

(9)

we have

\Pr [| N_{0} - τ | \geq 1] \geq ε

(10)

Algorithm 2: The adaptive member cardinality evaluation in the cluster-based VCPS $(f, p, τ, k, g)$
1: CH broadcasts f, p, $τ$ , k, g, and time synchronization messages, then switches to observe the channel;
2: Each CM sends a tone signal with probability p in each of the first k time slots;
3: CMs switch from the transmission state to the reception state and CH switches from the reception state to the transmission state;
4: if All the first k slots are empty then
5: CH sends a tone signal in the feedback slot;
6: CH judges that $M_{a} < M_{T}$ ;
7: Break;
8: else
9: CMs switch from the reception state to the transmission state and CH switches from the transmission state to the reception state;
10: Each CM sends a tone signal with probability p in each of the next $(g - k)$ time slots;
11: CMs switch from the transmission state to the reception state and CH switches from the reception state to the transmission state;
12: if All the first g slots are non-empty then
13: CH sends a tone signal in the feedback slot;
14: CH judges that $M_{a} \geq M_{T}$ ;
15: Break;
16: else
17: CMs switch from the reception state to the transmission state and CH switches from the transmission state to the reception state;
18: Each CM sends a tone signal with probability p in each of the next $(f - g)$ time slots;
19: if $N_{0} < τ$ or $N_{c} > f - τ$ then
20: CH judges that $M_{a} < M_{T}$ ;
21: Break;
22: else
23: CH judges that $M_{a} \geq M_{T}$ ;
24: end if
25: end if
26: end if

The threshold $β$ and confidence $ε$ are inputs to the evaluation. It is important to note that these two parameters are just the accuracy requirement for each evaluation process; they do not equal to the accuracy of the whole system. We will evaluate the system accuracy in section “Performance evaluation.” The parameter $τ$ in the above equation can be calculated as

τ = f {(1 - p)}^{M_{T}}

(11)

We give an example to help understand. If the threshold of the member cardinality is 100, and given $β = 1 %$ , when the actual member cardinality is ≤99, the desired number of empty slots $N_{0}$ is larger than $τ + 1$ with probability greater than $ε = 99.9 %$ . Since $N_{0}$ is binomially distributed with parameters f, p, and $M_{a}$ . According to the characteristic of monotonically decreasing function, we just need to concern about the situation that $M_{a}$ is close to $M_{T}$ . This is because when $M_{a}$ is very smaller than $M_{T}$ , $N_{0}$ will significantly be larger than $τ$ . If $M_{a}$ and f are large and p has a certain value, according to Umer et al.,¹⁰ we have that $N_{0}$ can be asymptotically approximated as normal distributions. We denote a normal distribution as $N [μ_{0}, σ_{0}^{2}]$ , where $μ_{0}$ is the mean of the normal distribution and $σ_{0}^{2}$ is the variance of the normal distribution. Then, we have

N_{0} ~ N [μ_{0}, σ_{0}^{2}]

(12)

where

μ_{0} = E [N_{0} (M_{a})] = f {(1 - p)}^{M_{a}} \approx f e^{- p M_{a}}

(13)

\begin{matrix} σ_{0}^{2} & = Var [N_{0} (M_{a})] \\ = E [{(\sum_{j = 1}^{f} X_{j})}^{2}] - {(E [\sum_{j = 1}^{f} X_{j}])}^{2} \\ = E [\sum_{j = 1}^{f} X_{j}^{2} + \sum_{i = 1}^{f} \sum_{j = 1, j \neq i}^{f} X_{i} X_{j}] - {(E [\sum_{j = 1}^{f} X_{j}])}^{2} \\ = f {(1 - p)}^{M_{a}} + f (f - 1) {(1 - p)}^{2 M_{a}} - f^{2} {(1 - p)}^{2 M_{a}} \\ \approx f e^{- p M_{a}} + f (f - 1) e^{- 2 p M_{a}} - f^{2} e^{- 2 p M_{a}} \\ = f e^{- p M_{a}} (1 - e^{- p M_{a}}) \end{matrix}

(14)

We have the following equations

\begin{matrix} \Pr [(N_{0} - τ) \geq 1] & = 1 - Φ (\frac{τ + 1 - μ_{0}}{σ_{0}}) \\ = \frac{1}{2} (1 - \erf (\frac{τ + 1 - μ_{0}}{\sqrt{2} σ_{0}})) \\ = \frac{1}{2} (1 - \erf (\frac{f {(1 - p)}^{M_{T}} + 1 - f e^{- p M_{a}}}{\sqrt{2 f e^{- p M_{a}} (1 - e^{- p M_{a}})}})) \end{matrix}

(15)

\begin{matrix} \Pr [(N_{0} - τ) \leq - 1] & = Φ (\frac{τ - 1 - μ_{0}}{σ_{0}}) \\ = \frac{1}{2} (1 + \erf (\frac{τ - 1 - μ_{0}}{\sqrt{2} σ_{0}})) \\ = \frac{1}{2} (1 + \erf (\frac{f {(1 - p)}^{M_{T}} - 1 - f e^{- p M_{a}}}{\sqrt{2 f e^{- p M_{a}} (1 - e^{- p M_{a}})}})) \end{matrix}

(16)

As $N_{0}$ monotonically decreases with the member cardinality and $M_{a}$ is an integer, for any f, p, and $ε$ , it is intuitive that if we achieve the desired accuracy for the case that $M_{a} = ⌊ (1 - β) M_{T} ⌋$ , it is achieved for all $M_{a} \leq ⌊ (1 - β) M_{T} ⌋$ . Also, if we achieve a desired accuracy for the case that $M_{a} = ⌈ (1 + β) M_{T} ⌉$ , it is achieved for all $M_{a} \geq ⌈ (1 + β) M_{T} ⌉$ . To satisfy the accuracy requirement, and to minimize the evaluation time, we have

\frac{1}{2} (1 - \erf (\frac{f_{l} {(1 - p)}^{M_{T}} + 1 - f_{l} e^{- p ⌊ (1 - β) M_{T} ⌋}}{\sqrt{2 f_{l} e^{- p ⌊ (1 - β) M_{T} ⌋} (1 - e^{- p ⌊ (1 - β) M_{T} ⌋})}})) = ε

(17)

\frac{1}{2} (1 + \erf (\frac{f_{r} {(1 - p)}^{M_{T}} - 1 - f_{r} e^{- p ⌈ (1 - β) M_{T} ⌉}}{\sqrt{2 f_{r} e^{- p ⌈ (1 - β) M_{T} ⌉} (1 - e^{- p ⌈ (1 - β) M_{T} ⌉})}})) = ε

(18)

f_{accuracy} = max (f_{l}, f_{r})

(19)

Then, by solving the above equations, we have

f_{accuracy} = K (p, M_{T}, β, ε)

(20)

Determining the evaluation parameters

For the proposed member cardinality evaluation method, on one hand, we need to ensure that the evaluation is valid, and, on the other hand, we need to achieve the required evaluation accuracy. According to the analysis of the above sections, for any $p, p \in (0, 1),$ we can calculate f by the following equation

f = ⌈ max (f_{lbound}, min (f_{ubound}, f_{accuracy})) ⌉

(21)

The goal of this article is to minimize the member cardinality evaluation time; we can minimize the number of time slots f by choosing a suitable occupation probability p. Due to the complexity of the function, the closed-form solution for p and f cannot be achieved. Instead, we can calculate them by numerical method. In Table 1, we present some evaluation parameters of the proposed method.

Table 1.

Evaluation parameters satisfied the requirement of validity and accuracy with setting $θ = 99.9 %$ and $γ = 99.9 %$ .

$M_{T}$	$β (%)$	$ε (%)$	p	f	$T (s)$
800	1	95	0.002	$42, 220$	0.549
400	1	95	0.004	$42, 220$	0.549
160	1	95	0.010	$27, 094$	0.352
80	1	95	0.019	$27, 092$	0.352
40	1	95	0.037	6852	0.089
800	5	95	0.002	1753	0.023
400	5	95	0.004	1753	0.023
160	5	95	0.010	1752	0.023
80	5	95	0.019	1750	0.023
40	5	95	0.036	1750	0.023
800	1	80	0.002	$11, 500$	0.150
400	1	80	0.004	$11, 500$	0.150
160	1	80	0.010	7449	0.097
80	1	80	0.019	7440	0.097
40	1	80	0.037	1962	0.026
800	5	80	0.002	541	0.007
400	5	80	0.004	541	0.007
160	5	80	0.009	537	0.007
80	5	80	0.018	537	0.007
40	5	80	0.035	537	0.007

From Table 1, we can see that the smaller the threshold $β$ or the larger the confidence $ε$ , the more the accuracy we desired about the evaluation, and the more time slots are needed for the evaluation process. We find that the time slot occupation probability p is relatively fixed for a fixed $M_{T}$ . Using this feature, we can reduce the parameter calculation steps which will reduce the computational complexity significantly. The duration of our evaluation method is also given in this table. We can see that the evaluation time increases with the increasing threshold $M_{T}$ . While in our evaluation method, even the longest evaluation time is shorter than the time in the traditional method. The efficiency of our method has been proved.

Adaptive member cardinality evaluation

The previous section has made a detailed introduction to the slot time occupation technique and the parameter determining process. When the accuracy parameters are fixed, the duration of a evaluation process just depends on $M_{T}$ . This section proposes modifications and extensions to the evaluation process in which the CH can interrupt the evaluation process and save the evaluation time.

Intuitively, if there are several consecutive empty slots in the beginning of the evaluation, it has a high confidence that $M_{a}$ is relatively small. With this feature, we propose an adaptive member cardinality evaluation method. In this method, when CH observes the channel after sending a start signal, it needs to judge whether all the first k consecutive slots are empty or not. After these k slots, based on the judgment, CH can interrupt the evaluation process by sending a tone signal in the feedback slot. Considering the status switch of CH and CMs, two more time slots are needed before and after the feedback slot. Similarly, if there are several consecutive non-empty slots in the beginning of the evaluation, it has a high confidence that $M_{a}$ is relatively large. In our adaptive member cardinality evaluation method, the CH also needs to judge whether all the first g consecutive slots are non-empty or not and to decide whether to interrupt the evaluation process or not. Figure 3 depicts the slot structure of the adaptive member cardinality evaluation method. After the CMs detecting the tone signal in the feedback slots, the adaptive evaluation process finishes. The duration of the whole adaptive evaluation process is defined as $T_{adapt}$ . The same as above, we define the time that the CH completes the initiation steps as T₁. If all the first k consecutive slots are empty, we have $T_{adapt} = T_{1} + 13 μ s * (k + 2)$ . If all the first g consecutive slots are non-empty, we have $T_{adapt} = T_{1} + 13 μ s * (g + 3 + 2)$ . If both the above situations do not occur, we have $T_{adapt} = T_{1} + 13 μ s * (f + 3 + 3)$ . For the whole evaluation process, the feedback time and the status switching time are relatively short. Obviously, when $M_{a}$ is much smaller or much greater than $M_{T}$ , the evaluation time will greatly decrease with the interruption of the evaluation process. The core of this method is to determine the parameters k and g.

Figure 3.

The slot structure of the adaptive member cardinality evaluation method.

Determining the parameter k

We analyze the parameter k first. In the classical vehicle cluster, the maximum member cardinality is 1000 which is defined as $M_{\max}$ . We need to choose a proper k to ensure that if all the first k consecutive slots are empty, we have

\Pr [(M_{T} - M_{a}) \geq 0] \geq τ

(22)

Generally, we set $τ = 99.9 %$ to guarantee accuracy of the judgment. We use A to denote that all the first k consecutive slots are empty. Then, we have the following equation

\begin{matrix} \Pr [M_{a} \leq M_{T} | A] & = \Pr [M_{a} = 1, M_{a} = 2, \dots, M_{a} = M_{T} | A] \\ = \Pr [M_{a} = 1 | A] + \dots + \Pr [M_{a} = M_{T} | A] \\ = \sum_{i = 1}^{M_{T}} P r [M_{a} = i | A] \\ = \sum_{i = 1}^{M_{T}} \frac{\Pr [A | M_{a} = i] \Pr [M_{a} = i]}{\sum_{j = 1}^{M_{\max}} \Pr [A | M_{a} = j] \Pr [M_{a} = j]} \\ (based on the Bayesian formula) \\ = \sum_{i = 1}^{M_{T}} \frac{\Pr [M_{a} = i] {(1 - p)}^{ki}}{\sum_{j = 1}^{M_{\max}} \Pr [M_{a} = j] {(1 - p)}^{kj}} \geq 99.9 % \end{matrix}

(23)

From the above equation, we can find that the value of k is related to the distribution of $M_{a}$ . After calculation, we find that, with $τ = 99.9 %$ , the value of k are similar when $M_{a}$ follows most common distributions. For convenience of calculations, we assume that $M_{a}$ is uniformly distributed here. By solving the following equation, we can obtain the minimum value of k

\sum_{i = 1}^{M_{T}} \frac{{(1 - p)}^{ki}}{\sum_{j = 1}^{M_{\max}} {(1 - p)}^{kj}} = 99.9 %

(24)

Determining the parameter g

We need to choose a proper g to ensure that if all the first g consecutive slots are non-empty, we have

\Pr [(M_{T} - M_{a}) \leq 0] \geq τ

(25)

In Figure 3, there are two state change slots and one feedback slot inserted in the g slots, but the three slots are not counted in the g slots. We use B to denote that all the first g slots are non-empty. Then, we have the following equation

\begin{matrix} \Pr [M_{a} \geq M_{T} | B] & = \Pr [M_{a} = M_{T}, M_{a} = M_{T} + 1, \dots, M_{a} = M_{\max} | B] \\ = \Pr [M_{a} = M_{T} | B] + \dots + \Pr [M_{a} = M_{\max} | B] \\ = \sum_{i = M_{T}}^{M_{\max}} P r [M_{a} = i | B] \\ = \sum_{i = M_{T}}^{M_{\max}} \frac{\Pr [B | M_{a} = i] \Pr [M_{a} = i]}{\sum_{j = 1}^{M_{\max}} \Pr [B | M_{a} = j] \Pr [M_{a} = j]} \\ (based on the Bayesian formula) \\ = \sum_{i = M_{T}}^{M_{\max}} \frac{\Pr [M_{a} = i] {(1 - {(1 - p)}^{i})}^{g}}{\sum_{j = 1}^{M_{\max}} \Pr [M_{a} = j] {(1 - {(1 - p)}^{j})}^{g}} \geq 99.9 % \end{matrix}

(26)

We can obtain the minimum value of g by solving the following equation

\sum_{i = M_{T}}^{M_{\max}} \frac{{(1 - {(1 - p)}^{i})}^{g}}{{\sum_{j = 1}^{M_{\max}} (1 - {(1 - p)}^{i})}^{g}} = 99.9 %

(27)

The whole adaptive evaluation process

In Table 2, we present the values of k and g for different values of $M_{T}$ , $β$ , and $ε$ . We find that the value of k is 5 under different parameters. The value of g increases with $M_{T}$ . Both of them are much smaller than f. If the CH interrupts the evaluation process, it can save a lot of time and ensure a high evaluation accuracy at the same time.

Table 2.

The values of k and g for different values of $M_{T}$ with setting $τ = 99.9 %$ .

$M_{T}$	$β (%)$	$ε (%)$	p	f	k	g
800	1	95	0.002	$42, 220$	5	81
400	1	95	0.004	$42, 220$	5	24
160	1	95	0.010	$27, 094$	5	16
80	1	95	0.019	$27, 092$	5	12
40	1	95	0.037	6852	5	9
800	5	80	0.002	541	5	81
400	5	80	0.004	541	5	24
160	5	80	0.009	537	5	13
80	5	80	0.018	537	5	11
40	5	80	0.035	537	5	8

The whole process of our adaptive member cardinality evaluation is presented in Algorithm 2.

Considering the channel state

In the above sections, we analyze the member cardinality evaluation method considering an ideal communication channel. While in the actual VANETs, the channel is unreliable. Even the tone signal has a signal loss problem. In this section, we extend the time slot occupation method by considering the channel state.

In one time slot, we define the CM which needs to send a tone signal as $v_{i}$ . The probability that the CH successfully receives the tone signal from $v_{i}$ is defined as $q_{i}$ . When one CM is at distance d from the CH and the transmitting power of the CH is $P_{HT}$ , we define the probability density function (pdf) of the received signal power in the CH as $D_{d P_{HT}} (\cdot)$ . Similarly, when one CH is at distance d from the CM and the transmitting power of the tone signal is $P_{toneT}$ , we define the pdf of the received signal power in the CH as $D_{d P_{toneT}} (\cdot)$ . In general, $D_{d P_{HT}} (\cdot)$ and $D_{d P_{tone}} (\cdot)$ depend on the actual channel model. The receiving sensitivity of the CM is defined as $P_{MS}$ . The receiving sensitivity of the tone signal in CH is defined as $P_{toneS}$ . The CH can successfully receive the tone signal from $v_{i}$ only if (1) the CM $v_{i}$ can correctly receive the start signal from the CH and (2) the CH can receive the tone signal from the CM $v_{i}$ . The $q_{i}$ can be calculated as

q_{i} = \int_{P_{MS}}^{\infty} D_{d P_{HT}} (x) \cdot \int_{P_{toneS}}^{\infty} D_{d P_{toneT}} (y) dxdy

(28)

We define the mean and the variance of $q_{i}$ as $μ_{q}$ and $σ_{q}^{2}$ . To satisfy the validity and the accuracy requirement of the member cardinality evaluation, we need to recalculate the parameters used in the proposed evaluation method.

The evaluation validity considering the channel state

Considering the channel state, the lower bound of the number of time slots can be obtained by solving the following equations

\begin{matrix} f_{lbound} \cdot Π_{i = 1}^{M_{T}} (1 - p q_{i}) \approx f_{lbound} e^{- p M_{T} μ_{q}} \\ (1 + \sum_{r = 1}^{\infty} \frac{p^{r}}{r!} (Σ q_{i} - M_{T} μ_{q})) \\ \approx f_{lbound} e^{- p M_{T} μ_{q}} = 5 \end{matrix}

(29)

f_{lbound} = L (p, μ_{q}, M_{T})

(30)

The upper bound of the number of time slots can be obtained by solving the following equations

\begin{matrix} f_{ubound} \cdot (1 - Π_{i = 1}^{M_{T}} (1 - p q_{i})) \approx f_{ubound} \\ [1 - e^{- p M_{T} μ_{q}} (1 + \sum_{r = 1}^{\infty} \frac{p^{r}}{r!} (Σ q_{i} - M_{T} μ_{q}))] \\ \approx f_{ubound} [1 - e^{- p M_{T} μ_{q}}] = 5 \end{matrix}

(31)

f_{ubound} = U (p, μ_{p}, M_{T})

(32)

The evaluation accuracy considering the channel state

For the accuracy of the member cardinality evaluation, by considering the channel state, the threshold $τ$ can be recalculated as

τ = f \cdot Π_{i = 1}^{M_{T}} (1 - p q_{i}) \approx f e^{- p M_{T} μ_{q}}

(33)

According to the analysis in section “Parameters determining method,” we have

N_{0} ~ N [μ_{0}, σ_{0}^{2}]

(34)

Then

\begin{matrix} μ_{0} = E [N_{0} (M_{a})] = f \cdot Π_{i = 1}^{M_{a}} (1 - p q_{i}) \approx f e^{- p M_{a} μ_{q}} \end{matrix}

(35)

Let

q = {q_{1}, q_{2}, \dots, q_{M_{a}}}

(36)

According to the conditional variance formula, we have

\begin{matrix} σ_{0}^{2} & = Var [N_{0} (M_{a})] \\ = Var [E [N_{0} (M_{a}) | q]] + E [Var [N_{0} (M_{a}) | q]] \end{matrix}

(37)

$Var [E [N_{0} (M_{a}) | q]]$ represents the variance due to different probability of receiving the tone signal. $E [Var [N_{0} (M_{a}) | q]]$ represents the variance due to different probability of time slot occupation. We use the following equations to calculate $σ_{0}^{2}$ :

1. Calculate $Var [E [N_{0} (M_{a}) | q]]$

\begin{matrix} Var [E [N_{0} (M_{a}) | q]] = E [{(E [N_{0} (M_{a}) | q])}^{2}] - {(E [N_{0} (M_{a})])}^{2} \\ \approx f^{2} e^{- 2 M_{a} pu} (1 + 2 p^{2} M_{a} σ_{q}^{2} - 1 - p^{2} M_{a} σ_{q}^{2}) \\ (consider only the first - and second - order terms) \\ = \frac{f^{2} p^{2} σ_{q}^{2} M_{a}}{e^{2 M_{a} pu}} \end{matrix}

(38)

2. Calculate $E [Var [N_{0} (M_{a}) | q]]$

\begin{matrix} Var [N_{0} (M_{a}) | q] \\ = E [{(\sum_{i = 1}^{f} X_{i})}^{2} | q] - E {[\sum_{i = 1}^{f} X_{i} | q]}^{2} \\ = f (f - 1) Π_{i = 1}^{M_{a}} (1 - 2 p q_{i}) + f Π_{i = 1}^{M_{a}} (1 - p q_{i}) - f^{2} Π_{i = 1}^{M_{a}} {(1 - p q_{i})}^{2} \\ \approx f (f - 1) Π_{i = 1}^{M_{a}} (e^{- \frac{2 q_{i}}{f}} - \frac{2 {q_{i}}^{2}}{f^{2}}) - f^{2} Π_{i = 1}^{M_{a}} {(e^{- \frac{q_{i}}{f}} - \frac{{q_{i}}^{2}}{2 f^{2}})}^{2} \\ + f Π_{i = 1}^{M_{a}} (1 - p q_{i}) (ignore the higher order terms) \\ \approx (- f + \frac{2 f - f^{2}}{f^{2}} \sum_{i = 1}^{M_{a}} p^{2} q_{i}^{2}) e^{- 2 M_{a} p μ_{q}} + f e^{- M_{a} p μ_{q}} \\ \approx f e^{- M_{a} p μ_{q}} (1 - (1 + \frac{1}{f} (\sum_{i = 1}^{M_{a}} p^{2} q_{i}^{2})) e^{- M_{a} p μ_{q}}) \end{matrix}

(39)

\begin{matrix} E [Var [N_{0} (M_{a}) | q]] = f e^{- M_{a} p μ_{q}} \\ (1 - (1 + \frac{M_{a}}{f} p^{2} ({μ_{q}}^{2} + σ_{q}^{2}) e^{- M_{a} p μ_{q}})) \end{matrix}

(40)

By solving the above equations, we have

\begin{matrix} σ_{0}^{2} = & \frac{f^{2} p^{2} σ_{q}^{2} M_{a}}{e^{2 M_{a} pu}} + f e^{- M_{a} p μ_{q}} \\ (1 - (1 + \frac{M_{a}}{f} p^{2} (μ_{q}^{2} + σ_{q}^{2}) e^{- M_{a} p μ_{q}})) \end{matrix}

(41)

After obtaining $μ_{0}$ and $σ_{0}^{2}$ , we can recalculate the evaluation parameters based on equations (15)–(20).

Determining k and g considering the channel state

By considering the unreliability of the channel state, similarly with equations (22)–(24), we can obtain k by solving the following equation

\sum_{i = 1}^{M_{T}} \frac{{[Π_{w = 1}^{i} (1 - p q_{w})]}^{k}}{{\sum_{j = 1}^{M_{\max}} [Π_{u = 1}^{j} (1 - p q_{u})]}^{k}} \approx \sum_{i = 1}^{M_{T}} \frac{e^{- ip μ_{q} k}}{\sum_{j = 1}^{M_{\max}} e^{- jp μ_{q} k}} = 99.9 %

(42)

Similarly with equations (25)–(27), we can obtain g by solving the following equation

\begin{matrix} \sum_{i = M_{T}}^{M_{\max}} \frac{{[1 - (Π_{w = 1}^{i} (1 - p q_{w}))]}^{g}}{\sum_{j = 1}^{M_{\max}} {[1 - (Π_{u = 1}^{j} (1 - p q_{u}))]}^{g}} \\ \approx \sum_{i = M_{T}}^{M_{\max}} \frac{{(1 - e^{- ip μ_{q}})}^{g}}{\sum_{j = 1}^{M_{\max}} {(1 - e^{- jp μ_{q}})}^{g}} = 99.9 % \end{matrix}

(43)

In this article, we consider the Rayleigh fading channels between vehicles. We assume $P_{HT} = P_{toneT} = 20 dB m$ , $P_{MS} = P_{toneS} = - 80 dB m$ , and $d_{\max} = 500 m$ . The receiving antenna gain $G_{r} = 6 dBi$ . The transmitting antenna gain $G_{t} = 6 dBi$ The path loss exponent $r = 3, 4, 5$ . We present some evaluation parameters of the proposed method in Table 3 considering the unreliability of the channel state. We can find that due to the unreliability of the channel state, we need more time slots to do the member cardinality evaluation. The values of k and g are presented in Table 4. We can find that the adaptive parameters k and g are barely affected by the unreliability of the channel state.

Table 3.

Evaluation parameters considering the channel state. Setting $θ = 99.9 %$ , $γ = 99.9 %$ , $β = 5 %$ , and $ε = 95 %$ .

r	$μ_{q}$	$σ_{q}^{2}$	p	$M_{T}$	f
3	0.9371	0.0032	0.002	800	2710
3	0.9371	0.0032	0.004	400	2710
3	0.9371	0.0032	0.010	160	2708
3	0.9371	0.0032	0.019	80	2708
3	0.9371	0.0032	0.036	40	2706
4	0.8762	0.0101	0.002	800	6852
4	0.8762	0.0101	0.004	400	6852
4	0.8762	0.0101	0.010	160	4922
4	0.8762	0.0101	0.019	80	4920
4	0.8762	0.0101	0.035	40	2068
5	0.7964	0.0290	0.002	800	$12, 256$
5	0.8762	0.0101	0.004	400	$12, 254$
5	0.7964	0.0290	0.010	160	6632
5	0.7964	0.0290	0.018	80	6630
5	0.7964	0.0290	0.034	40	4998

Table 4.

The values of k and g considering the channel state with setting $τ = 99.9 %$ .

r	$μ_{q}$	$σ_{q}^{2}$	p	$M_{T}$	k	g
3	0.9371	0.0032	0.002	800	5	72
3	0.9371	0.0032	0.004	400	5	21
3	0.9371	0.0032	0.010	160	5	13
3	0.9371	0.0032	0.019	80	5	10
3	0.9371	0.0032	0.035	40	5	7

Performance evaluation

Since different kinds of the performances of the proposed member cardinality evaluation methods have been presented in the tables above. In this section, our main concerns are the evaluation accuracy and the average evaluation time. The simulation follows IEEE 802.11p standard, and all the presented results are obtained by averaging over 500 runs.

We present evaluation accuracy of the member cardinality under different parameters in Figures 4 –7. As a whole, the proposed evaluation methods have a high evaluation accuracy. Figures 4 and 5 compare the evaluation accuracy with the basic evaluation method and the adaptive evaluation method in an ideal channel state. We can find that the adaptive evaluation method can help improve the evaluation accuracy. The same conclusion can be obtained by the comparison between Figures 6 and 7. These two figures present the evaluation accuracy of the basic evaluation method and the adaptive evaluation method in the unreliable channel state. Besides, by comparing Figures 4 and 6 and Figures 5 and 7, we can find that the unreliable channel state affects the accuracy of both the basic and adaptive evaluation methods.

Figure 4.

Evaluation accuracy of the basic evaluation method in the ideal channel state.

Figure 5.

Evaluation accuracy of the adaptive evaluation method in the ideal channel state.

Figure 6.

Evaluation accuracy of the basic evaluation method in the unreliable channel state.

Figure 7.

Evaluation accuracy of the adaptive evaluation method in the unreliable channel state.

In Figure 8, we present the average evaluation time of the proposed methods. We set $β = 5 %$ , $ε = 95 %$ , and $τ = 99.9 %$ . $r = 4$ , $μ_{q} = 0.8762$ , and $σ_{q}^{2} = 0.0101$ . From Figure 8, we can conclude that (1) the proposed member cardinality evaluation method is much faster than the traditional method; (2) the proposed adaptive evaluation method can improve the time efficiency of the proposed basic evaluation method; and (3) in the unreliable channel state, we need more time to do the member cardinality evaluation.

Figure 8.

The average evaluation time.

All the performances prove the accuracy and the efficiency of the proposed member cardinality evaluation method. It is suitable for the cluster-based VCPS.

Conclusion

In this article, we study the problem of how to evaluate the member cardinality in the cluster-based VCPS. We propose a new member cardinality evaluation method based on the time slot occupation technique. The validity and accuracy of the change verification method are analyzed in this article. We propose an adaptive evaluation method which can further reduce the evaluation time and improve the evaluation accuracy, and we analyze the effects of the channel state for the proposed member cardinality evaluation methods. Mathematical analysis and simulation results confirm the efficiency and accuracy of our method.

Footnotes

Academic Editor: Donghyun Kim

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Natural Science Foundation of China (grant nos 61471028, 61371069, and 61272505).

References

Zhang

. Specifying and modeling automotive cyber physical systems. In: Proceedings of the IEEE 16th international conference on computational science and engineering, Sydney, NSW, Australia, 3–5 December 2013, pp.603–610. New York: IEEE.

Xiong

Zhu

Liu

. Cyber-physical-social system in intelligent transportation. IEEE/CAA J Autom Sinica 2015; 2(3): 320–333.

Vodopivec

Bester

Kos

. A survey on clustering algorithms for vehicular ad-hoc networks. In: Proceedings of the IEEE 35th international conference on telecommunications and signal processing, Prague, 3–4 July 2012, pp.52–56. New York: IEEE.

Rawat

Bajracharya

Yan

. Towards intelligent transportation cyber-physical systems: real-time computing and communications perspectives. In: Proceedings of the SoutheastCon 2015, Fort Lauderdale, FL, 9–12 April 2015, pp.1–6. New York: IEEE.

Fallah

Sengupta

. A cyber-physical systems approach to the design of vehicle safety networks. In: Proceedings of the 32nd international conference on distributed computing systems workshops, Macau, China, 18–21 June 2012, pp.324–329. New York: IEEE.

Jara

Genoud

Bocchi

. Big data for cyber physical systems: an analysis of challenges, solutions and opportunities. In: Proceedings of the eighth international conference on innovative mobile and internet services in ubiquitous computing (IMIS), Birmingham, 2–4 July 2014, pp.376–380. New York: IEEE.

Qian

Jing

Huo

. Efficient change verification of member cardinality in cluster-based VCPS. In: 2015 international conference on identification, information, and knowledge in the internet of things (IIKI), Beijing, China, 22–23 October 2015, pp.169–174. New York: IEEE.

Artimy

. Local density estimation and dynamic transmission-range assignment in vehicular ad hoc networks. IEEE T Intell Transp 2007; 8(3): 400–412.

Shirani

Hendessi

Gulliver

. Store-carry-forward message dissemination in vehicular ad-hoc networks with local density estimation. In: Proceedings of the IEEE vehicular technology conference fall (VTC), Anchorage, AK, 20–23 September 2009, pp.1–6. New York: IEEE.

10.

Umer

Ding

Honary

. Implementation of microscopic parameters for density estimation of heterogeneous traffic flow for VANET. In: Proceedings of the 7th international symposium on communication systems networks and digital signal processing (CSNDSP), Newcastle upon Tyne, 21–23 July 2010, pp.66–70. New York: IEEE.

11.

Panichpapiboon

Pattara-atikom

. Evaluation of a neighbor-based vehicle density estimation scheme. In Proceedings of the 8th international conference on ITS telecommunications (ITST), Phuket, 24 October 2008, pp.294–298. New York: IEEE.

12.

Panichpapiboon

Pattara-atikom

. Exploiting wireless communication in vehicle density estimation. IEEE T Veh Technol 2011; 60(6): 2742–2751.

13.

Mao

. Road traffic density estimation in vehicular networks. In: 2013 IEEE wireless communications and networking conference (WCNC), Shanghai, China, 7–10 April 2013, pp.4653–4658. New York: IEEE.

14.

Mertens

Wellens

Mahonen

. Simulation-based performance evaluation of enhanced broadcast schemes for IEEE 802.11-based vehicular networks. In: Proceedings of the IEEE vehicular technology conference (VTC), Singapore, 11–14 May 2008, pp.3042–3046. New York: IEEE.

15.

Rawat

Yan

Popescu

. Dynamic adaptation of joint transmission power and contention window in VANET. In Proceedings of the IEEE vehicular technology conference (VTC), Anchorage, AK, 20–23 September 2009, pp.1–5. New York: IEEE.

16.

IEEE Std 802.11:2010. IEEE standard for information technology—local and metropolitan area networks—specific requirements—part 11: wireless LAN medium access control (MAC) and physical layer (PHY) specifications amendment 6: wireless access in vehicular environments, pp.1–51.

17.

Feller

. An introduction to probability theory and its applications. New York: John Wiley & Sons, 1968.

Efficient evaluation of member cardinality in cluster-based vehicular cyber-physical systems

Abstract

Keywords

Introduction and motivation

Related work

System description and basic principle

Parameters determining method

The empty slots and non-empty slots

The validity of the member cardinality evaluation

The accuracy of the member cardinality evaluation

Determining the evaluation parameters

Adaptive member cardinality evaluation

Determining the parameter k

Determining the parameter g

The whole adaptive evaluation process

Considering the channel state

The evaluation validity considering the channel state

The evaluation accuracy considering the channel state

Determining k and g considering the channel state

Performance evaluation

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References