(PDF) Distributed and adaptive resource management in Cloud-assisted Cognitive Radio Vehicular Networks with hard reliability gu

Vehicular Communications 2 (2015) 1–12 Contents lists available at ScienceDirect Vehicular Communications www.elsevier.com/locate/vehcom Distributed and adaptive resource management in Cloud-assisted Cognitive Radio Vehicular Networks with hard reliability guarantees Nicola Cordeschi ∗ , Danilo Amendola, Mohammad Shojafar, Enzo Baccarelli Sapienza University of Rome, Department of Information Electronics and Telecommunication Engineering (DIET), Via Eudossiana, 18, 00184 Rome, Italy a r t i c l e i n f o a b s t r a c t Article history: In this contribution, we design and test the performance of a distributed and adaptive resource Received 8 May 2014 management controller, which allows the optimal exploitation of Cognitive Radio and soft-input/soft- Received in revised form 28 August 2014 output data fusion in Vehicular Access Networks. The ultimate goal is to allow energy and computing- Accepted 28 August 2014 limited car smartphones to utilize the available Vehicular-to-Infrastructure WiFi connections for Available online 8 October 2014 performing traffic offloading towards local or remote Clouds by opportunistically acceding to a Keywords: spectral-limited wireless backbone built up by multiple Roadside Units. For this purpose, we recast Cloud-assisted vehicular networks the afforded resource management problem into a suitable constrained stochastic Network Utility Cognitive Radio access Maximization problem. Afterwards, we derive the optimal cognitive resource management controller, Stochastic network utility maximization which dynamically allocates the access time-windows at the serving Roadside Units (i.e., the access Energy and bandwidth limitations points) together with the access rates and traffic flows at the served Vehicular Clients (i.e., the Distributed and scalable adaptive resource secondary users of the wireless backbone). Interestingly, the developed controller provides hard reliability management guarantees to the Cloud Service Provider (i.e., the primary user of the wireless backbone) on a per-slot basis. Furthermore, it is also capable to self-acquire context information about the currently available bandwidth-energy resources, so as to quickly adapt to the mobility-induced abrupt changes of the state of the vehicular network, even in the presence of fadings, imperfect context information and intermittent Vehicular-to-Infrastructure connectivity. Finally, we develop a related access protocol, which supports a fully distributed and scalable implementation of the optimal controller. © 2014 Elsevier Inc. All rights reserved. 1. Motivation and goals instantaneous rate of packets collision among the backbone traffic (that is, the primary traffic) and the access traffic (that is, the sec- In this paper, we focus on Cloud and Internet-assisted Vehicle- ondary traffic). Several recent studies (see, for example, [2] and to-Infrastructure (V2I) communication for emerging non-safety references therein) about the mobile computation offloading in applications, which require the Quality of Service (QoS) up/down- real-life cloud-assisted scenarios point out that the usage of WiFi- loading of large amounts of data, such as, podcast subscrip- based traffic offloading in place of 3G-assisted one may reduce tions of audio/video programs, digital map downloading/updating, the average energy consumption of current smartphones of about Web surfing, advertising applications and opportunistic vehicular- 55%. About the spectral crowding of current vehicular networks, assisted content delivery applications. In fact, it is expected that the communication traffic flows typically generated by safety ap- these bandwidth-demanding applications will have a significant plications and routed in downlink over the available backbones are impact on the commercial success of Vehicular Cloud Computing of burst-type. Hence, these flows present inter-arrival gaps of non- (VCC) and will contribute to accelerate its implementation and de- negligible time durations, which can be opportunistically exploited ployment [1]. However, in order to continue to guarantee higher by VCs equipped with Cognitive Radio (CR) smartphones to accede priority to the traffic flows generated in downlink by the Service to the serving RSUs through WiFi connections [3]. Providers, hard upper bounds must be imposed on the tolerated Therefore, motivated by the aforementioned considerations, in this paper we consider the V2I CR-based access scenario of Fig. 1, where multiple car smartphones equipped with heterogeneous * Corresponding author. cognitive capabilities and energy budgets play the role of sec- E-mail addresses:

(N. Cordeschi),

(D. Amendola),

(M. Shojafar), ondary users and compete for acceding to the serving RSUs by

(E. Baccarelli). opportunistically exploiting the time and frequency holes of the http://dx.doi.org/10.1016/j.vehcom.2014.08.004 2214-2096/© 2014 Elsevier Inc. All rights reserved. 2 N. Cordeschi et al. / Vehicular Communications 2 (2015) 1–12 Fig. 1. The considered networked VCC infrastructure. The arrows refer to the downlink phase of each super-frame. RSU : Road Side Unit; CL : CloudLet; IG : Internet Gateway. traffic flow generated by the Service Provider (that is, the primary ited, for example by removing the data fusion module or keeping user of the Internet backbone). The pursued twofold objective is the client optimization and the MAC optimization decoupled. the joint maximization of the aggregate access goodput of the overall network, and the average per-client access rates. 1.2. Related work and outline of the paper 1.1. Technical contribution overview and main idea of the paper Passing to consider the related work, very few papers [4–6] on the cognitive scheduling for the V2I access have been published With respect to the technical contribution of the work and the so far. Specifically, Alcaraz et al. [4] assumes that the RSU knows novelty of the idea, the target of the paper is to optimize the ac- the connection lifetime of each served VC in advance, so as to cess throughput of the secondary user of the vehicular networks, give higher priority to the clients with less data to upload and/or while respecting the quality of service (QoS) requirements of the smallest remaining connection lifetime. This scheduling scheme, primary users, expressed in terms of maximum tolerated collision- although pioneering in exploiting some peculiar features of the V2I rate with the secondary users. From this point of view, the paper networks, is not specifically compatible with the IEEE802.11x stan- propose a new optimized medium access control (MAC) proto- dards and neglects to consider the link quality aspect. The latter is, col, able to maximize, under some assumptions detail below, the indeed, explicitly accounted for in [5,6], which develop optimized average aggregate throughput of the system. The proposed MAC IEEE802.11e compliant access scheduling policies supporting QoS protocol is new because of the following reasons: 1) it is a MAC differentiation. However, neither fading-induced energy constraints Protocol able to manage two different classes of users, it is scal- nor context-aware cognitive approaches are considered by these able, and from this point of view can be applied to any scenario contributions. of this form, not only the vehicular one we are here considering; Among the rich set of papers affording the more general topic 2) furthermore, unlike other approaches, we chose not to control of the resource management in Cognitive Wireless Mesh Networks just the collision probability among users, but the instantaneous (CWMNs), the contributions in [7–12] pursue solving approaches collision rate. We are motivated from the consideration of the which, as in our case, are inspired by the principle of the Network high time-varying nature of vehicular networks. In fact, more con- Utilization Maximization (NUM). Specifically, Bazerque and Gian- ventional approaches, even if they fulfill the collision probability nakis [7] present a distributed scheduling and resource allocation constraints, may incur in quite long transients, where the instanta- scheme for OFDMA-based CWMNs, which aims at maximizing a neous collision-rate is definitely too high, thus completely destroy- (suitably) weighted linear combination of the client rates. Although ing the information; 3) our MAC strategy takes fully into account the proposed scheme may represent a good starting framework for the energy, the parameters and the specific fading phenomena of the resource management in multicarrier CWMNs, the burst nature the vehicular wireless channels in the optimization framework; of the Internet traffic and the related queue aspects are not consid- 4) by introducing data-fusion techniques in our protocol, we al- ered in [7]. On the other hand, the solving approach of Urgaonkar low secondary users to use the information broadcasted from the and Neely [8] is based on the constrained stochastic optimization access point (AP) in order to optimize locally their queries, that and queue control, and, indeed, it is the most similar to that pur- is the requested throughput at the AP slot-by-slot, before the re- sued by our contribution. However, our work differentiates from source allocation decision is taken by the AP. This idea is somehow [8] under the following main aspects. First, the application scenario new, and couples the client throughput optimization with the MAC considered in [8] is fading-free, so that neither energy constraints problem. Our approach is able to make it solvable, and computa- and data fusion nor the effects of imperfect context information tionally tractable with a very low computational cost; 5) finally, are considered therein. Second, unlike our framework, Urgaonkar the proposed protocol is completely scalable, and can be used even and Neely [8] assume that each mobile client is equipped with an in rougher situations where the signaling exchange is more lim- infinite-capacity buffer. N. Cordeschi et al. / Vehicular Communications 2 (2015) 1–12 3 The COMNET paradigm in [9] formulates the channel assign- Table 1 ment problem as a suitable constrained NUM problem and, then, Main taxonomy of the paper. solves it in a distributed fashion. Although [9] and our contribution Symbol Meaning/role focus on the spectrally efficient opportunistic access in CWMNs, I, i Number of clusters and cluster index, they differ under the following main aspects. First, the COMNET i = 1, . . . , I paradigm in [9] requires reliable information about the relative N to , j, k Total number of VCs and VC indexes, locations of the wireless clients before performing channel assign- k, j = 1, . . . , N to ment. Second, the issues related to the fading phenomena, data fu- R, D Cluster radius and inter-RSU distance (m) sion, energy constraints, imperfect context-information and queue v, v max Average and maximum VC’s speeds (m/s) management are not considered by [9]. Finally, the burst nature T SF , T S , T C Super-frame, slot and mini-slot durations (s) of the of the traffic generated by the cognitive users is explicitly { f i , i = 1, . . . , I } Set of the available carrier frequencies (Hz) accounted for in [10–12]. However, they neglect fading effects, en- L E , L B , L D , L F , L S , LU , L A Lengths (in mini-slot) of the access protocol ergy constraints and mobility-related issues. phases (see Fig. 2) According to the above overview, the main contributions of C i (t ), N Set of VCs in cluster i at slot t, and Per-cluster this work may be so summarized. First, in Section 2 we describe average number of VCs the considered networked vehicular infrastructure, and detail the ai (t ) Binary variable indicating the presence/ main components and signaling flow of the proposed CR-based absence of the primary user in cluster i at access protocol which is able to support a fully distributed and slot t scalable implementation of the proposed optimal joint controller. xi (t ), νi Primary-secondary collision rate and its Section 3 formally introduces the tackled resource constrained maximum tolerated value in cluster i network-wide optimization problem and points out its structural λ j (t ), r j (t ), q j (t ) Input flow (IU/slot), transmission rate (IU/slot) constraints, specifically, the hard constraint on the instantaneous and queue length (IU) of VC ( j ) at slot t primary-vs.-secondary packets collision rates and average/peak en- E j (t ) Transmit energy of VC ( j ) in slot t (Joule/slot) ergy consumptions. Then, before proposing our solution, in Sec- j j j N max , Eave , E P , Eidle j Buffer size (IU) and average, peak and idle tion 4 we develop a novel form of soft-input/soft-output data fu- energies (Joule/slot) of VC ( j ) sion that improves the final reliability of the context information Ψ ji (t ) Fraction of the access time-window assigned which is acquired by the VCs, in order to cope with the limited to VC ( j ) by RSU (i ) at slot t sensing capability of the VCs. This optimized data-fusion technique R j (·), ε j (·), u j (·) Rate function (IU/slot), Energy function is then exploited for implementing the resulting network-wide re- (Joule/slot) and utility acquired by VC ( j ) source management in Section 5, where we develop the analytical gd Network-wide average aggregate access closed-form expressions for the optimal joint control of the traf- goodput (IU/slot) fic flows, access rates, client scheduling and assignment of the access time-windows, and its on-the-fly version able to quickly phase and a downlink phase, whose (possibly, unequal) relative adapt to the abrupt and unpredictable mobility-induced changes time-durations are tuned at the network setup. In the following, of the instantaneous state of the vehicular network. Finally, Sec- we focus on the (typically mostly frequency limitation affected) tion 6 describes the simulated vehicular scenario and presents the downlink phase of each super-frame, and consider the related pack- numerical results of several tests and performance comparisons, ets collision phenomena possibly occurring at the serving RSUs. and Section 7 concludes our paper. Proofs of the main results are During this phase, RSU (i ) exploits the carrier frequency f i for reported in Appendices A–C. simultaneously receiving the backbone traffic flow generated by About the adopted notation, scalar random variables (r.v.’s) are RSU (i − 1) and the access traffic offloaded by the currently served denoted by bold characters, while their outcomes are indicated by VCs (see the arrowed rays of Fig. 1). Since the backbone traffic the corresponding italic symbols. E {. . .} is the expectation opera- may convey safety-related information [13], it must retain a prior- tor, R+ 0 is the set of the non-negative real numbers, C denotes the ity level higher than the access traffic generated by the served VCs, set of the complex numbers, means equal by definition, [x]+ so that RSU (i − 1) is the primary user of the carrier frequency f i , max{x; 0}, and p s (a) is the probability density function (pdf) of the while all VCs traveling over cluster(i ) play the role of secondary r.v. s evaluated in a. Finally, E s {ϕ (s; x)} ϕ (s; x) p s (s)ds is the ex- users. The following binary variable: pectation of the bi-argument function ϕ (s; x) done over the pdf of the r.v. s, while [ f (x)]ab indicates max{a; min{ f (x); b}}. 1, if RSU (i − 1) transmits in slot t , ai (t ) (1) 0, otherwise, 2. The considered vehicular networked infrastructure and the proposed CR-based V2I access protocol is the indicator function of the transmit activity of the primary user RSU (i − 1) of cluster(i ) at slot t, and The main building blocks of this architecture are reported in P ai (t ) = 1 γi , i = 1, . . . , I , (2) Fig. 1. Specifically, a number I ≥ 2 of static (or, at most, movable) RSUs are deployed along the road and are evenly spaced apart of is the corresponding steady-state a priori probability. In the fol- D (m). Each RSU serves a spatial cluster of radius R (m), and acts lowing, C i (t ) ⊆ {1, . . . , N to } denotes the set of VCs which, at slot t, both as Access Point (AP) for the VCs currently traveling on the stay over the i-th cluster. Table 1 reports the main taxonomy used served cluster and relay node of the wireless backbone. In Fig. 1, in this paper. time is slotted, T s (s) is the slot duration, t is the discrete-time slot index. The VCs of Fig. 1 may change their spatial positions and the 2.1. The CR-based V2I access protocol network nodes may start to transmit only at the beginning of each slot t. In order to support the CR-based access of the VCs to the serv- In order to cope with the aforementioned bandwidth limita- ing RSU in a fully distributed and scalable way, we propose the tion, the communication traffic over the wireless backbone of Fig. 1 intra-cluster access protocol detailed in Table 2, where the adopted is Time Division Duplexed (TDD) and it is organized into super- frame format is reported in Fig. 2. The slot of duration T s is par- frames of duration T SF (s). Each super-frame comprises an uplink titioned into an integer number L t of non-overlapping mini-slots 4 N. Cordeschi et al. / Vehicular Communications 2 (2015) 1–12 Table 2 The proposed intra-cluster access protocol. Access protocol steps 1. Beacon broadcasting and channel estimation phase: each VC ( j ), j ∈ C i (t ), autonomously calculates own channel state estimate on the basis of the broadcast beacon. 2. Belief propagation phase: RSU (i ) updates P (ai (t )|Γi (t )) (see (21)). 3. Channel detection and sensing phase: each VC ( j ), j ∈ C i (t ), autonomously calculates own binary decision aˆ ji (t ) about the presence/absence of primary user activity (see (22)). 4. Data fusion phase: each VC (k), k ∈ C i (t ) sends to the serving RSU (i ) the set of probabilities in (24). Then, RSU(i ) computes P iL (t ) as in (26) and broadcast it over the served VCs. opt 5. Resource allocation and client scheduling phase: each VC (k), k ∈ C i (t ), autonomously computes own desired access rate rk (t ) as in (27) and sends the access opt query to the serving RSU(i ). Afterwards, RSU(i ) computes the optimal window sizes {Ψki (t )} (30) and broadcasts them to the served VCs. 6. Clients upload phase: each VC ( j ), j ∈ C i (t ), uploads to the serving RSU (i ) the contracted number: η0 r opt opt j (t )Ψ ji (t ) of IUs over own reserved time-window. 7. ACK/NACK phase: RSU (i ) acquires the value of the primary–secondary collision variable c i (t ), and, then: (i) it computes xi (t + 1) as in (4); and, (ii) it broadcasts the ACK/NACK variable Z iA (t ) 1 − c i (t ) over the served VCs. After receiving Z iA (t ), each VC ( j ), j ∈ C i (t ), computes the acquired utility u j (t ) in (5), and, then: opt (i) it computes λ j (t ) as in (31); and, (ii) it updates q j (t + 1) as in (8). Fig. 2. Frame format for the intra-cluster access. Orange (respectively, azure) boxes indicate tasks involving only the serving RSU (respectively, the served VCs), while mixed orange–azure boxes indicate hybrid tasks. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.) of duration T c T s / L t . According to Table 2, these seven phases ware and clear-sky line-of-sight, energy consumption, signal losses, span L E , L B , L D , L F , L S , L U and L A mini-slots, respectively. More- scarce scalability and possible time wasting. The more autonomous over, since only the L U mini-slots of the client upload phase are Timing Synchronization Function (TSF) of the IEEE 802.11 standard devoted to convey the access traffic, the fraction η0 of the overall is an alternative. Several papers, like [14,15], propose distributed slot used for traffic uploading (i.e., the protocol efficiency) equates and autonomous network time-synchronization (NTS) approaches η0 L U / Lt . for the support of QoS-aware protocols in mobile wireless net- As it can be recognized from an inspection of Table 2, the works that make no use of master clocks external or internal to tackled vehicular optimization problem is inherently of cross-layer the network, and the exchange of timing information is performed type and it jointly embraces the APPlication (APP), Medium ACcess through the periodic transmission of beacons compliant with IEEE (MAC) and PHYsical (PHY) layers of the underlying protocol stacks. 802.11. Due to the need of scalable and local NTS approaches, the Specifically, from an optimization point of view in this paper we beacon broadcasting and channel estimation phase of our protocol focus on 1) the Data fusion phase (and the related Belief propaga- in Table 2 is also devoted to beacon signal synchronization, and ex- tion and Channel detection and sensing phases), 2) the VC resource ploits these decentralized local pulse strategies that let VCs align allocation and optimal planning of the clients desired access rates, locally the timing of their packet transmissions. 3) the optimal RSU window-size allocation and client scheduling phase, while the other phases of the protocol (beacon broadcasting 2.1.2. Remark about the payload length L U and channel estimation phase, and VCs-RSU exchange information, About the protocol efficiency of the system and the manage- and the ACK/NACK phase) are part of the proposed protocol and ment of the payload phase, we explicitly remark that even is the are implemented in the simulation result scenario to test the over- length of the payload protocol phase L U can be considered vari- all efficiency. able slot-by-slot and we can generalize the proposed approach to a protocol with variable payload length, in the following and in 2.1.1. Synchronization between VCs and RSU the numerical results section we consider a constant L U . In fact, About the fundamental problem of achieving network time- since our access system is able to manage the time-varying vehic- synchronization (NTS) in the presence of node mobility, some ex- ular network parameters and optimize frame-by-frame the access isting implementations for vehicular networks assume the avail- speed of each VC, there is no need to consider variable frame-by- ability of common (external) sources of time, such as geographical frame the parameter L U . This solution allows fixed length frames, positioning systems (GPS). As in [14] we outline that NTS is one of that helps the recovery of synchronism among the RSU and the the foundations over which mechanisms at all levels of the proto- VCs, that as we said previously is a fundamental problem in pres- col stack can build better Quality of Service (QoS) solutions. The ence of node mobility. majority of Medium Access Control (MAC) protocols that try to satisfy the QoS requirements of real-time applications (e.g., voice, 3. The resource-constrained network-wide optimization streaming video) utilize a slotted-time structure, assumed to be problem achievable through the atomic clocks located in the GPS satellite (Q ) network. However, depending on GPS signals is, in most cases, Let r j (t ) (IU /slot) be the access query, that is, the desired less flexible and more costly due to the need of additional hard- access-rate at which VC ( j ) requires to transmit at slot t (more N. Cordeschi et al. / Vehicular Communications 2 (2015) 1–12 5 Fig. 3. Queue model for the access link: VB( j ) → RSU (i ). briefly, in the following, we also indicate it as r j (t )). Formally corresponding access channel: VC ( j ) → RSU (i ).) The cost to sup- (Q ) port the communication rate r j (t ) is the corresponding energy speaking, r j (t ) is the number of IUs uploaded by VC ( j ) over a time interval equal to a full slot time T s , when VC ( j ) is scheduled E j (t ) (Joule/slot) consumed by VC ( j ) for the transmission. Hence, for the access and primary–secondary packet collisions do not oc- r j (t ) depends on E j (t ) through the rate function R j (·) which is cur. During this phase, RSU (i ) allocates fractions {Ψ ji (t ) ∈ [0, 1]} of adopted for measuring the instantaneous throughput (in (IU/slot)) the overall slot time T s to the VCs currently traveling over the i-th sustained by the j-th access link, so that we can write: cluster. Afterwards, the scheduled VCs accede to the serving RSU (i ) r j (t ) R j E j (t ), s j (t ), P Li (t ) , (6) during the fractions of the time-slot allocated to them, which com- pose the next Upload phase. Lastly, the serving RSU (i ) detects the where P Li (t ) is the a posteriori probability of no primary user ac- possible occurrence of primary–secondary collisions. According to tivity at slot t in the cluster where VC ( j ) is currently traveling these assumptions, let c i (t ) be the indicator function of primary– (see Section 4 and (25), (26) for its formal definition and opti- secondary collision at slot t (that is, c i (t ) = 1 if primary–secondary mized computation). From an analytical point of view, R j (.) is a collision is detected at slot t in cluster(i ), and c i (t ) = 0, otherwise), non-negative real-valued function strictly increasing for increasing and let energy E j and concave in the E j -variable. These basic assump- t −1 tions are typically retained by all rate functions of practical in- 1 xi (t ) c i (τ ) (3) terest [16]. According to the considered rate function R j (·), in t−1 the sequel, we indicate by E j (t ) ≡ ε j (r j (t ), s j (t ), P Li (t )) R−1 τ =1 j (.), (Joule/slot) the per-slot energy to be radiated by VC ( j ) for sus- be the value of the collision rate computed by RSU (i ) at the begin- taining the transmission rate r j (t ), with R− j 1 (·) being the inverse ning of slot t. Hence, at the end of the ACK phase, RSU (i ) updates the collision rate as in of R j (·) with respect to the E j -argument. Interestingly, the ex- perimental results reported in [17] support the conclusion that xi (t + 1) = (1/t ) c i (t ) + (t − 1)xi (t ) , xi (1) = 0, t ≥ 1, (4) the energy-vs.-transmission rate relationships dictating the energy consumptions of WiFi, 3G and 2G access real-life connections may and, as a primary–secondary packet collision notification, RSU (i ) be suitably described by the following linear-type models (see Ta- broadcasts the variable: Z iA (t ) 1 − c i (t ). In the following, we in- opt ble 1 of [17]): dicate by r j (t ) the optimal VC ( j ) desired access rate, locally opti- s j P L ( j) j j mized by the vehicular client. Therefore, r j (t ) η (U ) opt opt 0 r j (t )Ψ ji (t ), j R j E , s j , P L ( j) = E − Eidle , j for E j ≥ Eidle , (7) ke j ∈ C i (t ), is the traffic flow transmitted by VC ( j ) at slot t, while we define as u j (t ) the instantaneous utility (in the following, we also where ke (measured in (Joule/IU/slot)) is the per-slot incremental refer to it as goodput) of the VC ( j ), that is, the traffic flow actually energy which is required for the transmission of an additional IU. uploaded by VC ( j ) at slot t and received without collisions: Finally, Fig. 3 reports the G /G /1/ N max j fluid queue model of the opt opt access link going from the served VC ( j ), j ∈ C i (t ), to the serving u j (t ) η0 r j (t )Ψ ji (t ) 1 − c (t ) , j ∈ C i (t ). (5) RSU (i ). Specifically, let q j (t ) (IU) be the backlog of the j-th queue of Fig. 3 at the beginning of slot t, with q j (t ) ≤ N max j . After receiv- After receiving the ACK signaling, VC ( j ) removes from its queue a (possibly, vanishing) number u j (t ) of IUs. ing the ACK signaling, VC ( j ) removes from its queue a (possibly, About the vehicular client and channel models, let h j (t ) ∈ C vanishing) number u j (t ) of IUs and, then, at the end of slot t, it be the complex-valued baseband equivalent representation of the injects into the queue a number of new IUs equal to λ j (t ), with random gain of the fading-affected pass-band downlink channel: λ j (t ) ≤ λmax j . Hence, the time evolution of the j-th queue of Fig. 3 RSU (i ) → VC ( j ) from the serving RSU (i ) to the served VC ( j ), and is dictated by the following buffer equation [18]: let s j (t ) G j (h j (t )) be the corresponding channel state (such as, q j (t + 1) = q j (t ) − u j (t ) + λ j (t ) + . (8) for example, s j (t ) = h j (t )2 ). In the following, we assume the channel coefficient remains constant over the slot interval t. (Since Under the model and definitions presented above, the afore- channel reciprocity holds, s j (t ) also describes the behavior of the mentioned network-wide resource limitations and reliability de- 6 N. Cordeschi et al. / Vehicular Communications 2 (2015) 1–12 mands are formally captured by the following list of constraints, would know in advance the set of the pdfs: { p sˆ j (·), j = 1, . . . , N to } for t ≥ 1: of the access links of all VCs currently traveling over the overall network of Fig. 1 for performing the corresponding optimal re- xi (t + 1) ≤ νi , (9) source allocation. Second, we note that since strictly increasing opt E s j ε j r j (t ), s j (t ), P Li (t ) q j (t ), j transformations preserve the ordering, the optimal solution rk (t ) P Li (t ) ≤ Eave , (10) of the problem in (17), (18) remains unchanged when rk (t ) in (17) ε j r j (t ), s j (t ), P iL (t ) ≤ E P , j (11) is replaced by the more general objective function: w k (rk (t )), pro- vided that w k (·) is a strictly increasing function of rk . Ψ ji (t ) ≤ 1, 0 ≤ Ψ ji (t ) ≤ 1, (12) j ∈Ci (t ) In the sequel, we present the optimized soft-input/soft-output j j 0 ≤ q j (t + 1) ≤ N max , 0 ≤ λ j (t ) ≤ λmax , (13) Data fusion technique, then we pass to detail the optimal solutions of the previously defined ARA and CTFA problems. 0 ≤ η0 r j (t ) ≤ q j (t ). (14) Specifically, the constraint in (9) limits in a hard way the in- 4. Optimal soft-input/soft-output data fusion stantaneous primary–secondary collision rate in the i-th cluster up to νi , so to provide hard reliability guarantees to the corresponding Target of this section is the description of the Belief propagation primary user RSU (i − 1) of cluster(i ) (see Fig. 1). Eqs. (10) and (11) and Channel detection phases, and the optimization of the Data limit on a per-slot basis the average and peak energies available fusion phase, in order to produce the optimized P iL (t ) that will be at VC ( j ), respectively, while the constraint in (12) guarantees that exploited in the following section by the previously defined ARA RSU (i ) assigns non-overlapped time-windows to the VCs scheduled and CTFA problems, so to produce the optimal cognitive controllers. for the access. Finally, the box constraints in (13), (14) clip the in- a) Belief propagation. Let Γi (t ) be the (possibly, empty) set of infor- stantaneous backlog and input flow of the j-th queue of Fig. 3 up mation about the past activity of the primary user RSU (i − 1) avail- j j to N max (IU) and λmax (IU/slot), and limit the number: η0 r j (t ) of able at RSU (i ) at the beginning of slot t. According to the aforemen- IUs which may be removed at the end of slot t from the j-th queue tioned considerations, task of the Belief propagation is to update of Fig. 3 up to the current queue backlog q j (t ), respectively. the corresponding a posteriori probability: P (ai (t ) = 1|Γi (t )) on Hence, the considered Network-wide Optimization Problem (NOP) the basis of the currently available information set Γi (t ). Various can be now defined as: cooperative or not cooperative Belief propagation algorithms may N be used. In our framework, in order to consider a scheme that to opt max θ j E u j (t ) rk (t ), k = 1, . . . , N to , (15) does not require inter-RSU information exchange, at the beginning {λ j (t ),Ψ ji (t )} of slot t RSU (i ) autonomously updates the transmission rate of its j =1 primary user RSU (i − 1) as in (see (1)) s.t.: Eqs. (9), (12), (13). (16) t −1 opt 1 In (15), θ j > 0 is the relative priority level of VC ( j ), while is rk (t ) F i (t ) ai (l) . (21) the k-th optimal offload (e.g., access) rate. This is, in turn, formally t−1 l =1 defined as the solution of the following k-th Access Rate Allocation Problem (k-th ARAP): In this case, therefore, we have Γi (t ) ≡ {ai (l), l ≤ (t − 1)}. Moreover, since F i (t ) approaches γi for growing t, RSU (i ) may use the cur- max E rk (t ) qk (t ) , (17) rently computed F i (t ) as a (reliable) estimate of the corresponding {rk (t )} (a priori unknown) activity probability γi . s.t.: Eqs. (10), (11), (14). (18) b) Channel detection and Data fusion. During the channel detection In order to compute the solution of opt opt opt {r j (t ), Ψ ji (t ), λ j (t )} and sensing, each served VC ( j ), j ∈ C i (t ), autonomously performs (15)–(18), we point out that, in [19], it is proved that, without loss channel sensing in order to detect the presence/absence of ongo- of optimality, the NOP is (15) may be recast into I parallel and in- ing transmission by the corresponding primary user RSU (i − 1) (see dependent sub-problems over the index i ∈ I . Specifically, at each t, Fig. 1). On the basis of these observations, VC ( j ) autonomously RSU (i ) autonomously solves the i-th Combined Time-Flow Allocation computes the following binary decision, for j ∈ C i (t ): Problem (i.e., the i-th CTFAP), which is formally defined as: 1, if VC ( j ) detects primary transmissions at slot t , aˆ ji (t ) opt 0, otherwise, max θ j E u j (t ) rk (t ) , (19) {λ j (t ),Ψ ji (t ), j ∈C i (t )} (22) j ∈C i (t ) s.t.: Eqs. (9), (12), (13). (20) about the presence/absence of transmit activity by RSU (i − 1) dur- ing the current slot t. The reliability level of the decision in (22) is measured by the corresponding Miss Detection probability and Remark 1. On the formulation of the NOP and ARAP False Alarm probability: In order to gain insight about the reported formulations of the NOP and ARAP, the following two remarks may be useful. First, the ji P md P (ˆa ji = 0|ai = 1), ji P f a P (ˆa ji = 1|ai = 0), (23) number of variables to be optimized on a per-slot basis is 3N to and, then, it scales up linearly with the (possibly, large) number that depend on the statistics of the fadings, the operating SNR, of the supported VCs. At this regard, we anticipate that the condi- the decision rule adopted by VC ( j ) for generating the decision tional expectation present in the objective function in (15) allows in (22) and the number of sensed observations. In order to each RSU to allocate the access resource to the currently served shorten the notation, let us pose: p j |0 (t ) P (ˆa ji (t )|ai (t ) = 0) and {VC ( j ), j ∈ C i (t )} in a fully distributed and scalable way. Due to the p j |1 (t ) P (ˆa ji (t )|ai (t ) = 1). Hence, after computing its binary de- constraints in (10) on the average energies of the served VCs, the cision aˆ ki (t ), VC (k) autonomously sends to the serving RSU (i ) the scalability property of the optimal resource allocation is lost when pair of real values the conditional expectation in (15) is replaced by the correspond- ing unconditional one: E {u j (t )}. In fact, in this case, each RSU p j |0 (t ), p j |1 (t ) , (24) N. Cordeschi et al. / Vehicular Communications 2 (2015) 1–12 7 instead of only the (rough) binary value aˆ ki (t ). This pair of prob- 5. Optimal adaptive and distributed joint resource controller abilities only depends on the performance of the sensing device ji ji equipping VC (k), and we have { p j |0 (t ), p j |1 (t )} = {(1 − P f a ), P md } In this section, we detail the optimal solutions of the previously ji ji when aˆ ji (t ) = 0, and { p j |0 (t ), p j |1 (t )} = { P f a , (1 − P md )} when defined ARA and CTFA problems. aˆ ji (t ) = 1. Afterwards, RSU (i ) performs the optimal fusion of all data: 5.1. Optimal control of the vehicular access rates V i (t ) {{ˆa ji (t )} j ∈C i (t ) , Γi (t )} currently gathered about the pres- ence/absence of primary user activity, in order to compute the Let ε˙ k (·) ∂ εk (·)/∂ rk be the derivative of the energy-rate func- following a posteriori probability: tion εk (·) of VC (k) with respect to the rate variable rk and let ε˙ k−1 (·) be the corresponding inverse function done with respect P Li (t ) P ai (t ) = 0 V i (t ) . (25) to rk . Hence, after recognizing that the k-th ARAP in (17)–(18) is a opt convex optimization problem, the resulting optimal solution rk (t ) At the end of the phase of the channel detection and sensing, may be autonomously computed by VC (k) as reported by the fol- RSU (i ) autonomously computes the a posteriori probability P Li (t ) lowing Proposition 2. in (25) by optimally fusing the set of information about the pres- ence/absence of primary user activity provided by the currently Proposition 2. Under the above reported assumptions, VC (k) au- served {VC ( j ), j ∈ C i (t )}. The optimal fusion is performed as de- tonomously computes the solution of the k-th ARAP in (17)–(18) ac- tailed by the following Proposition 1. cording to the following relationship: Proposition 1. Under the above reported assumptions, the optimized 1 rk (t ) = min ε˙ k−1 , sk (t ), opt P i (t ) in (25) is provided by: L P iL (t ), , r kP (t ) (27) μk (t ) + (1 − F i (t )) j ∈C i (t ) p j |0 (t ) P Li (t ) = . (26) where, by definition, r kP (t ) min{ kη ; Rk (E Pk , sk (t ), q (t ) P Li (t ))} (IU /slot) (1 − F i (t )) j ∈C i (t ) p j |0 (t ) + F i (t ) j ∈C i (t ) p j |1 (t ) 0 is the peak transmit rate of VC(k) at slot t. Furthermore, the real-valued non-negative μk (t ) parameter in (27) resists closed-form solution and, Proof. For brevity we omit in the proof the subscripts j ∈ C i (t ), which is the most, it is related to (10), so that its the closed-form evalua- and we indicate the event ai (t ) = 0/1 only by 0/1, so that, af- tion would require that the mobility-depending steady-state pdf p sk (·) is ter introducing the defining relationship of the set V i (t ) into (25), a priori available at VC (k). Hence, in order to evaluate μk (t ) on-the-fly, we can write: P Li (t ) P (0|Γi (t ), {ˆa ji (t )}), that can be rewritten we resort to the stochastic gradient projection algorithm [21]: as the following ratio: P ({ˆa ji (t )}, 0|Γi (t ))/ P ({ˆa ji (t )}|Γi (t )). Then, P ({ˆa ji (t )}|Γi (t )) is equal to: P ({ˆa ji (t )}, 0|Γi (t )) + P ({ˆa ji (t )}, 1|Γi (t )), k μk (t ) = μk (t − 1) − ζk (t − 1) Eave − E k (t − 1) + , (28) while, furthermore: P ({ˆa ji (t )}, 0|Γi (t )) = P ({ˆa ji (t )}|0) P (0|Γi (t )) (where the same chain stems for ai (t ) = 1). This result stems where {ζk (t )} is a suitable non-negative step-size sequence (in our sim- from the fact that Γi (t ) only accounts, by design, for the informa- ulation results we use the updating step-size provided in [22, Eq. (2.4)]), tion about the presence/absence of primary user activity acquired t −1 while: E k (t − 1) t −1 1 ( i =1 E k (i )) is the time-averaged energy actu- by RSU (i ) through Belief propagation, so that the conditioning of ally consumed by VC (k) up to (t − 1)-th slot. The interesting features {ˆa ji (t )} on ai (t ) suffices. Finally, from the assumption that the fad- of (28) are that the sequence {E k (t )} implicitly accounts for the (a pri- ing phenomena affecting different access channels are mutually ori unknown) mobility-depending pdf p sk (·) , and Eq. (28) can be au- independent in the spatial domain (that is, with respect to the j tonomously updated by VC (k) on a per-slot basis. From a formal point index), according to [20, Chapter 3] the corresponding conditional of view, Proposition 8.1 of [21] guarantees that, in the steady-state, joint probability: P ({ˆa ji (t )} j ∈C i (t ) |ai (t )) factorizes into the corre- the stochastic gradient-based iterates in (28) converge to the optimum, sponding marginal ones, and we obtain (26). 2 because the Laws of the Large Numbers assures that, in the steady- state, the time averages E k (t ) converge to the corresponding expecta- Finally, at the end of the phase of data fusion, the serving tion Eave k . RSU (i ) broadcasts the computed value of P Li (t ) over all currently served {VC ( j ), j ∈ C i (t )}. 5.2. Optimal distributed control of the access windows and client flows As a remark to the adopted data fusion strategy, according to [20] we point out that data fusion operations are traditionally cat- egorized as hard (respectively, soft) when the VCs provide hard Let (respectively, soft) decisions to the serving RSU, while, in both i opt cases, the serving RSU (that is, the data fusion point) feedbacks j max (t ) arg max θk rk (t ) , i = 1, . . . , I , (29) hard information. Interestingly, a peculiar feature of our framework k∈C i (t ) is that all the data provided by the served VCs and the correspond- be the (possibly, not unique) index of the VC which, at slot t, max- ing ones feedback by the serving RSU are soft, so that (26) may imizes the utility acquired by the access network of Fig. 1. Hence, be considered as a (novel) instance of a soft-input/soft-output data after denoting by δ(m) the Kronecker delta (e.g., δ(m) = 1, for fusion. Furthermore, we explicitly note that VCs may utilize the re- m = 0 and δ(m) = 0 for m = 0), in Appendices B and C it is proved ceived information about P Li (t ) as a further parameter to shape that the solution of the i-th CTFAP in (19)–(20) reads as reported their access query to the RSU, or as a feedback for their channel- by the following Proposition 3. detection. We do not address here this issue, while in the next section we focus in detail on the way RSU (i ) uses P Li (t ) (jointly with the other system parameters) to properly plan the VC access Proposition 3. Under the above reported assumptions, for the solution time windows. The optimal data fusion algorithm adopted for com- of the i-th CTFAP in (19)–(20) we have that: puting the probability in (25) is a building block of our optimal a) for j ∈ C i (t ), the access time-windows are optimally allotted by cognitive controller. the serving RSU(i ) according to: 8 N. Cordeschi et al. / Vehicular Communications 2 (2015) 1–12 Table 3 Main simulated parameters for the homogeneous application scenario of Section 6. I =3 L S = 200 (minislot) Eidle = 35 (mJ/slot) L t = 105 (minislot) R = D /2 = 250 (m) L B = 0 (mini slot) β = 0.5 L A = 50 (minislot) E P = 3Eave (mJ) N = 40/3 (client/slot) SNR = 20 (dB)@d = 15.5 (m) L F = 750 (minislot) N max = 1 (MB) T S = 100 (ms) θ = 1, l = 2 γ = 0.5 λmax = 240 (KB/slot) L E = 1500 (minislot) ke = 0.07 (mJ/KB/slot) B = 5 (MHz) P md = 9 · 10−4 , P f a = 10−1 P md = 1.2 · 10−3 , P f a = 5 · 10−2 P md = 3.5 · 10−3 , P f a = 10−2 P md = 6 · 10−3 , P f a = 10−3 ⎧ ν i t −1 ⎪ ⎪ 0, for ( P iL (t ) = 0) or xi (t ) > stemming from the resolution of the considered NOP in (15)–(16) ⎪ ⎪ t −1 ⎪ ⎪ ⎪ ⎨ and 0 < P iL (t ) < 1 , is amenable of fully distributed and scalable implementation. This opt t −1 means, in turn, that both the per-VC and per-RSU implementa- Ψ ji (t ) = δ( j − j max i (t )), for xi (t ) ≤ νti − (30) tion complexities do not depend at all on the number I of deployed ⎪ ⎪ 1 ⎪ ⎪ and 0 < P i (t ) < 1 , clusters and the total number N to of the served VCs. Second, each ⎪ ⎪ ⎪ ⎩ L VC is capable to autonomously adapt to the (possibly) abrupt and δ( j − j max i (t )), for ( P iL (t ) = 1); unpredictable changes of the statistical properties of the vehicu- b) the optimal value of the traffic flow injected by VC( j ) into its buffer lar network by locally implementing the iterates in (28), which at the end of slot t is do not require the a priori knowledge or forecasting of the pdf of the available link state s. Third, by design, the signaling overhead opt opt λ j (t ) = min N max j − q j (t ) + u j (t ) ; λmax j , j ∈ C i (t ), (31) needed to support the resulting access protocol of Table 2 is com- putable in closed-form and equates: (1 − η0 ). At this regard, we opt opt opt where u j (t ) η0 r j (t )Ψ ji (t ) Z iA (t ), j ∈ C i (t ), is the (possibly, van- anticipate that, at least in the carried out numerical tests of Sec- ishing) traffic flow actually uploaded by VC ( j ) at slot t. tion 6, signaling overheads limited up to 4% suffice for attaining the ultimate access goodput supportable by the simulated vehicu- Interestingly, an examination of (30) and (31) unveils that lar networks. opt opt {Ψ ji (t )} and λ j (t ) can be autonomously computed by RSU (i ) and VC ( j ), respectively. Hence, the joint optimal solution of the i-th 6. Simulated scenario and performance tests CTFAP reduces, indeed, to separately solve the problem of the al- location of the access time-windows and that of the flow control. In the carried out tests, we consider a homogeneous networked opt Furthermore, as pointed out by (5), the variables {Ψ ji (t ) Z iA (t ), j ∈ vehicular infrastructure, where all RSUs and VCs exhibit the same C i (t )} which are broadcast by RSU (i ) over its served VCs at the performance capabilities and mobility features (see Table 3). end of slot t (see Step (7) of Table 2) play the role of coupling variables between the access time-window and the flow-control 6.1. Simulated client mobility, primary activity pattern, faded access optimization problems. channels and channel sensing Before proceeding, some remarks about the structural proper- ties retained by the optimal controllers in (30) and (31) may be of As in Section 3.2 of [23], we resort to the so called Markovian interest. random walk with random positioning for simulating the VC mobil- ity. According to this model, at the beginning of slot time t, each Remark 2. On the structural properties of the optimal controller of VC autonomously moves to the next cluster with spatial transi- the access time-windows tion probability β , or stays in the current cluster with probabil- About the optimal access control, roughly speaking, the con- ity (1 − β). Furthermore, the simulated activity process {ai (t ) ∈ troller in (30) allows the access to the serving RSU (i ) when at least [0, 1], t ≥ 0} of the primary user RSU (i − 1) of the i-th cluster one of the conditions reported in the second and third rows of (30) of Fig. 1 is dictated by a spatially homogeneous stationary bi- is met, that is, when the instantaneous hard constraint in (9) on nary Markov chain with symmetric transition probabilities, where the i-th collision rate is guaranteed to hold, even if an additional γ ≡ P (ai (t ) = 1) is the steady-state activity probability of each pri- collision was to be occurred at slot t. Furthermore, when the ac- mary user. cess is allowed, the VC enabled to upload its data is the one which According to the measurement results of [24] for the character- maximizes the utility acquired by the network (see the second and ization of vehicular physical channels, in the carried out tests, we third rows of (30)). We anticipate that the numerical results of assume frequency-flat block-type Ricean fadings, with K Rice = 6.5 Section 6 point out that the constraint in (10) on the average en- (dB) being the Ricean factor of the considered access channels, ergy acts as an effective incentive for attaining fair access, even in and N v ( j ) (Watt/Hz) and l = 2 being the level of the receive noise the presence of low mobility. At this regard, it is understood that, power density spectrum and the path loss exponent of the j-th ac- when multiple VCs attain the maximum in (29), non-overlapped cess channel, respectively. Finally, N v ( j ) is tuned so as to have an access time-windows of equal duration are assigned them. average SNR j E {h j 2 }/ N v ( j ) of 20 (dB) at the VC-to-RSU dis- tance of 15.5 (m). About the simulated channel sensing algorithm, Remark 3. Implementation complexity, scalability and signaling the P md -vs.- P f a relationship is dictated by the numerical measure- overhead ments provided by [25] and reported in the last row of Table 3. About the implementation complexity of the overall joint con- troller, an examination of the expressions in (27), (28), (30) and 6.2. Numerical performance evaluation (31) leads to three main conclusions. First, since each VC is capa- ble to autonomously update its access rate and input flow through As in Table 1 of [17] the simulated rate function is the linear (27) and (31) respectively, while each RSU autonomously controls one in (7), with ke = 0.07 (mJ/KB/slot) and Eidle = 35 (mJ/KB). The the access of the served VCs according to (30), the joint controller metric adopted for measuring the network-wide performance of N. Cordeschi et al. / Vehicular Communications 2 (2015) 1–12 9 Fig. 4. (a) Behavior of the average aggregate offloaded goodput for various values of L D at ν = 0.05 and Eave = 60 (mJ/slot) for the application scenario of Section 6; (b) Average aggregate offloaded goodput-vs.-average per-client energy at ν = 0.05 and L E = L D = 1500; (c) Average aggregate goodput-vs.-per-client average energy for different values of the tolerated collision rate ν . Case of N = 1 (client/cluster). the simulated system is the per-slot aggregate offloaded goodput Table 4 gd (IU/slot), formally defined as in Numerically evaluated Jain’s fairness indexes of the per-client goodput for the ap- plication scenario of Section 6.d. N to opt 1 N to t opt Time-slot index t Average fairness index Average fairness index gd E θ j u j (t ) ≡ lim θ j u j (τ ). (32) at β = 0.1 at β = 0 t →∞ t j =1 j =1 τ =1 500 0.91 0.88 1000 0.96 0.92 a) Goodput-vs.-data fusion reliability. About the goodput-vs.-channel 1500 0.98 0.94 sensing reliability, in principle, larger values of L D improve the accuracy of the data fusion operation, but they also reduce the re- sulting protocol efficiency η0 . At this regard, the plot of Fig. 4(a) for the same application scenario we presented, at N to = 40 (i.e., leads to two main conclusions. First, the goodput-vs.-L D plot N = 40/3 (client/cluster)) and Eave = 60 (mJ/slot), we have numeri- presents a “bell-shaped” behavior, which is picked around the cor- cally evaluated the Jain’s fairness index of the average per-client responding optimized value of L D . Second, at least in the simulated goodput at slot times t = 500, 1000 and 1500 for the cases of scenario, the setting L D = 1500 stems out as the most performing β ≡ v¯ / v max = 0.1 (case of low mobility) and vanishing β (the static one. case). The obtained results have been averaged over 100 indepen- dent runs and the final averaged values are reported in Table 4. b) Goodput-vs.-energy performance. Task of the numerical results of Interestingly, the third column of Table 4 points out that, after this sub-section is to point out the effects on the goodput satu- 1500 slot-times (that is, 150 (s) in our simulated framework), a ration level induced by the per-cluster average number of clients ¯ (client/cluster). At this regard, Fig. 4(b) shows that, at fixed N¯ , fraction of about 94% of the VCs attains fair access, even when N mobility is absent. the aggregate offloaded goodput tends to increase for growing val- ues of the available per-client average energy Eave . Interestingly, e) WiFi-vs.-3G energy performance. In agreement with the analyt- Fig. 4(b) points out that, at fixed Eave , the aggregate offloaded ical model reported in Table 1 of [17], we resort to the linear- goodput increases for increasing N ¯ up to a saturation level which, type relationship in (7) with Eidle = 56 (mJ/slot) and ke = 0.25 in the carried out tests, is of the order of about 100 (KB/slot). (mJ/KB/slot) for characterizing the average energy-vs.-transmit rate Furthermore, higher values of N ¯ allow to approach the goodput performance of 3G-based mobile connections. Since 3G connec- saturation level at lower values of Eave . tions do not suffer, by design, by the presence of primary users, c) Access goodput-vs.-collision rate-vs.-backbone utilization factor. in the corresponding carried out simulations we have: (i) set P L ( j ) = 1 in (7); and, (ii) disabled the data fusion operation. Fig. 4(c) reports the behavior of the aggregate goodput versus the available per-client average energy for various values of the toler- Hence, under the same application scenario and mobility pat- ated collision rate ν . The limit cases of light (e.g., N = 1) loaded terns we already considered, we have numerically ascertained that vehicular access network is considered. An examination of these the per-client average energy consumptions of the simulated WiFi plots leads to two main conclusions. First, at fixed ν , the aggregate connections are about 40%, 52% and 58% lower than the cor- goodput approaches a saturation level for increasing Eave . Second, responding ones of 3G connections at per-client goodput of 10 the saturation level scales up for increasing values of ν . (KB/slot), 50 (KB/slot) and 100 (KB/slot), respectively. These re- sults are aligned with the trend already remarked in [2,26] about d) Fair behavior of the proposed joint controller. About the fair be- the significant energy savings offered by WiFi connections over 3G havior of the proposed joint controller, in principle, the optimal ones at medium/high levels of the per-client access rate. i access control policy in (30) is fair when the time-varying j max (t ) index in (29) acts as a random variable which is evenly distributed f) Adaptive capability of the proposed rate controller under intermittent over the set {1, . . . , N to } of the VC indexes. In addition to the (ex- V2I connectivity. Goal of a last set of numerical trials is to test pected) fairness induced by the VC mobility, a peculiar feature of the adaptive capability of the on-the-fly implementation of the our framework is that the constraint in (10) on the per-client aver- proposed rate controller of Section 5.1 when the RSUs of Fig. 1 age energy automatically forces the VCs which are already gained do not offer full spatial coverage. Specifically, the numerical re- the access in the past slots to refrain to query to accede again sults of this sub-section refer to the case in which the inter-RSU in the future slots. This leaves, in turn, room for the access by distance D is four times the cluster radius R, so that covered/un- energy-rich VCs which have not still served. Hence, we expect that covered clusters of the same radius are evenly interleaved over the the per-client average energy constraint in (10) acts as a strong spatial domain (see Fig. 1). The same simulation parameters of Sec- incentive for assuring fair access, even in quasi-static vehicular tion 6.2.b have been still considered at N ¯ = 1 and v¯ = 100 (km/h). environments. In order to (numerically) validate this expectation, The continue plot of Fig. 5 reports the (numerically evaluated) time 10 N. Cordeschi et al. / Vehicular Communications 2 (2015) 1–12 The carried out numerical tests support the performance opti- mality of the proposed controller, as well as its performance ro- bustness against several impairments (such as, for example, the mobility-induced unpredictable fluctuations of the transport ca- pacity of the Internet backbone), even under limited average/peak transmit energies and intermittent V2I connections. Appendix A. Proof of Proposition 2 Let rk (t ) be any feasible rate scheduler for the k-th ARAP in opt (17)–(18) and let rk (t ) be the corresponding optimal one. Af- ter expressing the constraint (11) on the peak energy in terms of rk (t ), from (14) we recognize that any feasible scheduler rk (t ) must satisfy the following inequality: rk (εk (t ), sk (t ), P Li (t )) ≤ r kP (t ), with Fig. 5. Numerically evaluated time evolution (–) of μ1 (t ) under intermittent spatial k r P (t ) defined in Proposition 2. Let us pass now to derive the ex- coverage. The dashed line marks the corresponding optimal steady-state values. opt pression for the optimal access rate policy rk (t ) of the k-th ARAP. It can be recognized that the ARAP in (17)–(18) is a strictly con- behavior of the Lagrange multiplier μ1 (t ) in (28) when the corre- vex optimization problem. Furthermore, since the all-null solution sponding client VC (1): (i) enters the first covered cluster at t = 0; (that is, λk (t ) = Ψki (t ) = rk (t ) ≡ 0) meets all the convex constraints (ii) exits from this cluster and enters the first uncovered cluster in (9)–(14) with the strict inequality, the Slater’s condition for the at t = 90; and, then, (iii) leaves the uncovered cluster and enters constraint qualification [27, p. 247] holds, so that, according to the second covered cluster at t = 180. Similar time-behaviors are opt the [27, p. 249], the optimal access rate rk (t ) may be computed exhibited by the Lagrange multipliers of all simulated VCs. In or- through an application of the Karush–Kuhn–Tucker (KKT) optimal- der to understand the behavior of the plot of Fig. 5, we observe ity conditions. In our framework, the resulting Lagrangian function that the estimated channel state experienced by VC (1) is posi- takes the following form: tive (respectively, vanishing) when VC (1) is traveling over covered (respectively, uncovered) clusters. In agreement with this observa- L rk (t ), μk (t ) tion, μ1 (t ) in Fig. 5 approaches a positive steady-state value when VC (1) travels over a cluster served by an RSU, while it decreases = E sk rk (t ) − μk (t ) E sk εk rk (t ), sk (t ), P iL (t ) − Eave k , (A.1) and ultimately vanishes when VC (1) is traveling over an uncovered area (see Eq. (28)). The interesting feature of the continue plot of so that, by imposing the gradient is vanishing condition, we obtain: Fig. 5 is that, in all cases, quick convergence of μ1 (t ) to the opti- ε˙ k (rk (t ), sk (t ), P Li (t )) = 1/μk (t ), that in turn, allows us to arrive at mal steady-state values (reported by the piece-wise dashed line of the following unconstrained solution: rk∗ (t ) = ε˙ k−1 ( μ 1(t ) , sk (t ), P Li (t )) k Fig. 5) is attained within 20 slot-times, with an residual error be- for the tackled k-th ARAP. Thus, since the Lagrangian function low 10%. This supports the conclusion that the proposed on-the-fly is concave, the solution of the following constrained problem: implementation of the optimal rate controller of Section 5.1 is ca- max0≤r (t )≤rk (t ) L(rk (t ), μk (t )) is the projection of rk∗ (t ) onto the k P pable to quick adapt to the abrupt environmental changes induced underlying definition set: [0, r kP (t )], so that we have: rk (t ) ≡ opt by intermittent spatial coverages. r k (t ) [˙ k−1 ( μ 1(t ) , sk (t ), ε P Li (t ))]0P , that is, the expression in (27). Finally, k 7. Conclusion since the rate function Rk (·) is assumed to be strictly increasing in the energy variable, the constraint in (10) on the average energy must be bound at the optimum, so that μk (t ) may be computed In this paper, we developed the optimal joint controller and as the (unique) solution of the (algebraic) average energy equa- the related supporting access protocol for the adaptive, scalable tion (10) considered as an equality, that can be solved on-the-fly and distributed management of the energy and bandwidth re- through the stochastic gradient projection algorithm in (28). sources of V2I CR-assisted access networks. The goal is to provide to smartphone-equipped vehicular clients the mobile Internet ac- Appendix B. Proof of the optimality of the flow control in (31) cess which is required by the emerging Cloud-assisted vehicular infotainment applications. In a nutshell, the main features of the From the buffer equation (8) we obtain: u j (t ) = [q j (t ) − developed optimal controller are that: 1) it dynamically controls q j (t + 1) + λ j (t )]+ , which points out that, given λ j (t ), u j (t ) the access time-windows at the serving RSUs, as well as the ac- does not depend on λk (t ) for k = j. As a consequence, we have: cess rates and traffic flows at the served VCs in an cross-layer E{u j (t )|λk (t ), k ∈ C i (t )} = E{u j (t )|λ j (t )}, which, in turn, allows us fashion; 2) it is capable to adapt to the (possibly, unpredictable to rewrite the objective function in (19) in the following equivalent and abrupt) mobility and fading-induced changes of the state of form: the underlying vehicular network, without requiring any a priori knowledge or forecasting of the statistical behaviors of the access opt max θj max E u j (t ) rk (t ), k ∈ C i (t ) . (B.1) channels and/or the vehicular traffic patterns; 3) it is distributed {Ψ ji (t ), j ∈C i (t )} λ j (t ) and scalable, so that its implementation complexity is fully inde- j ∈C i (t ) pendent from the number of the serving RSUs and served VCs; From (B.1), it follows that the computation of the optimal flow 4) in order to maximize both the energy and bandwidth efficiency opt λ j (t ) may be carried out in a distributed way by allowing of the overall vehicular access network, it exploits the CR support VC ( j ) to locally solve the following j-th Flow Control Problem (FCP): for performing the optimal soft-input/soft-output fusion of the en- opt maxλ j (t ) E{u j (t )|rk (t ), k ∈ C i (t )}. s.t.: (13). Towards this end, from vironmental data which are autonomously acquired by the served VCs; and 5) it provides hard reliability guarantees to the (possibly, the definition in (5) we directly obtain: u j (t ) = η0 r opt j (t )(1 − opt safety-type) primary traffic transported by the wireless communi- c i (t ))Ψ ji (t ), j ∈ C i (t ), that, after conditioning on {rk (t ), Ψki (t ), k ∈ cation backbone. C i (t )}, leads in turn, to the following inequality: N. Cordeschi et al. / Vehicular Communications 2 (2015) 1–12 11 E u j (t ) rk (t ), Ψki (t ), k ∈ C i (t ) opt feasibility of the controller in (30), we observe that, by design, it opt meets the constraints in (12), while it allows the access to sec- ≤η opt 0 r j (t )Ψ ji (t ) E 1 − c i (t ) rk (t ), Ψki (t ), k ∈ C i (t ) . (B.2) ondary users only when the following event happens (see (30)): t −1 Interestingly, (B.2) does not depend on λ j (t ). Therefore, provided Aopt i {xi (t ) ≤ νti − 1 }. In order to prove that the controller in (30) that the constraints in (13) are met, we have full freedom in the meets the instantaneous constraint in (9), we proceed by induc- choice of the flow controller λ j (t ). Thus, it follows that λ j (t ) opt tion over the time-index t. Hence, after assuming that: x(t ) ≤ νi , in (31) is the maximum feasible flow under the constraints in a direct inspection of (4) leads to the conclusion that the following opt (13) (that is, for any (u j (t ), q j (t )), we have: λ j (t ) ≤ λ j (t )), so inequality holds: xi (t + 1) ≤ νi , regardless from the value assumed by c i (t ), so that we conclude that the controller in (30) is feasible that: E { opt λ j (t )|u j (t ), q j (t )} ≤ E {λ j (t )|u j (t ), q j (t )} for any feasible for the problem in (C.2) s.t. (9), (12) Afterwards, in order to prove flow controller λ j (t ). Since this inequality must hold for any that the controller in (30) attains the maximum in (C.2), we begin opt (u j (t ), q j (t )), we conclude that λ j (t ) in (31) represents also the to upper bound the expectation in (C.2) as in the followings: unconditional optimal flow control policy, that is, the one which maximizes the unconditional expectation E {λ j (t )}. Hence, since in E 1 − c i (t ) α j (t )Ψ ji (t ) the steady-state we must have (see (8)): E {u j (t )} ≡ E {λ j (t )}, we opt j ∈C i (t ) conclude that λ j (t ) in (31) is the flow control policy which solves the j-th FCP, and also maximizes the unconditional average util- (a) ity: E {u j (t )} acquired by VC ( j ). This proves, in turn, the optimality =E α j (t )Ψ ji (t )|U i P ui j ∈C i (t ) of (31). i i i Appendix C. Proof of the optimality of the access control in (30) (b) =E α j (t )Ψ ji (t ) Q , A P u j ∈C i (t ) opt Since λ j (t ) in (31) depends on u j (t ), in order to obtain the so- (c ) i P Li lution of the i-th CTFAP in (19)–(20), it suffices that RSU (i ) solves ≤ E αimax (t ) Qi , Ai P col , (C.5) the following problem for the allocation of the optimal access 1 − P Li time-windows: where: (a) follows from the definition of U i ; (b) stems from opt the fact that, after conditioning on the joint event (Qi , Ai ), the max θ j E u j (t ) rk (t ), k ∈ C i (t ) , (C.1) i {Ψ ji (t ), j ∈C i (t )} collision-free event C is independent from the actual values as- j ∈C i (t ) sumed by {α j (t ), j ∈ C i (t )} and (c) steams from the constraint in s.t.: Eqs. (9), (12). Furthermore, after observing that the conditional (12) and from (C.3) and (C.4). About the achievement of the bound expectation in (C.1) equates (see the definition of u j (t ) in (5)): in (C.5), we observe that, provided that the access event Ai occurs, opt opt opt E{u j (t )|rk (t ), k ∈ C i (t )} = η0 r j (t ) E{(1 − c i (t ))Ψ ji (t )|rk (t ), k ∈ the controller in (30) assigns the whole unit-length access window C i (t )}, the problem in (C.1) s.t.: Eqs. (9), (12) may be recast in the to the “best” querying user (see (29) and the second row of (30)), following equivalent form: so that the bound in (C.5) is actually attained by (30). Hence, in order to prove the optimality of (30), we only have opt max E 1 − c i (t ) θ j r j (t )Ψ ji (t ) , (C.2) to prove that the policy (30) maximizes the last term in (C.5). To {Ψ ji (t ), j ∈C i (t )} this end, let us assume that, after conditioning on the secondary- j ∈C i (t ) query event Qi , the implemented access decision rule Ai does s.t. Eqs. (9), (12). Since we are pursuing the maximization of the not depend on αimax (t ), so that the following relationship holds: steady-state performance of the optimal controller, let us define: E {αimax (t )|(Qi , Ai )} = E {αimax (t )|Qi }. As a consequence, the last (a) P Li limt →∞ P Li (t ) = (1 − γi ), where (a) stems from an application term in (C.5) is maximized when the collision probability P col i is of the Laws of the Large Numbers in tandem with the observation maximized. Hence, since the hard instantaneous constraint in (9) that F i (t ) in (21) converges to γi for large t and the conditioning guarantees that: xi (t ) ≤ νi for any t, we conclude that every feasi- set V i (t ) in (25) includes F i (t ). Since it is direct to check that, in ble scheduler also meets the constraint: P col i ≡ limt →∞ xi (t ) ≤ νi . the limit cases of P Li = 1 and P Li = 0, the controller (30) is the i Therefore, since we have already proved that: P col ≤ P qi γi , the optimal one, in the sequel, we tackle the case 0 < P Li < 1. i following relationship must hold: P col ≤ δi min{νi , P qi γi }. In or- Towards this end, after introducing the dummy positions: α j (t ) θ j r opt (t ) and αimax (t ) max j ∈C i (t ) {α j (t )}, let Qi i der to prove that the controller in (30) meets P col ≡ δi with the j strict equality, we proceed by contradiction. Hence, let us assume {αimax (t ) > 0} be the secondary-query event in cluster(i ) and let i that, for the controller in (30), we have: P col < δi . Hence, being: P qi be the corresponding steady-state probability. Furthermore, let νi t −1 limt →∞ t −1 = νi ≥ δi , it follows that, for large t, the access con- Ai { j∈C i (t ) Ψ ji > 0}, C i {c i (t ) = 1} and C i {c i (t ) = 0} be the ν t −1 dition xi (t ) ≤ ti −1 is always met, so that, in the steady-state, secondary-access event, the primary–secondary collision event and the “best” secondary client gains the access at each slot. This i the collision-free event respectively, and let P sa i , P col and (1 − P col i ) leads, in turn, to P (Ai |Qi ) = 1, and, therefore, from (C.3), have: be the corresponding steady-state probabilities. Hence, after indi- i P col = γi P qi ≥ δi , which is a contradiction. This last observation cating by U i (Qi , Ai , C i ) the event of successful access and by completes the proof of the optimality of (30). P ui the corresponding steady-state probability, an application of the Bayes rule leads to: References i P col = P qi P Ai Qi P C i Ai , Qi = P qi P Ai Qi γi , (C.3) [1] M. Whaiduzzaman, M. Sookhak, A. Gani, R. Buyya, A survey on vehicular cloud P ui = P qi P Ai Qi P C i Ai , Qi = P qi P Ai Qi (1 − γi ). (C.4) computing, J. Netw. Comput. Appl. 40 (2013) 325–344. [2] M.V. Barbera, S. Kosta, A. Mei, J. Stefa, To offload or not to offload? The band- Interestingly enough, from (C.3) it follows that the following up- width and energy costs of mobile cloud computing, in: INFOCOM, Proceedings i per bound must hold: P col ≤ P qi γi . Hence, in order to prove the IEEE, IEEE, 2013, pp. 1285–1293. 12 N. Cordeschi et al. / Vehicular Communications 2 (2015) 1–12 [3] A. Festag, G. Noecker, M. Strassberger, A. Lübke, B. Bochow, M. Torrent-Moreno, [14] C. Rentel, T. Kunz, A clock-sampling mutual network time-synchronization al- S. Schnaufer, R. Eigner, C. Catrinescu, J. Kunisch, NoW – Network on Wheels: gorithm for wireless ad hoc networks, in: Wireless Communications and Net- Project objectives, technology and achievements, in: Proceedings of 5rd Inter- working Conference, 2005 IEEE, vol. 1, 2005, pp. 638–644. national Workshop on Intelligent Transportation, WIT, 2008, pp. 211–216. [15] M. Mustafa, M. Papatriantafilou, E. Schiller, A. Tohidi, P. Tsigas, Autonomous [4] J. Alcaraz, J. Vales-Alonso, J. Garcia-Haro, Control-based scheduling with QoS TDMA alignment for VANETs, in: Vehicular Technology Conference, VTC Fall, support for vehicle to infrastructure communications, IEEE Wirel. Commun. 2012, IEEE, 2012, pp. 1–5. 16 (6) (2009) 32–39. [16] N. Cordeschi, T. Patriarca, E. Baccarelli, Stochastic traffic engineering for real- [5] Y. Zhang, J. Zhao, G. Cao, On scheduling vehicle-roadside data access, in: Pro- time applications over wireless networks, J. Netw. Comput. Appl. 35 (2) (2012) ceedings of the Fourth ACM International Workshop on Vehicular ad Hoc Net- 681–694. works, ACM, 2007, pp. 9–18. [17] N. Balasubramanian, A. Balasubramanian, A. Venkataramani, Energy consump- [6] G. Korkmaz, E. Ekici, F. Özgüner, Supporting real-time traffic in multihop tion in mobile phones: a measurement study and implications for network vehicle-to-infrastructure networks, Transp. Res., Part C, Emerg. Technol. 18 (3) applications, in: Proceedings of the 9th ACM SIGCOMM Conference on Inter- (2010) 376–392. net Measurement Conference, ACM, 2009, pp. 280–293. [7] J.-A. Bazerque, G.B. Giannakis, Distributed scheduling and resource allocation [18] R. Wolff, Stochastic Modelling and the Theory of Queues, Prentice Hall, 1989. for cognitive OFDMA radios, Mob. Netw. Appl. 13 (5) (2008) 452–462. [19] N. Cordeschi, D. Amendola, E. Baccarelli, Distributed and Adaptive Re- [8] R. Urgaonkar, M.J. Neely, Opportunistic scheduling with reliability guarantees source Management in Cloud-assisted Cognitive Radio Vehicular Networks in cognitive radio networks, IEEE Trans. Mob. Comput. 8 (6) (2009) 766–777. with Hard Reliability Guarantees, http://infocom.uniroma1.it/%7Eenzobac/ [9] K.R. Chowdhury, I.F. Akyildiz, Cognitive wireless mesh networks with dynamic ResManagVehNetworks.pdf/. spectrum access, IEEE J. Sel. Areas Commun. 26 (1) (2008) 168–181. [20] P. Varshney, Distributed Detection and Data Fusion, Springer, 1997. [10] A. Chaoub, E. Ibn Elhaj, J. El Abbadi, Multimedia traffic transmission over TDMA [21] D.P. Bertsekas, J.N. Tsitsiklis, Parallel and Distributed Computation: Numerical shared cognitive radio networks with Poissonian primary traffic, in: Interna- Methods, Athena Scientific, 1997. tional Conference on Multimedia Computing and Systems (ICMCS), IEEE, 2011, [22] H.J. Kushner, J. Yang, Analysis of adaptive step-size SA algorithms for parameter pp. 1–6. tracking, IEEE Trans. Autom. Control 40 (1995) 1403–1410. [11] X. Gelabert, O. Sallent, J. Pérez-Romero, R. Agustí, Flexible spectrum access [23] T.H. Luan, X. Ling, X.S. Shen, Provisioning QoS controlled media access in vehic- for opportunistic secondary operation in cognitive radio networks, IEEE Trans. ular to infrastructure communications, Ad Hoc Netw. 10 (2) (2012) 231–242. Commun. 59 (10) (2011) 2659–2664. [24] G. Acosta-Marum, M.A. Ingram, Six time- and frequency-selective empirical [12] T. Jiang, H. Wang, A.V. Vasilakos, QoE-driven channel allocation schemes for channel models for vehicular wireless LANs, IEEE Veh. Technol. Mag. 2 (4) multimedia transmission of priority-based secondary users over cognitive radio (2007) 4–11. networks, IEEE J. Sel. Areas Commun. 30 (7) (2012) 1215–1224. [25] F.F. Digham, M.-S. Alouini, M.K. Simon, On the energy detection of unknown [13] G. Karagiannis, O. Altintas, E. Ekici, G. Heijenk, B. Jarupan, K. Lin, T. Weil, signals over fading channels, IEEE Trans. Commun. 55 (1) (2007) 21–24. Vehicular networking: a survey and tutorial on requirements, architectures, [26] K. Lee, J. Lee, Y. Yi, I. Rhee, S. Chong, Mobile data offloading: how much can challenges, standards and solutions, IEEE Commun. Surv. Tutor. 13 (4) (2011) WiFi deliver? IEEE/ACM Trans. Netw. 21 (2) (2013) 536–550. 584–616. [27] M.S. Bazaraa, H.D. Sherali, C.M. Shetty, Nonlinear Programming, Wiley, 2006.