In this paper, we propose a novel cooperative roadside unit (RSU) broadcast approach that can effectively enhance the vehicles’ packet-reception rates of the messages broadcast cooperatively by nearby RSUs. To enable message-aggregation among RSUs, we propose a new vehicular-message format based on the software-defined multiplexing code which can aggregate multiple messages without any need of packet form. To facilitate our proposed new cooperative scheme, RSUs must be organized into clusters. We formulate this RSU clustering problem as a graph partitioning problem, which aims to make individual cluster sizes as close to each other as possible. Furthermore, we design a new heuristic algorithm to efficiently solve this problem. This heuristic algorithm is also compared with the random clustering and minimum-degree clustering schemes in terms of the modified Gini index. The theoretical analysis of our proposed cooperative RSU broadcast scheme is also conducted to guarantee that our proposed new cooperative RSU-broadcast approach can improve the packet reception rate. Furthermore, we simulate the vehicular environment with the simulation tools SUMO and NS-3 as benchmarks. The simulation demonstrates that our proposed new cooperative RSU-broadcast system will increase the packet reception rate and the number of successfully received packets over the conventional non-cooperative broadcast system.

Nowadays, wireless local-area networks (WLANs) are widely deployed in residential and commercial areas. How to ensure full coverage is always an important challenge during the deployment of access-points (APs) and routers. In this study, we investigate the full Line of Sight (LoS) coverage problem. We will focus on how to achieve the full LoS coverage using a minimal number of APs/routers in an arbitrary polygonal/prismatic field-of-interest, which may be simply or multiply connected subject to a certain restricted link-range. We propose a new visibility-polygon-based approach for doing so. The performance of our proposed new approach is then evaluated in terms of the coverage efficiency, the total number of APs/routers, and the peak link-distance ratio for achieving the full LoS coverage. Meanwhile, we also compare our proposed new approach with the existing schemes. Compared to the existing schemes, our proposed novel visibility-polygon-based approach can achieve the full LoS coverage by requiring the same number of APs/routers but much less computation time.

The well-known soft-focus effect, which relies on either special optical filters or manual post-production techniques, has been intriguing and powerful in photography for quite a while. Nonetheless, how to impose the soft-focus effect automatically simply using sophisticated image-processing (computational photography) algorithms has never been addressed in the literature to the best of our knowledge. In this work, we would like to make the first-ever attempt to design an automatic, optical-filter-free approach to create the appropriate soft-focus effects desired by individual users. Our approach is first to investigate the physical optical filter, namely Kenko Black Mist No. 5, and estimate the corresponding kernel matrix (i.e., the system impulse response matrix) using our proposed novel irradiance-domain kernel-matrix estimation framework. Furthermore, we demonstrate that it is not feasible to find a kernel matrix that precisely characterizes the soft-focus effect by just using a pixel-value-domain image (a regular photo) in post production. To combat the aforementioned problem, we establish a novel pixel-value-to-pseudo-irradiance map such that the pseudo irradiance-domain image can be obtained directly from any pixel-value-domain image. Finally the soft-focus effect can be created from the two-dimensional convolution between the pseudo irradiance-domain image and the estimated kernel. To evaluate our proposed automatic scheme for soft-focus effect, we compare the results from our proposed new scheme and the physical optical filter in terms of the DCT-KLD (Kullback-Leibler divergence of discrete cosine transform) and the conventional PSNR (peak-signal-to-noise ratio). Experiments show that our proposed new scheme can achieve very small DCT-KLDs and very large PSNRs over the ground truth, namely the results from the physical optical filter.

Image mosaic is a prevalent technique to conceal critical content in images. However, conventional mosaic techniques cannot be recovered using a small-sized key, as they require retransmission of the original images for perfect recovery. In this work, we propose a novel, computationally efficient, and effective recoverable image-mosaic technique. A key advantage of our proposed image-mosaic scheme is its robust performance across a range of adjustable key lengths. Our technique effectively conceals original information even with a small-sized key of only a few bits. To evaluate its performance, we introduce a new image-similarity metric based on the magnitude of the discrete cosine transform (DCT). This metric exhibits several advantageous mathematical properties, including the ability to quantify the perceptibility of major content in mosaicked images, invariance under image reflections and 180-degree rotations, and insensitivity to small translations. Finally, numerical experiments demonstrate that our method outperforms existing recoverable image-mosaic techniques and performs consistent across varying key lengths. We also compare the run-times required by our proposed new scheme with those required by other existing recoverable image-mosaic methods and the state-of-the-art image-encryption methods to exhibit the computational efficiency of our proposed new scheme.

Mosaic is a prevalent signal-processing approach to hide or protect critical information from users. The conventional mosaic schemes simply abolish or add artificial noise to the original signal content a sender wants to conceal. Thus, they are not recoverable simply by use of a key which can be represented as a very short sequence compared to the concealed signal content. In this work, we extend our previous effort in recoverable image mosaicing to design a novel audio mosaicing approach using hierarchical permutations. Besides, we establish the mathematical relationship between the popular signal-quality metric, namely, signal-to-noise ratio (SNR), and our previously proposed signal-destructuring metric, namely, Kullback–Leibler divergence of discrete cosine transform (DCT-KLD), so that the mosaicing or signal-destructuring effect in terms of DCT-KLD and the general signal-quality measure in terms of SNR can be translated into each other. As a result, one can easily judge if the mosaicked signal reaches the concealability which is equivalent to the maximum SNR to eliminate the intelligibility of an utterance. The new relationship between DCT-KLD and SNR we develop can thus be very useful to qualify an audio mosaic method without any need of human listening test.

In this letter, a novel light-weight audio mosaic scheme using permutations of linear predictive coding (LPC) coefficients as LPC has been widely adopted in many audio codecs (coder-encoders) nowadays. We establish the theoretical secrecy analysis with respect to the degree of the original LPC polynomial and the minimum-phase population of permuted LPC polynomials. The mosaic (destructuring) performance in terms of DCT-KLD (Kullback-Leibler divergence of discrete cosine transform) is also evaluated through simulations. In comparison with the existing audio-mosaic method using waveform permutations, our proposed new audio-mosaic scheme using LPC-coefficient permutations can achieve a much better mosaic performance (a much higher DCT-KLD) subject to the same key size.

Nowadays, wireless local-area networks (WLANs) are widely deployed in residential and commercial areas. The coverage quality is essential to users. The full coverage appears to be one of the most crucial problems to be considered during the network and access-point/router deployment (placement). We formulate the light-of-sight (LoS) coverage problem using the visibility-graph framework. In this work, for arbitrary multiply-connected or simply-connected polygonal/prismatic fields-of-interest subject to an arbitrary link-range restriction, we investigate how the full LoS coverage can be achieved by a minimum number of access-points/routers. Based on the new mathematical lemmas we derive, we design a novel graph-theoretical approach accordingly. Our proposed new scheme can be deemed the first-ever systematic approach to the best of our knowledge. Our proposed new approach is also evaluated in terms of the coverage efficiency, the number of access-points/routers, and the peak link-distance ratio for full LoS coverage in comparison with the existing solution to the art gallery problem.

The use of mobile chargers (MCs) to charge the nodes in wireless rechargeable sensor networks via wireless power transfer (WPT) has attracted much research effort. Existing works mostly concentrate on path planning whereas neglecting the opportunities to improve charging coverage and efficiency by exploiting the energy redistribution (ERD) process among nodes and an MC’s capability of charging multiple nodes simultaneously via WPT. To exploit such opportunities, we study the underlying ERD-assisted MC charge scheduling (ERAMCCS) problem, i.e., to find a charging schedule satisfying the nodes’ energy demands with minimum energy loss and minimum time span. After proving that the problem is NP-hard, we propose a charge scheduling algorithm based on the greedy idea (CSBGI), which provides a solution by decoupling the problem into two subproblems: 1) ERAMCCS-Energy and 2) ERAMCCS-Time, to minimize the energy loss and the time span, respectively. By partitioning the energy loss into transmission energy loss and moving energy loss, we solve the ERAMCCS-Energy problem by minimizing the two parts, respectively, by formulating and solving some linear programming problems and traveling salesman problem problems based on the charging position set. The charging position set is iteratively refined by identifying and removing redundant charging positions. For the ERAMCCS-Time problem, concurrent energy transmission opportunities are exploited to try to minimize the time span of the schedule. We demonstrate some key properties of CSBGI, such as its approximation ratio in terms of energy loss and its time complexity. Testbed experiments and numerical simulations confirm the superiority of CSBGI over typical algorithms.

Cyber security has become an important problem nowadays as almost everyone is often linked to the Internet for business and entertainment. Conventional cryptographers fail to address timely issues regarding cyber-attacks, such as cyber identity theft. In this work, we propose a novel idea, namely, a bandage-cover cryptographer (BCC), which is completely software-defined and protocol-free. Besides, this new cryptographic approach can enable camouflages to confuse data-mining robots, which are often encountered in the cyber world nowadays. Because all of the existing cryptographers aim to protect the entire data (document and file) altogether, they cannot have camouflagibility to mislead data-mining robots. Conversely, by our proposed novel BCC, one can select arbitrary contexts or parts of the data (related to individual identify and/or private confidential information) under protection. To evaluate such a first-ever cryptographer capable of misleading data-mining robots, we define two new metrics, namely: 1) vulnerability and 2) camouflage rates. The theoretical analyses of vulnerability rate and camouflage rate for our proposed new BCC are also presented in this article to demonstrate the corresponding effectiveness.

Mosaic is a popular approach to provide privacy of data and image. However, the existing demosaicing techniques cannot accomplish efficient perfect-reconstruction. If the receiver wants to recover the original image, the extra transmission of the original subimage to be mosaicked is necessary, which consumes much channel resource and is therefore inefficient. In this paper, we propose a novel efficient recoverable cryptographic mosaic technique by permutations. A mosaic, or a privacy-protected subimage, can be constructed through either of the three permutations (Busch's, Wu's, and Sun's/Minmax). These three permutations are designed to maximize the objective function as the sum of the absolute row/column index-differences. This objective is related to the sum of the pixel-to-pixel cross-correlation by our pertinent theoretical study. To measure the effectiveness of the image-mosaicing methods, we propose two image-discrepancy measures, namely summed cross-correlation (SCC) and Kullback-Leibler divergence of discrete cosine transform (DCT-KLD). Compared to the big majority of random permutations for image-mosaicing, our proposed three permutation methods can achieve much better performances in terms of SCC. Nevertheless, the advantage of the three proposed permutation methods over random permutations is not obvious according to DCT-KLD.

Autonomous vehicles become more and more popular in our daily life. Mobile computing schemes to be installed on these vehicles have drawn a lot of recent research interest. In this paper, we address the important path-planning problem for autonomous vehicles. We introduce and formulate the novelpaintbrush coverage problem. We present a theoretical study on the minimum trajectory length of a paintbrush to cover an arbitrary convex region, which is derived as a function of the area of the region and the size of the cover. Three commonly-used patrolling/scouting methods, namely boustrophedon, spiral, and sector, are manifested in details as the potential solutions to the paintbrush coverage problem. The theoretical minimum trajectory lengths any algorithm can achieve are also demonstrated as the benchmarks for different shapes of regions.

Deception detection has been a hot research topic in many areas such as jurisprudence, law enforcement, business, and computer vision. However, there are still many problems that are worth more investigation. One of the major challenges is the data scarcity problem. So far, only one multi-modal benchmark dataset on deception detection has been published, which contains 121 video clips for deception detection (61 for deceptive class and 60 for truthful class). Therefore, most of the generated deception detection models (especially deep neural network-based methods) suffered from the overfitting problem and the bad generalization ability. To solve these problems, we proposed a novel Emotion Transformation Feature (ETF) to analyze deception detection with limited data. The critical analysis and comparison of the proposed methods with the state-of-the-art multi-modal methods have shown significant performance improvement up to 87.59%.

How to combine multiple data-streams for transmission in aggregate is a very interesting problem, especially for the emerging software-defined networks nowadays. The conventional packet-based protocols cannot provide the flexibility for combining data-streams in the ad hoc nature. If the number of data-streams changes over time, the existing packet formats cannot handle the transmission of multiple data-streams effectively. The effectiveness is measured by two performance metrics, namely coding efficiency and data-transmission intermittency. We propose a new software-defined multiplexing code (SDMC) approach, which can combine (multiplex) multiple data-streams easily and is much more effective than the conventional packet-based method. Three SDMC schemes (distributed, hierarchical, and hybrid) are compared theoretically and by simulation. A trade-off between these two performance metrics can be found when one selects one of the three SDMC schemes for combining multiple data-streams. The hierarchical SDMC scheme brings about the highest coding efficiency while the hybrid SDMC scheme suffers from the smallest overall intermittency.

More and more new communication scenarios have been emerging, such as heterogeneous, device-to-device (D2D), machine-to-machine (M2M), and unmanned aerial vehicular communications. The existing packet-based protocols cannot serve the individual demands in all of these scenarios effectively. In this paper, we propose a novel evolutional coding approach to govern all of the needs by various communication applications. Superior to our previously proposed software-defined multiplexing coding technique, the new evolutional codes can provide the capacity for fast information retrieval, which is crucial for real-time mapping, routing, and navigation. The fixed and static packet-based communication systems may be replaced by the flexible communication protocol based on the evolutional codes in the future.

The conventional multiplexing approaches for communication systems demand the pre-specified splitting of resources in time, frequency, space, etc. However, these existing techniques are not flexible when variable messages, such as alert or control information generated by other sources, emerges to be included for transmission during a communication session. In this paper, we propose an innovative idea, namely software-defined multiplexing coding, to efficiently accommodate emerging messages from time to time. Such a new multiplexing paradigm does not demand any additional resource and is very easy to be implemented in real time. The computational complexities of the software-defined multiplexing coding schemes are very low and the asymptotic expected code rate approaches very close to one according to our theoretical analysis.

Low-density parity-check (LDPC) codes are favorable in modern telecommunication technologies due to its superior error-correction capability especially when the codeword length is large. The commonly-used LDPC decoders are based on the belief-propagation (BP) algorithms. It is well known that the layered (serial) belief-propagation (LBP) decoding algorithms can reduce the number of iterations by half in comparison with the flooding (parallel) BP decoding algorithms. Further reduction in total number of iterations can be achieved by using the informed dynamic scheduling techniques, such as residual BP (RBP) and node-wise residual BP (NWRBP) methods. However, the incurred additional computation of residuals is far from trivial. In this paper, we propose a novel efficient dynamic scheduling scheme, called a posteriori probability RBP (APPRBP) algorithm, which offers more flexibility to leverage the performance-complexity trade-off using a threshold parameter. The simulation results demonstrate that the average iteration numbers for our proposed APPRBP algorithm can be remarkably reduced especially in the low E_b/N_0 (signal-energy-per-information-bit to noise-power-spectral-density ratio) conditions while the bit-error rate (BER) performance is subject to slight degradation.

The transmitter identification (Tx-ID) of digital television (DTV) systems becomes crucial nowadays. However, identification of a weak source signal is quite difficult, and therefore pseudo-random (PN) sequences were proposed to be embedded into the DTV signal for the Tx-ID purpose. Kasami sequences are excellent candidates adopted for the Tx-ID PN sequences as they provide a large family of nearly-orthogonal codes. We envision that, in the future, different broadcasting companies may use different Tx-ID sequences (codes) just as different telephone companies have owned different code prefixes or “area codes”. Tx-ID sequences may be grouped separately for different companies and hence there is an emerging need to categorize Tx-ID sequences just as ZIP codes are used to categorize postal addresses. In this paper, we are particularly interested in the Tx-ID sequences made of Kasami sequences. Our main objective is to efficiently categorize and address Kasami sequences. We design a new algorithm that can efficiently classify Kasami sequences within O(n1.5log2n)-time, where n is the sequence length. Simulations show that our proposed algorithm is very fast in practice. Our proposed new blind detection method for determining the addressing parameters for an arbitrary Kasami sequence can save the required huge memory storage space by the conventional correlation-based Kasami sequence classifier (detector).

In this paper, we propose a blind binary low-density parity-check (LDPC) encoder identification scheme for M-quadrature amplitude modulation (M-QAM) signals. The expectation-maximization (EM) algorithm is developed to estimate the unknown signal amplitude, noise variance, and phase offset for M-QAM signals. The a posteriori probabilities (APPs) of the coded bits are obtained from the APPs of the transmitted symbols according to the M-QAM mapper. Monte Carlo simulation results demonstrate the effectiveness of our proposed new blind binary LDPC encoder identification scheme for different modulation orders. The average iteration number needed for the EM algorithm to converge is also investigated for different modulation orders.

Orthogonal frequency-division multiplexing (OFDM) has been widely used for many communication technologies nowadays due to its high spectral efficiency, robustness against inter-symbol-interference and multipath fading, simplicity for implementation, and so on. In this paper, we propose the frequency-domain pilot multiplexing techniques (FDPMTs) for the channel estimation and equalization in OFDM systems. A robust and effective pilot insertion and detection scheme is devised thereby. The information signal sequence resulting from the constellation mapper is spread over all subcarriers by a precoder and certain subcarriers can be nulled for the insertion of training pilots. These pilot positions are optimally selected to minimize the distortion of the transmitted time-domain signal (OFDM modulated signal) caused by the aforementioned subcarrier-removal at the corresponding pilot positions. The associated new receiver structure is also presented, where three different blind pilot-detection techniques are designed without any a priori knowledge of the pilot positions (based on sample variance, subspace decomposition, and Jarqur-Bera (JB) statistics, respectively), and the distorted data symbols can thus be iteratively reconstructed. Besides, rigorous theoretical analysis and Monte Carlo simulation results both demonstrate that our proposed new OFDM system using dynamical pilot positions is more robust than the conventional OFDM system using the fixed pilot positions over multipath fading channels.

In real world, wireless heterogeneous sensor network (HSN) design and information integration are necessary in different applications. Traditionally, wireless sensor networks information integration is set up to passively fuse all received data. Such an approach is computationally challenging and operationally ineffective because improvements in information accuracy are not guaranteed. Opportunistic Sensing (OS) refers to a paradigm for signal and information processing in which a network of sensing systems can automatically discover and select sensor platforms based on an operational scenario. In this paper, we propose theory and algorithms of OS to simplify the HSN design and promote more efficient information integration. We propose an information theoretical criterion for opportunistic sensing in HSN, and show that HSN with correlated modalities needs less number of codewords than that with independent modalities. Our OS algorithm advances autonomous sensing that not only ensures effective utilization of sensing assets but also provides robust optimal performance. We apply our OS algorithm to radar sensor networks for surveillance and monitoring, and show that our approach works very well and much better than other approaches.

In this work, we study the statistical behavior of the peak-to-mean-envelope-power ratio (PMEPR) for orthogonal frequency-division multiplexing (OFDM) signals both theoretically and empirically. First, the relationship is mathematically established between the PMEPR upper-bound of OFDM-QPSK (quadrature phase-shift keying) sequences and the clipping probability for moderate sequence lengths n (i.e. n < 100). Then, the empirical study of the PMEPR distributions is carried out to rectify the preliminary theoretical results. Finally, we theoretically prove that the analysis for OFDM-QPSK sequences can be extended to OFDM-QAM (quadrature amplitude modulation) sequences as well.

Nonbiliary low-density parity-check (LDPC) codes can lead to excellent error performance while the codewords are of short or moderate length. However, the high decoding complexity of nonbiliary LDPC codes inevitably depreciates their practical values. The computational bottleneck arises from the check node processing in the iterative message passing (MP) algorithms which terminate when either all parity checks are satisfied or the maximum iteration number is reached. We have observed that for undecodable blocks, the MP algorithms always run up to the maximum iteration limit and therefore cannot generate the correct codeword. Thus, it would be better to terminate the algorithms early so as to save the unnecessary computational time and reduce the extra power consumption when undecodable blocks are experienced. In this paper, we propose a new T-tolerance stopping criterion for LDPC decoders by exploiting the fact that the total a posteriori probability (APP) should increase as the iteration number grows. Simulation results demonstrate that our proposed new T-tolerance criterion can greatly reduce the average iteration number (complexity) while restricting the decoding performance degradation within 0.1 dB in low bit-energy-to-noise ratio scenarios.

We studied secure homomorphic as well as searchable encryption in this work. In ad hoc/sensor networks, quiteoften we need to gather data from those sensors to a fixed sink and process them, such as a group of sensor nodes responsible for gathering temperature data gathering. In order to ensure user'sprivacy, all gathered data must be encrypted to be sent to the sink. Each piece of data are to be summed up at the sink via homomorphic encryption. In this paper, we consider the scenario where a group of users share some encrypted group data stored at the sink. Each authorized user must be able to efficiently retrieve the group data so he/she can contribute his/her own piece to bemerged with the group data via homomorphic encryption. Our proposed scheme is both provably secure and practical in bothad hoc/sensor networks as well as cloud computing.

In this work, we derive the PMEPR upper bound for the concatenation of OFDM (orthogonal frequency-division multiplexing) sequences. This new study enables people to construct the longer OFDM sequences from the shorter ones. We investigate how the PMEPR (peak-to-mean-envelope-power ratio) upper bound changes as sequences of different lengths and PMEPRs concatenate. Our new theoretical results are crucial for the PMEPR control of OFDM sequences since it is harder to construct long sequences possessing good properties and concatenating several shorter sequences can be an effective alternative solution in practice.

Nowadays, there is urgent demand for wireless sensor network applications. In these applications, usually a base station is responsible for monitoring the entire network and collecting information. If emergency happens, it will propagate such information to all other nodes. However, quite often the message source is not a fixed node, since there may be base stations in charge of different regions or events. Therefore, how to propagate information efficiently when message sources vary from time to time is a challenging issue. None of conventional broadcast algorithms can deal with this case efficiently, since the change of message source incurs a huge implementation cost of rebuilding a broadcast tree. To deal with this difficult problem, we make endeavor in studying multiple source broadcast, in which targeted algorithms should be source-independent to serve the practical need. In this paper, we formulate the Minimum-Latency Multisource Broadcast problem. We propose a novel solution using a fixed shared backbone, which is independent of the message sources and can be used repeatedly to reduce the broadcast latency. To the best of our knowledge, our work is deemed the first attempt to design such a multisource broadcast algorithm with a derived theoretical latency upper bound.

Adaptive-modulation transceivers have been widely used in wireless communications nowadays. The tradeoff between symbol error rate and data rate can be tuned by adjusting the constellation size. In this paper, we propose a constellation subset selection (CSS) approach and design the novel efficient approximation algorithms to tackle the CSS problems. The approximation ratios for these algorithms are derived. The theoretical studies on how to control the target symbol error rate by selecting an appropriate parameter K are also presented. Monte Carlo simulation results show that our CSS scheme really can reach below the target error probability.

For the prevalent research in wireless sensor networks, the main objective is to maximize the lifetime of a sensor network subject to the battery-energy at the sensor nodes. Various heuristic approaches have been proposed to achieve this objective and many simulation results have been presented in the existing literature. However, hardly exists any analytic framework to govern this network lifetime issue. In this paper, we analytically determine the lifetime of a sensor network under different data reporting schemes. Those schemes include direct data reporting by each node to the sink or the base station, cluster-data reporting based on the hexagonal clustering with arbitrary cluster-heads, and cluster-data reporting based on the hexagonal clustering with centroid cluster-heads.We will evaluate the lifetimes of the sensor network under these different reporting methods analytically or via simulations. Moreover, the effects of both path-loss exponent and compression-ratio on the network performances subject to these aforementioned schemes will also be investigated.

Orthogonal frequency division multiplexing (OFDM) is a prevalent telecommunication technology to mitigate the common multi-path problem and it is widely adopted with high-order modulations such as quadrature amplitude modulation (QAM) in many communication systems. However, uncoded OFDM systems have a serious drawback of high peak-to-mean-envelope-power ratio (PMEPR). On the other hand, coded OFDM systems, although mitigating the PMEPR problem, often lead to low code rates. Obviously, there exists a tradeoff between PMEPR and code rate in the design of OFDM systems. Nevertheless, hardly exists any approach to address this tradeoff so far in the literature. In this paper, a new general design framework for OFDM M-QAM sequences is proposed, in which the constellation size M can be any arbitrary radix-4 number (i.e. M = 4h) and the sequence length n can be any radix-2 number (i.e. n = 2m). Theoretical studies on PMEPR and code rate are presented so that both metrics can be determined for arbitrary radix-4 M and radix-2 n. This new general approach can be used to construct numerous families of sequences achieving low PMEPR, high code rate, or balancing these two metrics. Our proposed novel general design framework can be deemed very promising for the future OFDM transmission systems.

The connected dominating set (CDS) has been extensively used for routing and broadcast in wireless ad hoc networks. While existing CDS protocols are successful in constructing CDS of small size, they either require localized information beyond immediate neighbors, lack the mechanism to properly handle nodal mobility, or involve lengthy recovery procedure when CDS becomes corrupted. In this paper, we introduce the timer-based CDS protocols, which first elect a number of initiators distributively and then utilize timers to construct a CDS from initiators with the minimum localized information. We demonstrate that our CDS protocols are capable of maintaining CDS in the presence of changes of network topology. Depending on the number of initiators, there are two versions of our timer-based CDS protocols. The Single-Initiator (SI) generates the smallest CDS among protocols with mobility handling capability. Built on top of SI, the Multi-Initiator (MI) version removes the single point of failure at single-initiator and possesses most advantages of SI. We evaluate our protocols by both the ns-2 simulation and an analytical model. Compared with the other known CDS protocols, the simulation results demonstrate that both SI and MI produce and maintain CDS of very competitive size. The analytical model shows the expected convergence time and the number of messages required by SI and MI in the construction of CDS, which match closely to our simulation results. This helps to establish the validity of our simulation.

In order to mitigate the overhead of the routing protocols in any large-scale network, the hierarchical protocol has been proposed in the early 1980's. However, the message relay would entail the huge throughput reduction in such a hierarchical network. Thanks to the recently developed network coding techniques, a high-throughput low-complexity hierarchical protocol can be facilitated due to the multiple-source relay-based data transmissions built on the network coding schemes, especially for the data communications between the adjacent network levels. In this paper, we will apply the random geometry theory to evaluate the network performance of the proposed hierarchical routing method in the statistical average sense. Three essential measures, namely routing complexity, end-to-end throughput and average network throughput, are formulated and derived thereby. The numerical results demonstrate that the significant improvements in terms of these three network performance measures can be achieved by the proposed hierarchical routing protocol using network coding according to our new statistical analysis.

Orthogonal frequency division multiplexing (OFDM) is a prevalent telecommunication technology to mitigate multipath distortion with high-order modulations such as quadrature amplitude modulation (QAM). However, uncoded OFDM systems also have a serious drawback of high peak-to-mean envelope power ratio (PMEPR). On the other hand, coded OFDM systems can reduce the PMEPR problem but often lead to low code rates. There is thus a tradeoff between PMEPR and code rate in the design of OFDM systems. In this paper, PMEPR reduction for OFDM 64- and 256-QAM sequences is comprehensively studied. Four new families of 64-QAM sequences and seven new families of 256-QAM sequences are proposed to achieve the lowest PMEPR, the highest code rate, or the tradeoffs between these two metrics. Through the comparison with all other OFDM 16- or 64-QAM sequences, these new families of OFDM sequences can facilitate higher code rates. Furthermore, many of these new sequences have lower PMEPR than other OFDM sequences. Adjustment of the tradeoff between PMEPR and code rate can be made to meet the stringent demand in low PMEPR or the need for high code rate subject to various system requirements. Moreover, the construction method of the proposed new sequences is quite simple.

Adaptive modulation communication systems have been popular nowadays. The tradeoff between the symbol error rate and the data rate resulting from the constellation option is crucial in adaptive modulation. In this paper, we propose a constellation subset selection (CSS) approach to seek this tradeoff and design novel efficient approximation algorithms to tackle the CSS problems. The new theorems and studies on the algorithmic and systematic aspects for the constellation subset selection are facilitated. Our attempt to cope with the CSS problems would be valuable for the future communication systems with adjustable constellation sets.

Beaconing is a primitive communication task in which every node locally broadcasts a packet to all its neighbors within a fixed distance. Assume that all communications proceed in synchronous time-slots and each node can transmit at most one fixed-size packet in each time-slot. The problem Minimum-latency beaconing schedule (MLBS) in multihop wireless networks seeks a shortest schedule for beaconing subject to the interference constraint. MLBS has been intensively studied since the mid-1980s, but all assume the protocol interference model with uniform interference radii. In this paper, we first present a constant-approximation algorithm for MLBS under the protocol interference model with arbitrary interference radii. Then, we develop a constant-approximation algorithm for MLBS under the physical interference model. Both approximation algorithms have efficient implementations in a greedy first-fit manner.

In multi-hop wireless networks, the use of virtual backbone can greatly simplify routing, broadcasting, as well as energy/bandwidth saving. However, constructing a virtual backbone is costly and time-consuming because of the inevitable transmission interference during the process of the construction. In the literature, most of virtual backbone construction algorithms did not take the interference issue into consideration. To the best of our knowledge, our proposed algorithm is the first fully-distributed, interference-aware virtual backbone construction algorithm that has a proven bound on the construction latency. Besides, our proposed algorithm can be applied to the leader election problem, and such application results in a fully-distributed and interference-aware leader election algorithm of time complexity O(n \log n) (where n is the number of nodes). This new leader election algorithm is practical in wireless networks because interference has already been dealt with; is also results in the fastest interference-aware leader election algorithm to the best of our knowledge.

In this paper, we propose a new family of 64-QAM based sequences for achieving the lowest PMEPR and the highest code rate compared to all other 64-QAM based schemes, which can be applied for OFDM systems. The construction of the proposed sequences is simple and the theoretical analysis is presented.

We studied the minimum latency gossiping (all-to-all broadcast) problem in multihop radio networks defined as follows: Each node in the network is preloaded with a message and the objective is to distribute each node's message to the entire network with minimum latency. We studied this problem in the unit-size message model and the unit disk graph model. The unit-size model means different messages cannot be combined as one message, and the unit disk graph model means a link exists between two nodes if and only if their euclidean distance is less than 1. The minimum latency gossiping problem is known to be NP-hard in these two models. In this work, we designed a gossiping scheme that significantly improved all current gossiping algorithms in terms of the approximation ratio. Our work has approximation ratio 27, a great improvement of the current state-of-the-art algorithm (which has ratio 1,947). We also discussed the single point of failure problem and its impact on our approximation ratio. We designed an amended gossiping algorithm with ratio 27 in case of a nonsource node failure. We also designed an amended gossiping algorithm with ratio 29 in case of source failure.

In this paper, we study the minimum-latency broadcast scheduling problem in the probabilistic model. We establish an explicit relationship between the tolerated transmission-failure probability and the latency of the corresponding broadcast schedule. Such a tolerated transmission-failure probability is calculated in the strict sense that the failure to receive the message at any single node will lead to the entire broadcast failure and only if all nodes have successfully received the message do we consider it a success. We design a novel broadcast scheduling algorithm such that the broadcast latency is evaluated under such a strict definition of failure. The latency bound we derive is a strong result in the sense that our algorithm achieves a low broadcast latency under this rather strict broadcast-failure definition. Simulation results are also provided to justify our derived theoretical latency bound.

In this project, we developed an adaptive multihop clustering algorithm MaxLife for sensor networks. MaxLife significantly improves sensor network lifetime by balancing energy dissipation and minimizing energy consumption at the same time. The algorithm is compared to Random and MinEnergy algorithms and shows great performance gain. Random is extended from its original design of single hop clustering in (Wendi Rabiner Heinzelman et al., 2000) to multihop clustering, which elects cluster heads with absolute fairness. However, the idea of rotating the role of cluster heads does not work well in a multihop environment, because relay nodes can also drain out energy quickly. MinEnergy chooses cluster heads to minimize total energy consumption, which leads to large energy disparity and hurts long-term performance. MaxLife on the other hand, uses global optimization techniques and directly maximizes network lifetime. Simulation results verified that MaxLife achieves the best tradeoff between fairness and energy efficiency, and the clustering topology computed from it has significantly longer lifetime than those from the other two algorithms.

Minimum-latency aggregation schedule (MLAS) in synchronous multihop wireless networks seeks a shortest schedule for data aggregation subject to the interference constraint. In this paper, we study MLAS under the protocol interference model in which each node has a unit communication radius and an interference radius ρ ≥ 1. All known aggregation schedules assumed ρ = 1, and the best-known aggregation latency with ρ = 1 is 23R + Δ - 18 where R and Δ are the radius and maximum degree of the communication topology respectfully. In this paper, we first construct three aggregations schedules with ρ = 1 of latency 15R + Δ - 4, 2R + O(log R) + Δ and (1 + O(log R/3√R)) R + Δ respectively. Then, we obtain two aggregation schedules with ρ > 1 by expanding the first two aggregation schedules with ρ = 1. Both aggregation schedules with ρ > 1 have latency within constant factors of the minimum aggregation latency.

In this paper, we study the channel-aware minimum-latency broadcast scheduling problem using the probabilistic model. We establish an explicit relationship between the tolerated transmission-failure probability and the latency of the corresponding broadcast schedule. Such a tolerated transmission-failure probability is calculated in the strict sense that the failure to receive the message at any single node will lead to the entire broadcast failure and only if all nodes have successfully received the message, do we consider it a successful broadcast. We design a novel reconfigurable broadcast scheduling algorithm such that the latency is evaluated under such a strict definition of failure. Our derived latency bound associated with this new randomized algorithm is substantial to guarantee the low broadcast latency for the complete broadcasting success thereby.

We studied the minimum-latency gossiping (all-to-all broadcast) problem in multi-hop wireless networks defined as follows. Each node in the network is initially given a message and the objective is to design a minimum-latency schedule such that each node distributes its message to all other nodes. We considered the unit-size message model, in which different messages cannot be combined as one message, and the unit disk graph model, in which a link exists between two nodes if and only if their Euclidean distance is less than 1. This problem is known to be NP-hard in such models. In this work we designed a gossiping scheme that significantly improved all current gossiping algorithms in terms of approximation ratio. Our work has approximation ratio 27, a great improvement of the current state-of-the-art algorithm (which has ratio 1000+).

Broadcast is a fundamental operation in wireless networks and naive flooding is not practical because it cannot deal with interference. Scheduling is a good way to avoid interference, but previous studies on broadcast scheduling algorithms all assume highly theoretical models such as the unit disk graph model. In this work, we re-investigate this problem using the 2-disk and the signal-to-interference-plus-noise-ratio (SINR) model to realize it. We first design a constant approximation algorithm for the 2-disk model and then extend it to the SINR model. This result is the first result on broadcast scheduling algorithms in SINR model, to the best of our knowledge.

A wide range of applications for wireless ad hoc networks are time-critical and impose stringent requirement on the communication latency. This paper studies the problem Minimum-Latency Broadcast Scheduling (MLBS) in wireless ad hoc networks represented by unit-disk graphs. This problem is NP-hard. A trivial lower bound on the minimum broadcast latency is the radius R of the network with respect to the source of the broadcast, which is the maximum distance of all the nodes from the source of the broadcast. The previously best-known approximation algorithm for MLBS produces a broadcast schedule with latency at most 648 R. In this paper, we present three progressively improved approximation algorithms for MLBS. They produce broadcast schedules with latency at most 24 R -23, 16 R -15, and R + O (log R) respectively.

Data aggregation is a fundamental yet time-consuming task in wireless sensor networks. We focus on the latency part of data aggregation. Previously, the data aggregation algorithm of least latency [1] has a latency bound of (Delta - 1)R, where Delta is the maximum degree and R is the network radius. Since both Delta andRcould be of the same order of the network size, this algorithm can still have a rather high latency. In this paper, we designed an algorithm based on maximal independent sets which has an latency bound of 23R+ Delta - 18. Here Delta contributes to an additive factor instead of a multiplicative one; thus our algorithm is nearly constant approximation and it has a significantly less latency bound than earlier algorithms especially when Delta is large.

802.11 standards support high data rates for a low price and thus provides an economical way for WLANs. On the other hand, 3G standards offer a much wider area of coverage that enables ubiquitous connectivity. The integration of them takes advantages from both sides and offers the possibility of achieving anywhere, anytime cost-efficient Internet access. To facilitate such integration, seamless vertical handoff is one of the major challenges because it needs to make physical movement transparent to mobile users and preserves application-level connectivity. Previous works did not consider the impact of authentication mechanisms on the performance of vertical handoff, especially on its delay. In a 3G-WLAN integration environment, since 3G and WLAN may use different authentication servers, when a mobile terminal hands over across them, certain authentication procedure needs to be performed. According to the literature, such authentication delay may be as high as hundreds of milliseconds, which is intolerable for delay-sensitive applications. We present seamless authentication protocols (SAPs) for vertical handoff in wireless heterogeneous networks, to reduce this delay. Simulation results show that SAP significantly reduces the delay caused by authentication procedures in vertical handoff.

This paper presents various new techniques on secure group communication schemes. We present a new broadcast encryption scheme RBE, being particularly efficient in multiple revocation, and a node-based key pre-distribution scheme, remedying the key overlapping problem of pool-based schemes. Starting with a detailed analysis on broadcast encryption and group key distribution schemes, we discuss the influence of join as well as the feasibility of including it in broadcast encryption schemes by means of performing full updating or overprovisioning.

Cryptographic protocols have been widely used to protect communications over insecure network environments. Existing cryptographic protocols usually contain flaws. To analyze these protocols and find potential flaws in them, the secure properties of them need be studied in depth. This paper attempts to provide a new framework to analyze and prove the secure properties in these protocols. A number of predicates and action functions are used to model the network communication environment. Domain rules are given to describe the transitions of principals' knowledge and belief states. An example of public key authentication protocols has been studied and analysed.