Artificial intelligence (AI) cameras are edge devices with embedded graphics processing units that can run lightweight deep learning models. In traffic management applications, traffic flow and traffic incidents can be detected from roadside images with the use of AI cameras, and only detected high-level information is sent to the server to minimize the use of network bandwidth and server resources. However, because edge devices are computationally limited, models should be optimized before they are deployed to these AI cameras. In addition, environment-related parameters must be configured appropriately after model deployment. Thus, an AI camera management system is required. Consequently, in this study, we designed a deployment and management system for AI cameras; this system can perform model optimization and parameter configuration with ease. The main functions of this system involve 1) automatic modeling and code transfer, 2) the remote deployment of deep learning models, 3) the remote configuration of relevant applications, and 4) the presentation of analytical results on a graphical user interface. The performance of the developed system was investigated by using it to deploy traffic analysis models and visualize analysis results. The experimental results indicate that this system achieved all of its design goals.

Vehicle trajectory collection is critical for intelligent transportation systems and tasks such as driving behavior analysis, travel time measurement, and traffic planning. Object tracking through computer vision can be used to obtain vehicle trajectories; however, trajectory information collected from a single camera is limited because of the camera's limited field of view. In multi-target multi-camera (MTMC) tracking, multiple camera views are integrated to associate various trajectories to a single vehicle by matching the vehicle's appearance with the trajectories. These cameras might have overlapping or nonoverlapping fields of view. Trajectory information from MTMC tracking can be used for driving behavior analysis, traffic congestion estimation, and route planning. However, color tones and angles differ between cameras; thus, trajectory association is challenging. In MTMC tracking, appearance, spatial, and temporal information can be integrated to reduce identification failures. This paper proposes a trajectory association framework for travel time and traffic flow estimation. The effects of spatial and temporal information on performance were evaluated for the AI City Challenge dataset and a self-collected dataset. The F1 scores obtained for these two datasets were 0.917 and 0.897, respectively. The inclusion of spatial and temporal information improved the F1 scores by approximately 0.06-0.72. The errors for estimating travel time and vehicle behavior (turning or straight movement) were approximately 3 sand 15 %, respectively, for various camera angles.

With the recent progress in sports analytics, deep learning approaches have demonstrated the effectiveness of mining insights into players' tactics for improving performance quality and fan engagement. This is attributed to the availability of public ground-truth datasets. While there are a few available datasets for turn-based sports for action detection, these datasets severely lack structured source data and stroke-level records since these require high-cost labeling efforts from domain experts and are hard to detect using automatic techniques. Consequently, the development of artificial intelligence approaches is significantly hindered when existing models are applied to more challenging structured turn-based sequences. In this paper, we present ShuttleSet, the largest publicly-available badminton singles dataset with annotated stroke-level records. It contains 104 sets, 3,685 rallies, and 36,492 strokes in 44 matches between 2018 and 2021 with 27 top-ranking men's singles and women's singles players. ShuttleSet is manually annotated with a computer-aided labeling tool to increase the labeling efficiency and effectiveness of selecting the shot type with a choice of 18 distinct classes, the corresponding hitting locations, and the locations of both players at each stroke. In the experiments, we provide multiple benchmarks (i.e., stroke influence, stroke forecasting, and movement forecasting) with baselines to illustrate the practicability of using ShuttleSet for turn-based analytics, which is expected to stimulate both academic and sports communities. Over the past two years, a visualization platform has been deployed to illustrate the variability of analysis cases from ShuttleSet for coaches to delve into players' tactical preferences with human-interactive interfaces, which was also used by national badminton teams during multiple international high-ranking matches.

AI cameras are edge devices that can execute lightweight deep learning models with embedded GPU devices. In traffic management applications, traffic flow and traffic incidents can be detected from roadside images by AI cameras, and only the detected high-level information needs to be sent back to the server to avoid network bandwidth consumption and spare server resources. However, due to limited hardware resources at edge devices, the models should be optimized for specific AI cameras before they are deployed. In addition, the environment-related parameters need to be configured properly after model deployment. These tasks call for an AI camera management system. In this research, we design a management and deployment traffic monitoring system which can accomplish model optimization and parameter configuration with ease. Except for the camera hardware installation, other main functions can be called remotely from the management system, including 1) Automatic modeling and code transfer generation; 2) Remote deep learning model deployment; 3) Remote application configuration; 4) Analysis result presentation with a graphical user interface. To validate our proposed system, the embedded GPU devices, including NVIDIA Jetson TX2 and AGX Xavier combined with roadside cameras, are used as the prototype of the AI cameras, and the deployment of intersection flow analysis models and the visualized analysis results are conducted by the proposed system. The experiments validate that the proposed management system achieves all the design goals.

In this study, an affordable data collection solution is proposed for the tactical and strategic analysis of badminton. To make mass technical data collection possible, broadcast video is considered as the data source, and an intuitive and efficient video labeling tool is designed and implemented. The contribution of this work includes three folds. First, in response to the needs of the next generation of badminton technical and tactical analysis, the concept of Shot-By-Shot Labeling is proposed and a prototype data representation is formulated. Second, UI designs and computer vision techniques are utilized to develop an efficient computer-aided labeling tool for shot-by-shot technical data collection from match videos. Third, a Shot-By-Shot Labeling dataset composed of six badminton matches is shared with the community to accelerate related research. The dataset is available at https://drive.google.com/drive/folders/1eweBFa_M_CnYcqkQ5IHJ-Y8ag3TqRwUh.

Simultaneously controlling the signs of each intersection in the arterial road sections grouping based on the concept of arterial signal progression is the trend of traffic control over the past few years since traffic conditions are usually regional and diffuse, and the regulation of a single intersection sign can only achieve limited improvement. While adjusting a signal controller using traditional method, there are multiple parameters needed to be confirmed and set. To further control the intersection of other continuing sections, it is required to switch the signs sequentially by entering different intersection operation interfaces, which not only has a higher error rate, but also makes it difficult to relieve the traffic flow at the first moment since there will be a time lag in the change of the signal at each intersection. In order to solve this problem, we propose a sensing-active event script operation mode and a UI design based on arterial traffic signal control on the basis of the existing traffic log network. When the system detects changes in the performance of road sections (heavy traffic or congestion), it will trigger the number control adjustment mechanism, which links the website controlled by the real-time signal sent through the network system to the communication group in the operator's mobile phone. This paper takes Chiayi County as the field demonstration. Through our proposed sensing-active event script operation mode and UI-based arterial traffic signal control, the work efficiency of the operator has increased, and the rate of input error in the number of seconds of the sign has reduced that thus, relieved the traffic flow at once.

Continuous monitoring of road surface quality is necessary to maintain high functionality of the entire road networks and allow users to perceive road roughness. Although several fundamental methods have been used to evaluate road roughness by employing smart probe cars, the accuracy of these methods is affected by factors, such as vehicle speed, sensor positions, and vehicle suspension systems. Also, the long-term application of these methods to the entire road network is also limited due to the high cost. Further, the widely used roughness indices do not reflect road users’ perception about road roughness as these indices are also affected by the accuracy of the roughness evaluation methods. Therefore, we propose a crowdsourcing based road roughness evaluation model which uses power spectral density accompanied with blind source separation technique to eliminate the vehicle effects. We also propose a road surface ranking based on majority voting algorithm for comparing roads based on their surface quality. Finally, the road surface roughness index is derived to widen the range of quality scale and capture roughness at fine granularity. The models are tested by real world experiments on different roads in Taiwan. The results show that the proposed model can accurately measure the roughness of roads, rank these roads and index them accordingly in a way that shows tiny differences in the road surface quality.

Traditional license plate recognition technology mostly uses traditional image processing methods to find out the characteristics of the license plate, and then crop and recognize the characters. The process needs to be modified due to the different environments, scenes and conditions. In recent years, many studies have implemented license plate and character recognition by using deep learning algorithms. Although it has a good recognition accuracy, the calculation speed still cannot reach the level of real-time recognition. This research proposes a real-time license plate recognition system based on YOLOv3, which uses deep learning model to realize the vehicle license plate recognition, lane identification and vehicle trajectory tracking. In this study, a web-based platform is established to present the result of license plate recognition and trajectory, and the streaming roadside video in the campus. In the platform, license plates of driving vehicles can be identified in real-time, and the user can search and track specific vehicle intuitively. In the experiment, the average accuracy of the system performs 84.3% in real-time license plate recognition, and 100% in lane identification. The system can process in 40 FPS, which can meet the level of real-time system. In the future, the system can cooperate with traffic access control in campus or community to improve the efficiency of traffic control.

The application of voice services has become more common in daily life, including traffic navigation, voice assistants, audio books and so on. However, considering the cost and variability, it is difficult to fully utilize real voice recordings in different scenarios. In practice, speech synthesis technology is usually used to mimic human voices; On the other hand, with the development of computer equipment, the computing power of edge devices has also gradually improved, which enables light deep-learning network inference. Currently, many deep learning technologies have been ported to edge devices to create different applications, such as face recognition, speech recognition, and photo retouching. Therefore, if the speech synthesis network is ported to edge devices, with the advent of the fifth generation mobile communication generation (5G), it would be able to provide more innovative basis for voice services. In this research, the speech synthesis network Tacotron2 [1] + CBHG [2] will be ported to edge device and aims to optimize the model inference time and amount of parameters. The model optimization would be based on the compression of deep learning network, quantization, structured pruning and low-rank matrix approximation techniques to allow the speech synthesis network working effectively on edge devices. On the other hand, we get over the difference in library support between TensorFlow 1.5 and TensorFlow Lite. After the compression of the model, the inference speed of the Tacotron2 speech synthesis network on edge device is increased by 1.91 times, while the model size is reduced by 86% respectively.

Fast and reliable communication plays a major role in the success of smart shopping applications. In a “Just Walk Out” shopping scenario, a video camera is installed on the cart to monitor shopping activities and transmit images to the cloud for processing so that items in the cart can be tracked and checked out. This paper proposes a prototype of a smart shopping cart based on image-based action recognition. Firstly, deep learning networks such as Faster R-CNN, YOLOv2, and YOLOv2-Tiny are utilized to analyze the content of each video frame. Frames are classified into three classes: No Hand, Empty Hand, and Holding Items. The classification accuracy based on Faster R-CNN, YOLOv2, or YOLOv2-Tiny is between 93.0% and 90.3%, and the processing speed of the three networks can be up to 5 fps, 39 fps, and 50 fps, respectively. Secondly, based on the sequence of frame classes, the timeline is divided into No Hand intervals, Empty Hand intervals, and Holding Items intervals. The accuracy of action recognition is 96%, and the time error is 0.119s on average. Finally, we categorize the events into four cases: No Change, placing, Removing, and Swapping. Even including the correctness of the item recognition, the accuracy of shopping event detection is 97.9%, which is higher than the minimal requirement to deploy such a system in a smart shopping environment. A demo of the system and a link to download the data set used in the paper are in Smart Shopping Cart Prototype or found at this URL: https://hackmd.io/abEiC83rQoqxz7zpL4Kh2w.

Real-time traffic video streaming, such as roadside surveillance and aerial video, has been widely used in traffic monitoring nowadays. However, most of the traditional traffic data collection methods lack mobility that can only collect macroscopic data. In this paper, an intelligent traffic monitoring system based on an open source cooperative platform called SAGE2 was developed. Based on the integrated big screen TV wall of SAGE2, a map-based aerial traffic video streaming management interface was designed. In the image pre-processing section, it provides functions such as lens distortion removal, top view projection transforms, and video stabilization; simulate video streaming to provide instant and long-term micro-flow data collection. Micro-traffic flow data provides high-resolution information both in time and space which can be used to analyze the driving behavior of individuals and the public. Combined with the lane level map, it can provide a variety of visual vehicle flow presentations, such as intersection traffic distribution that can also be used to develop an innovative application in the future.

Self-checkout systems enable retailers to reduce costs and customers to process their purchases quickly without waiting in queues. However, existing self-checkout systems suffer from design problems as they require large hardware consisting of a camera, sensors, RFID and other IoT technologies which increases the cost of such systems. Therefore, we propose a smart shopping cart with self-checkout, called iCart, to improve customer's experience at retail stores by enabling just walk out checkout and overcome the aforementioned problems. iCart is based on mobile cloud computing and deep learning cloud services. In iCart, a checkout event video is captured and sent to the cloud server for classification and segmentation where an item is identified and added to the shopping list. The Linux based cloud server contained the yolov2 deep learning network. iCart is a lightweight system of low cost solution which is suitable for the small-scale retail stores. The system is evaluated using real-world checkout video, and the accuracy of the shopping event detection and item recognition is about 97%. iCart demo can be found at URL: http://nol.cs.nctu.edu.tw/iCart/index.html.

Computer vision based object tracking has been used to annotate and augment sports video. For automatically and systematically competition data collection and tactical analysis. The proposed project also includes research of data visualization, connected training auxiliary devices, and data warehouse. Deep learning techniques will be used to develop video-based real-time microscopic competition data collection based on broadcast competition video. Machine learning techniques will be used to develop tactical analysis. In addition, training auxiliary devices including smart badminton rackets and connected serving machines will be developed based on the IoT technology to further utilize competition data and tactical data and boost training efficiency. Especially, the connected serving machines will be developed to perform specified tactics and to interact with players in their training.

Over the decades, fitness activities and extreme endurance events are expanding throughout the world. The number of available public skeletal repositories and recognition/evaluation benchmarks has grown rapidly since Microsoft manufactured a motion sensing device called Kinect. Kinect RGBD data has become a very useful representation of an indoor scene for solving activity/fitness recognition problems. The other alternative sensor which has been utilized widely in this area is the wearable inertial measurement unit (IMU) sensor. With numerous advance sensors with mass adoption, this technology represents a possible approach to surpass current activity recognition and evaluation research solutions. Nevertheless, there is a limited number of publicly available datasets where depth camera, inertial sensor, and RGB image data are captured at the same time. In this paper, we introduce NCTU-MFD (National Chiao Tung University Multisensor Fitness Dataset), a comprehensive, diverse multisensor dataset collected using Kinect RGBD sensor, wearable inertial sensors, and web cameras. The dataset contains 47131 RGB images, 47131 depth images, and 100 csv files including 47131 skeletal data (from 25 joints) collected from Kinect sensor. In addition, our dataset also contains acceleration and gyroscope data from IMU sensors, and 94262 RGB images (47131 images from each web camera). To demonstrate the possible use of our dataset, we conduct an experiment on evaluation of depth maps.

Ball trajectory data are one of the most fundamental and useful information in the evaluation of players' performance and analysis of game strategies. It is still challenging to recognize and position a high-speed and tiny ball accurately from an ordinary video. In this paper, we develop a deep learning network, called TrackNet, to track the tennis ball from broadcast videos in which the ball images are small, blurry, and sometimes with afterimage tracks or even invisible. The proposed heatmap-based deep learning network is trained to not only recognize the ball image from a single frame but also learn flying patterns from consecutive frames. The network is evaluated on the video of the men's singles final at the 2017 Summer Universiade, which is available on YouTube. The precision, recall, and$F1$-measure reach 99.7%, 97.3%, and 98.5%, respectively. To prevent overfitting, 9 additional videos are partially labeled together with a subset from the previous dataset to implement 10-fold cross-validation, and the precision, recall, and$F_{1}$-measure are 95.3%, 75.7%, and 84.3%, respectively. The source code and dataset are available at https://nol.cs.nctu.edu.tw:234/open-source/TrackNet/.

The use of the badminton stroke strategy in the evenly matched game is often the key to victory. In this work, a smart racket based on wearable sensors is proposed to collect the data of swing of badminton. A cell phone APP with machine learning techniques is implemented to record stroke types automatically. In each stroke hit event, this prototype system uses Bluetooth earphone to collect the sound for detecting the accuracy time. It uses the data of IMU in each stroke for determining stroke type. Compared to EMU only solution, the system will reduce the false count of stroke hit. Using cloud techniques could record the training and game record in a long period. Overall the accuracy of stroke hit event is almost 100% by using voice print. The data of EMU is classified by Random Forest or SMO. The accuracy for personal model is 95.91%, and it is 7932% for general model. We develop a stroke record system which is combined with Wearable sensor, Mobile platform and Cloud service.

Public transportation is essential in people's daily life and it is crucial to understand how people move around the city. Some prior works have exploited GPS, Wi-Fi or bluetooth to collect data, in which extra sensors or devices were needed. Other works utilized data from smart card systems. However, some public transportation systems have their own smart card system and the smart card data cannot include all kinds of transportation modes, which makes it unsuitable for our study.Nowadays, each user has his/her own mobile phones and from the cellular data of mobile phone service providers, it is possible to know the uses' transportation mode and the fine-grained crowd flows. As such, given a set of cellular data, we propose a system for public transportation mode detection, crowd density estimation, and crowd flow estimation. Note that we only have cellular data, no extra sensor data collected from users' mobile phones. In this paper, we refer to some external data sources (e.g., the bus routing networks) to identify transportation modes. Users' cellular data sometimes have uncertainty about user location information. Thus, we propose two approaches for different transportation mode detection considering the cell tower properties, spatial and temporal factors. We demonstrate our system using the data from Chunghwa Telecom, which is the largest telecommunication company in Taiwan, to show the usefulness of our system.

As the aging population grows, the elderly care service has become an important part of the service industry in the aging population era. Activity monitoring is one of the most important services in the field of the elderly care service. In this paper, we proposed a wearable solution to provide an activity monitoring service on elders for caregivers. This service monitors restroom activities, such as washing hands, urinating and defecation. In the proposed solution, wireless motion sensors are wore on elder's wrist and waist to measure their body movement. The measured motion data are processed to statistical features and aggregated to cloud servers through gateways. A two-layer hierarchical framework is used for the activity recognition. In the first layer, a preliminary recognition is performed by a supervised Reduced Error Pruning (REP) Tree classifier to detect the transition of the activity. In the second layer, a Variable Order Hidden Markov Model (VOHMM) is proposed to determine the sequence of the activities. The experiment results show that the recognition accuracy is 70 percent. We developed a prototype service App to provide a life log for the recording of the activity sequence. The caregivers can make use of this information to take necessary actions accordingly.

Road networks are the most important facility to the public transportation in modern cities. Governments around the world allocate large amounts of budgets for the pavement maintenance every year. In this paper, we proposed a crowdsourcing solution to categorize road anomalies into safety related anomalies such as speed bumps and rumble strips, and dangerous anomalies such as bumps and potholes. The proposed system is composed of three parts: a smart probe car crowds (SPC-crowd) that serve as the anomaly data source; cloud servers that are the core for the anomaly classification; and application services that provide various innovative applications to facilitate the pavement maintenance. To support the crowdsourcing procedure, in the SPC-crowd side, we proposed cross-SPC techniques by adopting the underdamped oscillation model (UOM). In the cloud side, a supervised learning classification model was adopted on the anomaly data generated from the SPC-crowd. To validate the proposed system, extensive field trial was performed. The experimental results shown that our system can facilitate the pavement maintenance through the crowdsourcing solution.

Tocolysis is a treatment to prevent premature labor and thus can reduce the happening of perinatal and neonatal mortality. In developed and developing countries, the increasing of elderly primigravidae usually accompanies the increase in the preterm birth rate and therefore raises the need for tocolysis. To fulfill the increasing need, more tocolytic centers have been established, such as the one in Mackay Memorial Hospital, Taiwan. However, as emergent situations happen and doctors in charge are not on-site, a tele-cardiotocograph system is needed to help doctors to give proper advice by providing real-time CTG data. Currently, the solution practiced in Mackay Memorial Hospital is to send photos of the cardiotocogram to doctors by email or MMS. In this work, the team from NCTU and ITRI collaborated with Maya, Inc. to develop a remote vital sign access system called FetalCare to improve the solution in Mackay Memorial Hospital by utilizing mobile technology. With the developed system, doctors can remotely access real-time physiological data of patients via our app.

In most developed and developing countries, the maintenance of roadway pavement consumes considerable resources and represents a major item in government budget. However, due to the lack of sustainable and systematic approaches to implement long-term road pavement monitoring and assessment, the cost-effectiveness of performing such tasks is often a concern. In this paper, a crowdsourcing framework is proposed as a solution based on a smart probe car (SPC) system that utilizes mobile sensing technologies to collect environmental roadway data. Built upon the probe-vehicle system, the proposed method not only has the potential to save a significant amount of resources but also makes it possible to acquire real-time pavement information in a large scale.

The traditional electrocardiograph (ECG) is used to record heart activity under the supervision of doctors or well-trained medical personnel in the hospital or clinic. However, due to the advances in the MEMS technology in recent years, wearable ECG sensors are developed to collect ECG signals in daily life. The ECG signals can reveal the activity of the autonomic nervous system (ANS). The fluctuations in emotion may cause the enhancement of ANS, and further cause the rising of the heart rate. Hence, by investigating the heart rate data, we may understand how human emotion is affected by the outside environments or events. In this work, we measure the heart rate in two activities, including movie watching and adventure riding, which may cause people excited and nervous. The correlation between the heart rate and the activities are investigated. We propose to assess the exciting level of the activities via the heart rate data. We develop an algorithm to mark the exciting segments, and design questionnaires to understand how people feel in the activities. The experiment results show that the heart rate and the exciting level are positively correlated, and the exciting segments marked by the proposed algorithm are coincident with the answers from the questionnaires.

In crowdsourcing applications, the quality of the crowdsourced data is decisive to the success of subsequent system-level mining processes. We proposed a smartphone probe car (SPC) system to monitor road pavement. An SPC is essentially an ordinary vehicle with a mounted smartphone that runs sensing programs to objectively assess bumping caused by road anomalies such as potholes and bumps. The proposed system has several features. First, to allow dynamic forming of SPCs, we develop a signal processing heuristic for the extraction of the vertical acceleration components from the accelerometer readings (upon which bumping detection and road surface anomaly assessment rely). By these means, the proposed system provides a driver-friendly environment, requiring neither complicated installation nor driver-assisted training processes, and thus is possible to achieve hassle-free mass deployment such that drivers would be willing to participate in crowdsourcing. Second, based on the underdamped oscillation model, we propose a road anomaly indexing heuristic that is representable for road anomalies rather than vehicle conditions. This will later facilitate the system-level data mining processes in the servers. Third, a prototype SPC system was implemented and extensive field tests were undertaken to verify the performance of our system framework. Furthermore, we experimentally adopted a DENCLUE-like algorithm to mine road anomaly information from reported events to demonstrate any potential benefit from future investigation of data mining process at the system level. We believe the research works introduced in this paper consist the first step toward building an “ecosystem” of SPC-based crowdsourcing traffic and road monitoring applications.

The cycle lengths and signal transition time ofTraffic Light Systems(TLS’s), or known as thePhase Timing Information(PTI), play a key role in modern transportation systems. However, such information is not always available to the public. In this paper, we propose acrowdsourcingapproach to solve this problem by exploiting thestop and goevents, abbreviated bySGevents, of vehicles on roads happening in front of target traffic lights. The PTI discovery problem is formulated by allowing only part of the vehicles participating in the discovery process. The proposed framework starts with discovering SG events, followed by collapsing these events over multiple signal cycles into one and calculating PTI information through ashockwavetechnique. The crowdsourcing part may be directly implemented on smartphones. The proposed framework was verified via field trials and simulations. Our simulation results showed that, even with a low penetration rate around$3.8$percent, the root mean square errors of the cycle length, green light and red light signal transition time of a TLS are$0.04$,$1.3$and$5.8$seconds, respectively. The achieved accuracy can be helpful in many PTI-enabled applications.

Parallel, coordinated, and network-wide traffic management requires accurate and efficient traffic forecasting models to support online, real-time, and proactive dynamic control. Forecast accuracy is impacted by a critical characteristic of traffic flow, i.e., overdispersion. Efficiency depends on the time complexity of forecasting algorithms. Therefore, this paper proposes a novel spatiotemporal multivariate forecasting model that is based on the negative binomial additive models (NBAMs). Negative binomial is utilized to handle overdispersion, and additive models are used to efficiently smooth nonlinear spatial and temporal variables. To evaluate the model, it is applied to real-world data collected from Taipei City and compared with other forecasting models. The results indicate that the proposed model is an accurate and efficient approach in forecasting traffic flow in urban context where flow is overdispersed, autocorrelated, and influenced by upstream and downstream roads as well as the daily seasonal patterns, namely, low-, moderate-, and high-traffic seasons.

We propose the i-Traffic system that utilizes crowd sourced data from smartphones for the traffic flow mining by shockwave techniques. Shockwave is the propagation phenomenon of vehicle accumulation or relief on roads between two traffic flows with different speeds. The movement data of vehicles in front of an intersection are collected via smartphones for the shockwave identification. To conquer the low penetration problem when the number of the movement data is low, a folding heuristic is proposed by using traffic light cycle information to virtually increase the penetration of movement data. We implement our system on a client-server architecture and perform a small scale field trial experiment to demonstrate the system capability. Our results showed that our system is able to compute traffic information, including red/green light transition information and vehicle arrival rate with mean absolute errors of 5.0/0.6 seconds and 2.43 vehicles per minute, respectively under a low penetration rate of 1.2%.

Crowdsourcing is a new trend for pervasively discovering traffic information due to its low deployment and maintenance cost as compared with traditional infrastructure-based approaches, e.g., loop detectors and CCTV. Mining techniques and the penetration rate of participators in the discovery process are two major issues in such approaches. In this work, we first point out the shockwave phenomenon occurring in signalized traffic can be used to discover useful traffic information including traffic light information and vehicle flow information. To reduce the requirement on the penetration rate, a folding heuristic is proposed. The proposed concepts are verified via extensive simulations, especially on the penetration rate issue. Our results show that shockwave models are useful to extract traffic information from crowdsourced data, and the folding technique can effectively reduce the requirement on the penetration rate. It is remarkable that the proposed approach can provide high quality information even at a penetration rate as low as 1.6%.

In mobile opportunistic networks, security is a major concern in consequence of store-carry-and-forward data dissemination. To guarantee that messages can be only accessed by authorized users, access control is a necessity. Fuzzy-IBE that has been proposed can provide group access control. In addition, if a sender wants to expose his/her message only to some members of his/her group, Fuzzy-IBE can provide a whitelist mechanism to further indicate which users in the group can access the data. Because overhead linearly increases with respect to the length of the whitelist, this mechanism is not sufficiently scalable as the whitelist becomes larger. In this work, we propose a Fuzzy-IBE based negative access control scheme (NAC) that allows users to selectively exclude specific members from accessing data dynamically. NAC, which does not require intensive calculation in mobile devices, is suitable for mobile opportunistic networks.

Recent developments in mobile techniques have enabled a great variety of Location Based Services (LBS). A high positioning accuracy is a fundamental requirement for precision LBS applications, e.g., precise LBS marketing in shopping malls or indoor emergency evacuation services with mobile devices. However, most offerable commercial positioning systems, such as GPS/GNSS and RF-based systems, can not provide positioning accuracy within one meter. In this work, a new positioning approach is proposed for mobile devices, Called Photo Positioning, it can provide a high accuracy positioning service. The “positioning” here means to find the location where a photo was taken by investigating the geometric relations between the images of points of interest (POI) in the photo and their location in the real world based on the principle of photo imaging. To implement a photo positioning system, three major components are needed, including a POI database, a method to recognize and locate POIs in a photo and an algorithm to calculate the position where the photo was taken from the POI information. A positioning algorithm based on the geometric similarity in photo imaging is presented in this work, and a prototype system is developed for Android smartphone platforms. Our experimental results shows that the average positioning error of the proposed photo positioning approach can be as low as 74.34 cm.

Vehicular Ad-hoc NETworks (VANETs) adopting Dedicated Short-Range Communications (DSRCs) have emerged as a preferred choice of network design for the Intelligent Transportation System (ITS). A possible application of the ITS is to disseminate emergency messages by multihop broadcast. Due to the high density and high mobility of vehicles, it is difficult to design an efficient broadcast protocol for VANETs in urban areas. In this work, we propose a broadcast protocol, named \emph{Streetcast}, to provide efficient broadcast service. Street maps are used to assist the selection of relay nodes, and multicast RTS (Request-To-Send) is adopted to protect wireless communications for providing high reliability. In addition, an adaptive beacon control heuristic is proposed to reduce beacon overheads. At last, we evaluate our broadcast protocol in a real roadmap scenario with real traffic flows. The simulation results show that the proposed broadcast protocol has a superior performance in terms of packet delivery ratio and the number of collisions under various traffic load patterns.

In most inertial motion tracking systems, motion directions are detected and measured by direction sensors such as magnetometers and gyroscopes. In this paper, we propose a motion tracking system, called g-sensor constellations, in which only g-sensors but no direction sensors are used. The g-sensor constellation is a loose coupling g-sensor system with rigid geometric topology. As few as three g-sensors are needed for motion tracking, including direction detection. The system is easy to be installed. No complicated calibrations are needed and the necessary information is the distances between sensors. The proposed framework can improve the accuracy of dead reckoning systems and help in the analyzing of traffic accidents and developing new human-computer interfaces. In our experiments, a g-sensor constellation composed of three g-sensors, which are located at the vertices of an equilateral triangle with edges of 0.3m and communicate with the processing unit via Bluetooth links, is built to verify the proposed technique.

In the past, although mobile devices were equipped with multiple radio interfaces, for the sake of power saving, only one was activated for data transmission. The idea of concurrent transmission via multiple radio interfaces has not been seriously studied. However, nowadays, power consumption no longer is a problem in many application scenarios, e.g. VANETs. In this work, we investigate the performance improvement of concurrent file transfer over two heterogeneous radio networks, e.g. WiFi and 3G. The traditional File Transfer Protocol is modified to utilize two heterogeneous radio connections and experiments are executed over the Internet and a 3G data network to measure the latency and average bandwidth. Our results show that it is possible to integrate the bandwidth of both radio networks.

In grid routing, the plane is tessellated into equal-sized square cells.Two cells are called neighbor cells if they share a common edge, and two nodes are called routing neighbors if they are in neighbor cells and within each other's transmission range.If communication parties are in the same cell, packets can be transmitted directly; otherwise, packets are forwarded to routing neighbors that are in cells closer to destination cells.As a greedy strategy, grid routing suffers the existence of local minima at which no neighbor nodes exist for relaying packets.To guarantee deliverability, in this paper, we investigate two vital parameters of grid routing, called the grid size and the transmission radius.Assume that nodes are represented by a Poisson point process with rate n over a unit-area square, and let l denote the grid size and r the transmission radius.First, we show that if l = β ln n/n for some constant β and r = √ 5l, then β = 1 is the threshold for deliverability.In other words, there almost surely do not exist local minima if β > 1 and there almost surely exist local minima if β < 1. Next, for any given β > 1, we give sufficient and necessary conditions to determine the critical transmission radius (CTR) for deliverability.Then, we show that as β ∼ = 1.092, the CTR r ∼ = 2.09 √ ln n/n is the minimum over all β > 1. Simulation results are given to validate this theoretical work.

A range assignment to the nodes in a wirelessad hocnetwork induces a topology in which there is an edge between two nodes if and only if both of them are within each other's transmission range. The critical transmission radius fork-connectivity is the smallestrsuch that if all nodes have the transmission radiusr, the induced topology isk-connected. In this paper, we study the asymptotic critical transmission radius fork-connectivity in a wirelessad hocnetwork whose nodes are uniformly and independently distributed in a unit-area square or disk. We provide a precise asymptotic distribution of the critical transmission radius fork-connectivity. In addition, the critical neighbor number fork-connectivity is the smallest integerlsuch that if every node sets its transmission radius equal to the distance between itself and itsl-th nearest neighbor, the induced (symmetric) topology isk-connected. Applying the critical transmission radius fork-connectivity, we can obtain an asymptotic almost sure upper bound on the critical neighbor number fork-connectivity.

In wireless ad hoc networks, relative neighborhood graphs (RNGs) are widely used for topology control. If every node has the same transmission radius, then an RNG can be locally constructed by using only one hop information if the transmission radius is set no less than the largest edge length of the RNG. The largest RNG edge length is called the critical transmission radius for the RNG. In this paper, we consider the RNG over a Poisson point process with mean density ¿ in a unit-area disk. Let ß0= ¿(1/(2/3 - ¿(3)/2¿)) ¿ 1.6. We show that the largest RNG edge length is asymptotically almost surely at most ß ¿(1n n/¿n) for any fixed ß > ß0and at least ß ¿(1n n/¿n) for any fixed ß0. This implies that the threshold width of the critical transmission radius is o (¿(1n n/n)). In addition, we also prove that for any constant ¿, the expected number of RNG edges whose lengths are not less than ß0¿(1n n+¿)/¿n is asymptotically equal to ß02/2 e-¿.

Thanks to the growing of the wireless networks, the video streaming application becomes a ubiquitous joyful service. In wireless communication networks, the service traffic spans across the wired and wireless domains. Hence, the service of quality (QoS) control becomes complicated. Generally, the QoS is manipulated by the receiving feedback from the mobile user equipments (UEs) to the streaming server. If the feedback latency can be shortened, the streaming service can be adapted according to the individual network condition timely. Meanwhile, a public streaming service is normally realized by multiple uni-casting streams instead of the multicasting ones over IP. To make the service more efficient, an input video session can be encoded as multiple-quality streams so that some UEs with a similar receiving condition can share streams with the same service quality. In this article, SPONGE (Stream Pooler Over a Network Graded Environment) is proposed to improve the adaptive streaming service across wired/wireless networks. SPONGE can alleviate the direct load from the original streaming server to the end UEs and make each UE get an adaptive streaming service according to its network condition timely by the reduced feedback latency of network conditions. Our simulation results show that SPONGE can react to network condition accurately and quickly so as to have a smooth and better playback quality at the end user site across wired/wireless networks.

Wireless sensor networks (WSNs) have been increasingly available for critical applications such as security surveil-lance and environmental monitoring. An important per-formance measure of such applications is sensing coverage that characterizes how well a sensing field is monitored by a network. Although advanced collaborative signal process-ing algorithms have been adopted by many existing WSNs, most previous analytical studies on sensing coverage are con-ducted based on overly simplistic sensing models (e.g., the disc model) that do not capture the stochastic nature of sens-ing. In this paper, we attempt to bridge this gap by explor-ing the fundamental limits of coverage based on stochastic data fusion models that fuse noisy measurements of multi-ple sensors. We derive the scaling laws between coverage, network density, and signal-to-noise ratio (SNR). We show that data fusion can significantly improve sensing coverage by exploiting the collaboration among sensors. In particu-lar, for signal path loss exponent of k (typically between 2.0 and 5.0), ρf = O(ρ1−1/kd), where ρf and ρd are the densi-ties of uniformly deployed sensors that achieve full coverage under the fusion and disc models, respectively. Our results help understand the limitations of the previous analytical re-sults based on the disc model and provide key insights into the design of WSNs that adopt data fusion algorithms. Our analyses are verified through extensive simulations based on both synthetic data sets and data traces collected in a real deployment for vehicle detection.

The iLamp system is a sensor-enhanced desk lamp with surface-tracking capability based on received light intensity. It consists of two components: lamp and bookmark. The bookmark is a ZigBee-enabled sensor node that can report its sensed light intensity to the lamp with a user-friendly interface and two-way communication capability. The lamp can use its LEDs to locate user's reading surface to which the bookmark is attached, move toward the surface, and further tune its luminous intensity to meet user's preference. We develop the geometrical model for surface tracking. iLamp demonstrates a new centimeter-level location-tracking system using light intensity alone without other extra media or devices.

In wireless ad hoc networks, greedy forward routing is a localized geographic routing algorithm in which one node discards a packet if none of its neighbors is closer to the destination of the packet than itself, or otherwise forwards the packet to the neighbor closest to the destination. If all nodes have the same transmission radii, the critical transmission radius for greedy forward routing is the smallest transmission radius which ensures packets can be delivered by greedy forward routing through any source-destination pair. In this paper, we study asymptotic critical transmission radii of randomly deployed wireless ad hoc networks. Assume network nodes are represented by a Poisson point process of density n over a unit-area convex compact region whose boundary curvature is bounded. We show that the ratio of critical transmission radii to radic (lnn/pin) is asymptotically almost surely equal to radic (1/ (2/3 - radic(3)/2pi)) ap 1.6.

Due to limitations on transmission power of wireless devices, areas with sparse nodes are decisive to some extreme properties of network topology. In this paper, we assume wireless ad hoc and sensor networks are represented by uniform point processes or Poisson point processes. Asymptotic analyses based on minimum scan statistics are given for some crucial network properties, including coverage of wireless sensor networks, connectivity of wireless ad hoc networks, the largest edge length of geometric structures, and local-minimum-free geographic routing protocols. We derive explicit formulas of minimum scan statistics. By taking the transmission radius as a major parameter, our results are applied to various network problems. This work offers a unified approach to solve various problems and reveals the evolution of network topology. In addition, boundary effects are thoroughly handled.

Relative neighborhood graph (RNG) has been widely used in topology control and geographic routing in wireless ad hoc networks. Its maximum edge length is the minimum requirement on the maximum transmission radius by those applications of RNG. In this paper, we derive the precise asymptotic probability distribution of the maximum edge length of the RNG on a Poisson point process over a unit-area disk. Since the maximum RNG edge length is a lower bound on the critical transmission radius for greedy forward routing, our result also leads to an improved asymptotic almost sure lower bound on the critical transmission radius for greedy forward routing.

Consider a random wireless ad hoc network represented by a Poisson point process over a unit-area disk with mean n. Let σn denote its critical transmission radius for greedy forward routing, and βo = 1/ (2/3 -- √3/2π) ≈ 1.62. It was recently proved that for any constant ε > 0, it is asymptotically almost sure that (1 -- ε) √βo in n/πn ≤ σn ≤ (1 + ε) √βo in n/πn. In this paper, we obtain tighter asymptotic bounds on σn. Specifically, we prove that for any constant c, the asymptotic probability of σn ≤ √βo in n + c/πn is at least 1 -- ( 1/1/βo--1/3 -- βo/2) e -c and at most e -βo/2 e -- c. Consequently, for any positive sequence (εn : n ≥ 1) with εn = o(In n) and εn → ∞, it is asymptotically almost sure that √βo in n --εn/πn ≤ σn ≤ √βo in n + εn/πn. We also conjecture that for any constant c, the asymptotic probability of σn ≤ √βo 1n n + c/σn is exactly exp (--(1/1/βo--1/3 -- β;o/2) e --c).

In randomly-deployed wireless ad hoc networks with reliable nodes and links, vanishment of isolated nodes asymptotically implies connectivity of networks. However, in a realistic system, nodes may become inactive, and links may become down. The inactive nodes and down links cannot take part in routing/relaying and thus may affect the connectivity. In this paper, we study the connectivity of a wireless ad hoc network that is composed of unreliable nodes and links by investigating the distribution of the number of isolated nodes in the network. We assume that the wireless ad hoc network consists ofnnodes which are distributed independently and uniformly in a unit-area disk or square. Nodes are active independently with probability 0p1les1, and links are up independently with probability 0p2les1. A node is said to beisolatedif it doesn't have an up link to an active node. We show that if all nodes have a maximum transmission radiusrn=radiclnn+xi/pip1p2nfor some constant xi, then the total number of isolated nodes is asymptotically Poisson with meane-xiand the total number of isolated active nodes is also asymptotically Poisson with meanp1e-xi. In addition, the work can be extended for secure wireless networks which adoptm-composite key predistribution schemes in which a node is said to beisolatedif it doesn't have a secure link. Letpdenote the probability of the event that two neighbor nodes have a secure link. We show that if all nodes have a maximum transmission radiusrn=radiclnn+xi/pipnfor some constant xi, then the total number of isolated nodes is asymptotically Poisson with meane-xi.

Greedy forward routing (abbreviated by GFR)in wireless ad hoc networks is a localized geographic routing in which each node discards a packet if one of its neighbors is closer to the destination of the packet than itself, or otherwise forwards the packet to the neighbor closest to the destination of the packet. If all nodes have the same transmission radii, the critical transmission radius for GFR is the smallest transmission radius which ensures that packets can be delivered between any source-destination pairs. In this paper, we study the asymptotic critical transmission radius for GFR in randomly deployed wireless ad hoc networks. We assume that the network nodes are represented by a Poisson point process of density n over a convex compact region of u it area with bounded curvature.Let ß0 = 1/ (⅔√3 over 2π) ≈ 1.62. We show that √ß0 1n n over πn is asymptotically almost surely (abbreviated by a.a.s.) the threshold of the critical transmission radius for GFR.I other words,for ß > ß0 if the trasmission radius is √ß 1n n over πn, it is a.a.s. packets can be delivered between any source-destination pairs; for any ß < ß0 if the transmission radius is √ß 1n noverπn, it is a.a.s. packets can't be delivered between some source-destination pair.

Nodes in wireless ad hoc networks may become inactive or unavailable due to, for example, internal breakdown or being in the sleeping state. The inactive nodes cannot take part in routing/relaying, and thus may affect the connectivity. A wireless ad hoc network containing inactive nodes is then said to be connected, if each inactive node is adjacent to at least one active node and all active nodes form a connected network. This paper is the first installment of our probabilistic study of the connectivity of wireless ad hoc networks containing inactive nodes. We assume that the wireless ad hoc network consists of n nodes which are distributed independently and uniformly in a unit-area disk, and are active (or available) independently with probability p for some constant 0

One of the main applications of wireless sensor networks is to provide proper coverage of their deployment regions. A wireless sensor network k-covers its deployment region if every point in its deployment region is within the coverage ranges of at least k sensors. In this paper, we assume that the sensors are deployed as either a Poisson point process or a uniform point process in a square or disk region, and study how the probability of the k-coverage changes with the sensing radius or the number of sensors. Our results take the complicated boundary effect into account, rather than avoiding it by assuming the toroidal metric as done in the literature.

Abstract Conflict‐free channel assignment is a classic and fundamental problem in wirelessad hocnetworks. It seeks an assignment of the fewest channels to a given set of radio nodes with specified transmission ranges without causing either primary collision or secondary collision. It is NP‐hard even when all nodes are located in a plane and have the same transmission radii. We observe that a prior analysis of the approximation ratio of a classic greedy heuristic, FIRST‐FIT in smallest‐last ordering, is erroneous. In this paper, we provide a rigorous and tighter analysis of this heuristic and other greedy FIRST‐FIT heuristics. We obtain an upper bound of 13 on the approximation ratios of both FIRST‐FIT in smallest‐last ordering and FIRST‐FIT in radius‐decreasing ordering. Such upper bound can be reduced to 12 if all nodes have quasi‐uniform transmission radii. When all nodes have equal transmission radii, we obtain an upper bound of 7 on the approximation ratios of FIRST‐FIT in smallest‐last ordering, FIRST‐FIT in distance‐increasing ordering, and FIRST‐FIT in lexicographic ordering. In addition, for nodes with equal transmission radii, we present a spatial divide‐and‐conquer heuristic with approximation ratios of 12. All these heuristics, except FIRST‐FIT in smallest‐last ordering, are modified to heuristics for maximum independent set with the same approximation ratios. Copyright © 2006 John Wiley & Sons, Ltd.

The problem min-power k-connectivity seeks a power assignment to the nodes in a given wireless ad hoc network such that the produced network topology is k-connected and the total power is the lowest. In this paper, we present several approximation algorithms for this problem. Specifically, we propose a 3k-approximation algorithm for any k /spl ges/ 3, a (k + 12H (k))-approximation algorithm for k(2k - 1) /spl les/ n where n is the network size, a (k + 2 [(k + 1)/2])-approximation algorithm for 2 /spl les/ k /spl les/ 7, a 6-approximation algorithm for k = 3, and a 9-approximation algorithm for k = 4.

This paper addresses the maximal lifetime scheduling problem in sensor surveillance networks. Given a set of sensors and targets in a Euclidean plane, a sensor can watch only one target at a time, our task is to schedule sensors to watch targets, such that the lifetime of the surveillance system is maximized, where the lifetime is the duration that all targets are watched. We propose an optimal solution to find the target watching schedule for sensors that achieves the maximal lifetime. Our solution consists of three steps: 1) computing the maximal lifetime of the surveillance system and a workload matrix by using linear programming techniques; 2) decomposing the workload matrix into a sequence of schedule matrices that can achieve the maximal lifetime; 3) obtaining a target watching timetable for each sensor based on the schedule matrices. Simulations have been conducted to study the complexity of our proposed method and to compare with the performance of a greedy method.

One of the main applications of wireless sensor networks is to provide proper coverage of their deployment regions. A wireless sensor network k-covers its deployment region if every point in its deployment region is within the coverage ranges of at least k sensors. In this paper, we assume that the sensors are deployed as either a Poisson point process or a uniform point process in a square or disk region, and study how the probability of the k-coverage changes with the sensing radius or the number of sensors. Our results take the complicated boundary effect into account, rather than avoiding it by assuming the toroidal metric as done in the literature.

Wireless ad hoc networks with Bernoulli nodes provide a unified model of various important problems including fault-tolerance, randomized construction of virtual backbone, randomized broadcast routing, and randomized wake/sleep management. We assume that the wireless ad hoc network consists of n nodes which are distributed independently and uniformly in a unit-area disk and are active (or available) independently with some constant probability /spl rho/. Let /spl rho//sub n/ denote the random variable which is the smallest transmission range at which the active nodes form a connected network, and p/sub n/' denote the random variable which is the smallest transmission range at which the active nodes form a connected network and each inactive node is adjacent to at least one active node, /spl rho//sub n/ is referred to as the critical transmission range for connectivity of active modes, and /spl rho//sub n/' is referred to as the critical transmission range for connectivity of all nodes. In this paper, we derive the precise asymptotic distributions of /spl rho//sub n/ and /spl rho//sub n/'.

Abstract Since no fixed infrastructure and no centralized management present in wireless networks, a connected dominating set (CDS) of the graph representing the network is widely used as a virtual backbone. Constructing a minimum CDS is NP‐hard. In this paper, we propose a new greedy algorithm, called S‐MIS, with the help of Steiner tree that can construct a CDS within a factor of 4.8 + ln5 from the optimal solution. We also introduce the distributed version of this algorithm. We prove that the proposed algorithm is better than the current best performance ratio which is 6.8. A simulation is conducted to compare S‐MIS with its variation which is rS‐MIS. The simulation shows that the sizes of the CDSs generated by S‐MIS and rS‐MIS are almost the same. Copyright © 2005 John Wiley & Sons, Ltd.

A range assignment to the nodes in a wireless ad hoc network induces a topology in which there is an edge between two nodes if and only if both of them are within each other’s transmission range. The critical transmission radius for kconnectivity is the smallest r such that if all nodes have the transmission radius r, the induced topology is k-connected. The critical neighbor number for k-connectivity is the smallest integer l such that if every node sets its transmission radius equal to the distance between itself and its l-th nearest neighbor, the induced topology is k-connected. In this paper, we study the asymptotic critical transmission radius for k-connectivity and asymptotic critical neighbor number for k-connectivity in a wireless ad hoc network whose nodes are uniformly and independently distributed in a unit-area square or disk. We provide a precise asymptotic distribution of the critical transmission radius for k-connectivity and an improved asymptotic almost sure upper bound on the critical neighbor number for k-connectivity.

Wieselthier et al. (2000) proposed three greedy heuristics for Min-Power Asymmetric Broadcast Routing: SPT (shortest-path tree), MST (minimum spanning tree), and BIP (broadcasting incremental power). Wan et al. (2001) proved that SPT has an approximation ratio of at least (n/2) where n is the total number of nodes, and both MST and BIP have constant approximation ratios. Based on the approach of pruning, Wieselthier et al. also proposed three greedy heuristics for Min-Power Asymmetric Multicast Routing: P-SPT (pruned shortest-path tree), P-MST (pruned minimum spanning tree), and P-BIP (pruned broadcasting incremental power). In this paper, we first prove that the approximation ratios of these three heuristics are at least (n-1/2),n-1, and n-2-o(1), respectively. We then present constant-approxiation algorithms for Min-Power Asymmetric Multicast Routing. We show that any /spl rho/-approximation Steiner tree algorithm gives rise to a c/spl rho/-approximation heuristic for Min-Power Asymmetric Multicast Routing, where c is a constant between 6 and 12. In particular, the Takahashi-Matsuyama Steiner tree heuristic leads to a heuristic called SPF (shortest-path first), which has an approximation ratio of at most 2c. We also present another heuristic, called MIPF (minimum incremental path first), for Min-Power Asymmetric Multicast Routing and show that its approximation ratio is between (13/3) and 2c. Both SPF and MIPF can be regarded as an adaptation of MST and BIP, respectively, in a different manner than pruning. Finally, we prove that any /spl rho/-approximation Steiner tree algorithm also gives rise to a 2/spl rho/-approximation algorithm for Min-Power Symmetric Multicast Routing.

Abstract We consider a large‐scale of wirelessad hocnetworks whose nodes are distributed randomly in a two‐dimensional region Ω (more specifically, a unit square). Givennwireless nodesV, each with transmission rangern, the wireless networks are often modeled by graphG(V,rn) in which two nodes are connected if and only if their Euclidean distance is no more thanrn. We first consider how to relate the transmission range with the number of nodes in a fixed area such that the resulted network can sustainkfault nodes in its neighborhood with high probability when all nodes have the same transmission range. We show that, for a unit‐area square region Ω, the probability that the networkG(V,rn) isk‐connected is at least${\rm e}^{-{\rm e}^{-\alpha}}$ when the transmission radiusrnsatisfies$n \pi r_n^2 \ge {\rm ln}\ n \,+ (2k - 3) {\rm ln}\, {\rm ln}\, n - 2 \,{\rm ln}(k - 1)! + 2 \alpha \ {\rm for} \, k >\,1$ andnsufficiently large. This result also applies to mobile networks when the moving of wireless nodes always generates randomly distributed positions. We also conduct extensive simulations to study the practical transmission range to achieve certain probability the network beingk‐connectivity, when the number of nodesnis not large enough. The relation between the minimum node degree and the connectivity of graphG(V,r) is also studied. Setting the transmission range of all nodes tornguarantees thek‐connectivity with high probability, but some nodes may have excessive number of neighbours in the graphG(V,rn). We then present a localized method to construct a subgraph of the network topologyG(V,rn) such that the resulting subgraph is stillk‐connected but with much fewer communication links maintained. We show that the constructed topology has onlyO(k · n) links and is a length spanner. Here a graphH ⊆ Gis spanner for graphG, if for any two nodes, the length of the shortest path connecting them inHis no more than a small constant factor of the length of the shortest path connecting them inG. Finally, we conduct some simulations to study the practical transmission range to achieve certain probability ofk‐connected whennis not large enough. Copyright © 2004 John Wiley & Sons, Ltd.

We consider a large-scale of wireless ad hoc networks whose nodes are distributed randomly in a two-dimensional region /spl Omega/. Given n wireless nodes V, each with transmission range r/sub n/, the wireless networks are often modeled by graph G(V, r/sub n/) in which two nodes are connected if their Euclidean distance is no more than r/sub n/. We show that, for a unit-area square region /spl Omega/, the probability G(V, r/sub n/) being k-connected is at least (e/sup -e/)/sup -/spl sigma// when n/spl pi/(r/sup 2/)/sub n/ /spl ges/ ln n + (2k - 3) ln ln n - 2 ln (k - 1)! + 2/spl sigma/ for k > 1 and n sufficiently large. This result also applies to mobile networks when the moving of wireless nodes always generates randomly and uniformly distributed positions. We also conduct extensive simulations to study the practical transmission range to achieve certain probability of k-connectivity when n is not large enough. The relation between the minimum node degree and the connectivity of graph G(V, r) is also studied.

This paper investigate fault tolerance for wireless ad hoc networks. We consider a large-scale of wireless networks whose nodes are distributed randomly in a unit-area square region. Given n wireless nodes V, each with transmission range rn, the wireless networks are often modeled by graph G(V,rn) in which two nodes are connected if their Euclidean distance is no more than rn.We first consider how the transmission range is related with the number of nodes in a fixed area such that the resulted network can sustain k fault nodes with high probability. We show that, for a unit-area square region, the probability that the network G(V,rn) is (k+1)-connected is at least e-e-α when the transmission radius rn satisfies n π rn2 ≥ ln n + (2k-1) ln ln n -2ln k! + 2α for k>0 and n sufficiently large. This result also applies to mobile networks when the moving of wireless nodes always generates randomly distributed positions. Our simulations show that n should be larger than 500 if k=2 or 3 and α = log n and n should be larger than 2500 if k=2 or 3 and α = log log n.We then present a localized method to control the network topology given a (k+1)-faults tolerant deployment G(V,rn) of wireless nodes such that the resulting topology is still (k+1)-faults tolerant but with O(kn) communication links maintained. We show that the constructed topology is also a length spanner. Here a subgraph H is spanner of graph G, if for any two nodes, the length of the shortest path connecting them in H is no more than a small constant factor of the length of the shortest path connecting them in G.Finally, we conduct some simulations to study the practical transmission range to achieve certain probability of k-connected when n is not large enough.

Nodes in wireless ad hoc networks may become inactive or unavailable due to, for example, internal breakdown or being in the sleeping state. The inactive nodes cannot take part in routing/relaying and thus may effect the connectivity. A wireless ad hoc network containing inactive nodes is then said to be connected if each inactive node is adjacent to at least one active node and all active nodes form a connected network. This paper is the first installment of our probabilistic study of the connectivity of wireless ad hoc networks containing inactive nodes. We assume that the wireless ad hoc network consists of n nodes, which are distributed independently and uniformly in a unit-area disk and are active (or available) independently with probability p for some constant 0 < p /spl les/ 1. We show that if all nodes have a maximum transmission radius r/sub n/ = /spl radic/(ln n+c//spl pi/pn) for some constant c, then the total number of isolated nodes is asymptotically Poisson with mean e/sup -c/ and the total number of isolated active nodes is also asymptotically Poisson with mean pe/sup -c/.