Belazzougui D.,CERIST Research Center
Theoretical Computer Science | Year: 2016
Suppose we have two players A and C, where player A has a string s[0. ..u-1] and player C has a string t[0. ..u-1] and none of the two players knows the other's string.Assume that s and t are both over an integer alphabet [σ]. =[0, σ. -1], where the first string contains n non-zero entries. We would wish to answer the following basic question. Assuming that s and t differ in at most k positions, how many bits does player A need to send to player C so that he can recover s with certainty? Further, how much time does player A need to spend to compute the sent bits and how much time does player C need to recover the string s? This problem has a certain number of applications, for example in databases, where each of the two parties possesses a set of n key-value pairs, where keys are from the universe [. u] and values are from [σ] and usually n≪. u.In this paper, we show a time and message-size optimal Las Vegas reduction from this problem to the problem of systematic error correction of k errors for strings of length Θ(n) over an alphabet of size 2Θ(log σ+log (u/n)).The additional running time incurred by the reduction is linear expected (randomized) for player A and linear worst-case (deterministic) for player C, but the correction works with certainty. When using the popular Reed-Solomon codes, the reduction gives a protocol that transmits O(k(log u+log σ)) bits and runs in time O(n·polylog(n)(log u+log σ)) for all values of k. The time is expected for player A (encoding time) and worst-case for player C (decoding time). The message size is optimal whenever k≤(uσ)1-Ω(1). © 2016.
Djenouri D.,CERIST Research Center
IEEE Vehicular Technology Conference | Year: 2014
Receiver-to-receiver time synchronization in wireless networks is considered, and appropriate maximum-likelihood estimators (MLE) for environments with exponential distrusted reception delays are proposed. In the receiver-to-receiver synchronization approach, time at receivers should be directly related to one another without referring to the sender (reference), which permits to eliminate the sender's uncertainty from the variable delays (time critical-path). The models and estimators proposed for the sender-to-receiver approach are thus inappropriate for the receiver-to-receiver one. A model that accurately reflects the relative feature of the considered approach and eliminates the senders's uncertainty is used, where timestamps at the receivers are directly related without referring to the sender's time or timestamps. By directly relating time at two receivers with identical exponential reception delay, Exp(λ), it yields a Laplace(0,1/λ) distribution as the difference between the two delays. By using the log-likelihood function of the latter and the ML method, the offset estimator is analytically derived and a linear program is given for the joint offset/skew model. The accuracy of the proposed estimators has been numerically analyzed by simulation. Results show high precision of the proposed estimators, which can be integrated with any receiver-to-receiver synchronization protocol. © 2014 IEEE.
Djenouri D.,CERIST Research Center |
Balasingham I.,University of Oslo
IEEE Transactions on Mobile Computing | Year: 2011
A new localized quality of service (QoS) routing protocol for wireless sensor networks (WSN) is proposed in this paper. The proposed protocol targets WSN's applications having different types of data traffic. It is based on differentiating QoS requirements according to the data type, which enables to provide several and customized QoS metrics for each traffic category. With each packet, the protocol attempts to fulfill the required data-related QoS metric(s) while considering power efficiency. It is modular and uses geographical information, which eliminates the need of propagating routing information. For link quality estimation, the protocol employs distributed, memory and computation efficient mechanisms. It uses a multisink single-path approach to increase reliability. To our knowledge, this protocol is the first that makes use of the diversity in data traffic while considering latency, reliability, residual energy in sensor nodes, and transmission power between nodes to cast QoS metrics as a multiobjective problem. The proposed protocol can operate with any medium access control (MAC) protocol, provided that it employs an acknowledgment (ACK) mechanism. Extensive simulation study with scenarios of 900 nodes shows the proposed protocol outperforms all comparable state-of-the-art QoS and localized routing protocols. Moreover, the protocol has been implemented on sensor motes and tested in a sensor network testbed. © 2011 IEEE.
Khiati M.,University of Science and Technology Houari Boumediene |
Djenouri PhD D.,CERIST Research Center
International Journal of Communication Systems | Year: 2015
Broadcasting delay-sensitive information over a duty-cycled wireless sensor network is considered, and a cluster-based protocol is proposed. The proposed protocol, namely Broadcast over Duty-Cycle and LEACH (BOD-LEACH), takes advantage of the LEACH's energy-efficient clustering. This approach shifts the total burden of energy consumption of a single cluster head by rotating the cluster-head role among all nodes in the network. It also permits the ordinary (member) nodes in a cluster to turn off their radios whenever they enter inactive TDMA slots. However, LEACH does not consider broadcast messages, and the member nodes scheduling is established as a sequence of Time Division Multiple Access (TDMA) without any common active period. A broadcast message should then be postponed to the next TDMA schedule and transmitted in a sequence of unicast messages, which is inefficient in terms of latency, bandwidth occupation, and power consumption. The proposed protocol adds new common static and dynamic broadcast periods to support and accelerate broadcasting. The dynamic periods are scheduled following the past arrivals of messages and using a Markov chain model. To our knowledge, this work is the first that proposes the use of clustering to perform simultaneous local broadcasts at several clusters. This reduces broadcast latency and ensures scalability. The protocol has been simulated, numerically analyzed, and compared with LEACH. The results show clear improvement over LEACH with regard to broadcast latency, at a low energy cost. Copyright © 2013 John Wiley & Sons, Ltd.
Djenouri D.,CERIST Research Center
IEEE Signal Processing Letters | Year: 2012
A new time synchronization protocol for wireless sensor networks (WSN) is proposed. It uses the receiver-to-receiver principle introduced by the Reference Broadcast Synchronization (RBS), which reduces the time-critical path compared to the sender-to-receiver approach. The proposed protocol has the advantage of distributing the reference's function among all sensors, which eliminates the single point of failure (reference) shortcomings of RBS. It also allows timestamps to be piggybacked to the regular signals (beacons) and thus eliminates the need of separate transmissions for exchanging timestamps. After local synchronization, a multihop extension is proposed using final local estimates, with no forwarding of synchronization signals. Maximum likelihood estimators (MLE) are derived to estimate relative skew/offset for channels with Gaussian distributed delays. The Cramer-Rao lower bounds (CRLB) are accordingly derived and numerically compared with the MLE's mean square error (MSE). Results show convergence of the proposed estimators' precision to their respective CRLB with the increase of the number of signals. © 2006 IEEE.