Spurred by the limited availability of quantum resources, known as qubits, in recent quantum computers, quantum federated learning (QFL) is drawing attention. Due to its ability to fully utilize distributed qubits, QFL is suitable for developing quantum algorithms. QFL achieves local quantum gradients using the parameter-shift rule (P-S rule) and aggregates them, effectively coping with the limited number of qubits in each quantum computer. However, realizing QFL remains challenging due to the characteristics of the P-S rule, which requires two forward passes to compute the quantum gradients in each local quantum computer. These challenges become even more severe when the aggregation of the local quantum gradients occurs under heterogeneous channel conditions and data distributions. Motivated by this, this paper proposes the joint P-S rule, which eliminates the aggregation process in QFL and instead directly achieves the global quantum gradients. Furthermore, this paper proposes joint efficient quantum federated learning (Joint EQFL) that leverages successive interference cancellation and divergence-based clustering for achieving stability under heterogeneous channel conditions and robustness to heterogeneous data distributions. This paper analyzes the convergence and corroborates the superiority of Joint EQFL.

Blockchain permeates nearly every facet of daily life, providing a crucial role in securely interweaving networked elements such as smart appliances and IoT devices. Proof-of-work (PoW) retains an undiminished status as one of the most adopted technologies in the blockchain industry for its trustworthiness and proportional fairness. Transactions will be safely committed and confirmed in a PoW-based blockchain scheme as long as a malevolent party does not control the majority of miners. However, since the discovery of a block withholding (BWH) attack where a malicious mining pool participant intentionally equivocates when finding a correct answer to the cryptographic puzzle, the proportional fairness between PoW miners has been compromised and cannot be guaranteed anymore. In this article, based on existing BWH attacks such as the BWH attack and the fork-after-withholding (FAW) attack, we introduce a novel attack scheme, a return-after-withholding (RAW) attack, which can be even more injurious to the proportional fairness of PoW mining. Analytic and experimental studies prove that our attack scheme is advantageous over the existing BWH attacks and distinguished by unique characteristics from the other BWH attacks.

Text-to-image generation is a multivariable process in which the resulting quality is determined by both the generative model and the input prompt. While previous efforts rely on a single model either by enhancing its capability or by reformulating prompts, we point out that no single model excels at handling all types of tasks, as there exist inter-model and intra-model quality variance induced by the difference in types of prompts. This paper explores the relationship between the generation quality of text-to-image models and the linguistic features of input prompts by measuring the performance of state-of-the-art models using five different prompt datasets each with its distinctive features. Motivated by our empirical observations, we propose a novel approach that assigns each prompt to its best-performing model based on quality prediction. This enables utilizing a diverse set of models each with its expertise and cost, thereby enhancing cost-effectiveness. Evaluation results show that our approach can reduce the total generation cost by 29.25% with comparable or even higher generation quality than using only the single best model.

Most Wi-Fi backscatter systems have been proposed with mechanisms that decode the data from backscatter tags based on XOR operations. These XOR-based mechanisms require two receivers listening on the Wi-Fi and backscatter channels and consider the channel coding process as an obstacle to decode the backscatter packets. We focus on channel coding, which is a technique that all Wi-Fi systems use to detect and correct errors from the wireless channels. In our backscatter system, the tag reflects ambient Wi-Fi signals at the symbol level to transmit tag data. When the receiver demodulates and decodes these reflected signals, certain patterns of errors can be observed because of the symbol and subcarrier structures according to the OFDM scheme in Wi-Fi. We propose a method for detecting bit errors caused by backscatter tags and investigate the possibility of utilizing them in decoding.

Automatic modulation classification (AMC) has been envisioned as a significant element for security issues at the physical layer due to its indispensable role in accurate communications. Recent attention to deep learning has impacted the AMC, which exhibits exceptional performance without manual feature engineering. To guarantee the accuracy and robustness of deep learning-based AMC, data augmentation is a critical issue. While existing studies have used several deep generative models to handle the data insufficiency, these studies face three challenges including low scalability, lengthy training time, and limited accuracy improvement. To this end, this paper presents UniQGAN, a novel unified generative architecture that models I/Q constellation diagrams from various signal-to-noise ratios (SNRs) using a single model. The proposed method enables the generation of high-quality data with a scalable generator, while requiring reduced training time. At the core of UniQGAN aremulti-conditions embeddingandmulti-domains classificationtechniques that leverage both SNR and modulation type during the optimization process to enable unified modeling. Using abundant high-quality training data, UniQGAN accelerates the enhanced AMC with high performance and adversarial robustness. Experimental results demonstrate that the data generation by UniQGAN achieves superiority in terms of scalability, training time, and accuracy.

This paper proposes a heterogeneous carrier-sense multiple access (CSMA) protocol named LoHEC as the first research attempt to improve energy fairness when applying CSMA to long-range wide area network (LoRaWAN). LoHEC is enabled by Channel Activity Detection (CAD), a recently introduced carrier-sensing technique to detect LoRaWAN signals even below the noise floor. The design of LoHEC is inspired by the fact that existing CAD-based CSMA proposals are in a homogeneous manner. In other words, they require LoRaWAN end devices to perform identical CAD regardless of the differences of their used network parameter – spreading factor (SF). This causes energy consumption imbalance among end devices since the consumed energy during CAD is significantly affected by SF. By considering the heterogeneity of LoRaWAN in terms of SF, LoHEC requires end devices to perform different numbers of CAD operations with different CAD intervals during channel access. Particularly, the number of needed CADs and CAD interval are determined based on the CAD energy consumption under different SFs. We conduct extensive experiments regarding LoHEC with a practical LoRaWAN testbed including 60 commercial off-the-shelf end devices. Experimental results show that in comparison with the existing solutions, LoHEC can achieve up to$0.85\times $improvement of the energy fairness on average.

HTTP’s intrinsic request-and-response traffic pattern makes most web servers often idle, leaving a potential to accelerate page loads. We present the notion of HTTP steady connections, which fully utilizes the server’s available network bandwidth during a page load using the promising HTTP/3 server push, transforming the intermittent workload of loading a page into a more steady one. To construct a proper server push policy to achieve this, we separate the structure of a page, which is a relatively static factor, from the page load environments including client and network characteristics, which are generally dynamic and unknown to servers. We formulate a deadline-based sequencing problem using a page load model with dependency graphs and design a feedback-based reprioritization mechanism within HTTP server push to reactively match client progress robustly. Experiments with a prototype and a wide range of real-world pages show that HTTP steady connections significantly improve web page loads compared with state-of-the-art accelerators, even under packet losses and without any prior knowledge of network environments.

While third-party trackers breach users’ privacy by compiling large amounts of personal data through web tracking techniques, combating these trackers is still left at the hand of each user. Although network operators may attempt a network-wide detection of trackers through inspecting all web traffic inside the network, their methods are not only privacy-intrusive but of limited accuracy as these are susceptible to domain changes or ineffective against encrypted traffic. To this end, in this paper, we propose Net-track, a novel approach to managing a secure web environment through platform-independent, encryption-agnostic detection of trackers. Utilizing only side-channel data from network traffic that are still available when encrypted, Net-track accurately detects trackers network-wide, irrespective of user’s browsers or devices without looking into packet payloads or resources fetched from the web server. This prevents user data from leaking to tracking servers in a privacy-preserving manner. By measuring statistics from traffic traces and their similarities, we show distinctions between benign traffic and tracker traffic in their traffic patterns and build Net-track based on the features that fully capture trackers’ distinctive characteristics. Evaluation results show that Net-track is able to detect trackers with 94.02% accuracy and can even discover new trackers yet unrecognized by existing filter lists. Furthermore, Net-track shows its potential for real-time detection, maintaining its performance when using only a portion of each traffic trace.

Switches in cloud data centers support multiple service queues per port to provide differentiated network performance among different traffic classes. To isolate service queues, recent solutions leverage the power of Explicit Congestion Notification (ECN). However, this causes a fundamental dependency on ECN-based transport protocols, making it hard to use generic transport protocols. To this end, we design DynaQ, a protocol-independent multi-queue management solution that enables service queue isolation with generic transport protocols. The key idea of DynaQ is to adjust the packet dropping threshold of service queues dynamically. Specifically, DynaQ allows a service queue to occupy free buffer space but prevents the queue from hurting other active queues. Our solution requires only a few additional clock cycles to implement on hardware. To evaluate DynaQ comprehensively, we conduct a series of testbed experiments and large-scale simulations. Our evaluation results show that, compared to alternative schemes, DynaQ is the only solution that achieves work-conserving weighted fair sharing and low latency without protocol dependency.

Data centers are the fundamental component in the Internet of Things (IoT) system architecture. Data center servers where IoT services are co-located require hierarchical network policy enforcement to ensure fair bandwidth sharing among tenants and to prioritize latency-sensitive traffic within a tenant simultaneously. Meanwhile, emerging network interface cards (NICs) in servers make use of multiple hardware queues to drive increasing line rates. Unfortunately, multiqueue NICs make it hard to enforce hierarchical policies because the NIC packet scheduler dequeues packets in a static round-robin (RR) fashion for per-flow fairness. In this article, we enable hierarchical network policy enforcement with existing commodity multiqueue NICs. We design TONIC, a multiqueue NIC packet scheduling solution that approximates hierarchical packet scheduling by manipulating the packet dequeueing sequence of the NIC scheduler through dynamic packet enqueueing decisions. Specifically, TONIC leverages multiple hardware queues and the double-ended queue structure of qdiscs to express different tenant weights and application priorities without hardware modifications. We implement a TONIC prototype as a Linux kernel module and evaluate it on a testbed with commodity multiqueue NICs. Our experiment results show that TONIC can enforce hierarchical policies consisting of weighted fair sharing and traffic prioritization while maintaining robustness to various network conditions.

Leaderless replication allows any replica to handle any type of request to achieve read scalability and high availability for distributed data stores. However, this entails burdensome coordination overhead of replication protocols, degrading write throughput. In addition, the data store still requires coordination for membership changes, making it hard to resolve server failures quickly. To this end, we present NetLR, a replicated data store architecture that supports high performance, fault tolerance, and linearizability simultaneously. The key idea of NetLR is moving the entire replication functions into the network by leveraging the switch as an on-path in-network replication orchestrator. Specifically, NetLR performs consistency-aware read scheduling, high-performance write coordination, and active fault adaptation in the network switch. Our in-network replication eliminates inter-replica coordination for writes and membership changes, providing high write performance and fast failure handling. NetLR can be implemented using programmable switches at a line rate with only 5.68% of additional memory usage. We implement a prototype of NetLR on an Intel Tofino switch and conduct extensive testbed experiments. Our evaluation results show that NetLR is the only solution that achieves high throughput and low latency and is robust to server failures.

A bursty traffic pattern, called the microburst, is a key hurdle to achieve low latency for user-facing applications because it causes excessive packet losses in shallow buffered switches. Explicit Congestion Notification (ECN) can absorb microbursts by reserving buffer headroom, but the existence of headroom results in a fundamental trade-off between latency and throughput. To this end, we present LossPass, a buffer sharing mechanism that absorbs microbursts as many as possible while maintaining line-rate throughput. Specifically, LossPass evicts buffered large flow packets to make free buffer space on demand for arriving small flow packets. Our solution is inexpensive to implement on hardware. We implement a LossPass prototype and evaluate its performance through extensive testbed experiments and large-scale simulations. Our evaluation results show that LossPass reduces the FCT of small flows while maintaining line-rate throughput. For example, in testbed experiments, LossPass outperforms ECN by up to$3.20\times$in the 99th percentile FCT of small flows.

If we had the performance information of every application on every SSD, it would be very beneficial to both SSD users and SSD manufacturers. For SSD users, they can buy the SSD that is fastest for the most frequently using applications; for SSD manufacturers, they can figure out the strength and weakness of their SSD for every application. Toward this end, this article proposes a framework named${\sf FORESEE}$FORESEEthat estimates accurately the execution time of a given IO trace (i.e.,query IO trace) of a given application on a target SSDwithout its actual execution.${\sf FORESEE}$is developed based on the observation thatif two IO traces are similar to each other in their IO behavior, their execution times tend to be similar when they are executed on the same SSD. In${\sf FORESEE}$, the execution time of a query IO trace is estimated by using the execution times of the IO traces in a database similar to the query IO trace. Our technical contributions in${\sf FORESEE}$are as follows: (1) we propose a goodness function that efficiently evaluates the quality of sets of features that are used to measure the similarity of IO traces; (2) we propose a DB structure and a searching method for efficiently searching for similar IO traces to a query IO trace; (3) we propose an aggregation method that aggregates the execution times of similar IO traces to a query IO trace for accurately estimating the execution time of the query IO trace; and (4) we verify the effectiveness of${\sf FORESEE}$via extensive experiments by using real-world application IO traces. According to the results, the Pearson correlation coefficient (PCC) of the actual execution time and the estimated execution time by${\sf FORESEE}$is found to be 0.87, indicating${\sf FORESEE}$estimates the execution time accurately.

The last decade has witnessed the ever-increasing deployment of Wi-Fi networks and the explosion of Bluetooth-based applications. As a result, the coexistence of Bluetooth piconets with highly-dense Wi-Fi networks is a common phenomenon currently. Unlike Wi-Fi that conducts carrier sensing before channel access, Bluetooth adopts frequency hopping based on a predefined hop sequence, which inevitably incurs considerable cross-technology interference to Wi-Fi. While the Adaptive Frequency Hopping technique is standardized for interference reduction, it does not perform well in current practice where densely-deployed Wi-Fi networks commonly cover the whole 2.4 GHz unlicensed spectrum. In this context, this article presents BuSAR, a novel approach to account for the coexistence problem between Bluetooth piconets and dense Wi-Fi networks. BuSAR embodies the first work to aim at mitigating the cross-technology interference between Bluetooth and highly-dense Wi-Fi networks in a distributed manner. At the heart of BuSAR lies a subtle technique called Bluetooth slot availability randomization, which exploits the redundancy of erroneous Bluetooth packets for better Bluetooth/Wi-Fi coexistence. With BuSAR adopted, multiple Bluetooth piconets are guaranteed to operate independently and only a lightweight algorithm is needed to be implemented at each Bluetooth device. Both theoretical analysis and experimental results validate the feasibility and superiority of BuSAR.

To isolate service queues in switch ports, recent solutions leverage the power of Explicit Congestion Notification (ECN). However, this causes a fundamental dependency on ECN-based transport protocols, making it hard to use generic transport protocols. To this end, we design DynaQ, a protocol-independent multi-queue management solution that enables service queue isolation with generic transport protocols. DynaQ dynamically adjusts the packet dropping threshold of service queues. Our solution is inexpensive to implement on hardware. Through extensive testbed experiments and large-scale simulations, we show that compared to alternative schemes, DynaQ is the only solution that achieves work-conserving weighted fair sharing and low latency without protocol dependency.

With the wide adoption of TLS, malware's use of TLS is also growing fast. However, fine-grained feature selection in existing approaches is too burdensome. To this end, we propose to visualize TLS-encrypted flow metadata as an image for better malware traffic analysis and classification. We discuss its feasibility and show some preliminary classification results with high accuracy.

In this paper, we introduce technology-independent ambient backscatter systems where a backscatter tag utilizes all single-stream ambient signals transmitted by nearby devices. Specifically, we design a phase demodulation algorithm that detects a backscatter signal from the phase difference between the two antennas, no matter which signal the tag reflects. We then develop a parallelized backscatter receiver that mitigates the dead spot problem by leveraging antenna diversity. To show the feasibility of our design, we implement a backscatter receiver on the software-defined radio platform and analyze 50 MHz RF bandwidth in real-time. Our evaluation shows that the receiver can decode backscatter bits carried by any single stream ambient signal such as a continuous wave, a QAM signal, and even a noise signal. We also demonstrate backscatter transmissions with commodity Wi-Fi and Bluetooth devices to prove that our design can be combined with existing wireless networks.

Radio-frequency identification (RFID) system, successfully adopted in many industrial applications, suffers from security issues due to the inherent weakness of wireless communication, such as eavesdropping, replay attack, impersonation attack, and traceability issues. A lot of research efforts based on cryptographic primitives have been conducted in a decade, however, most of the existing security protocols depending on cryptosystems are not feasible to be applied due to the minimalist design of passive tags. A lightweight cryptographic authentication is one of the practical solutions, but it has traceability issues from physical layer information. The other approach is to use the properties of the physical layer of RFID systems. However, since the physical-layer characteristics cannot be intentionally updated, they are vulnerable to situations where an adversary actively obtains authentic data for traceability attacks or replay attacks. Therefore, to resist the security threats, we propose Tagora, a cross-layer authentication protocol, which is the first integration work of two-layer approaches that harness the unpredictable properties of tag's collision responses at both the physical and application layers. Our protocol design is composed of a collision recovery algorithm with a random offset scheme and phase encryption in the physical layer, and authentication process based on a challenge-response mechanism in the application layer. We evaluate Tagora in terms of the untraceability and reliability, and also provide security analysis on how Tagora can defend against plausible attacks while meeting security requirements.

The prosperity of IEEE 802.11-based Wi-Fi networks aggravates cross-technology interference to IEEE 802.15.4-enabled ZigBee networks widely deployed to enable various Internet-of-Things applications. To make ZigBee communication reliable and robust even in a dense Wi-Fi environment, taming Wi-Fi interference in ZigBee networks especially from the perspective of physical layer is of paramount importance. In this context, this work takes aim to design a novel Wi-Fi interference-resilient ZigBee decoder called PolarScout, which separates collided ZigBee signal samples out of Wi-Fi interference to bootstrap ZigBee data decoding. Unlike several existing solutions which need clear signal preamble, tremendous signal strength difference between ZigBee and Wi-Fi, and Wi-Fi interference recognition in prior to ZigBee decoding, PolarScout aims at direct ZigBee decoding in a more generic and challenging case where Wi-Fi interference features a wide range of power levels and arises within a ZigBee packet at an arbitrary position. At the heart of PolarScout lies a subtle shell-shaping technique which harnesses a customized sample sequence to smooth the shell of corrupted signal samples. PolarScout then refers to the resulting shell to recover each contaminated ZigBee sample. Experimental results validate the superiority of PolarScout and its resilience to a wide range of Wi-Fi interference types.

Wi-Fi backscatter is an emerging technique that enables ultra-low power wireless communications thanks to the simplicity of a backscatter tag. This simplicity drastically reduces communication power. However, this simplicity also removes channel selectivity of the backscatter tag. In this regard, we introduce two issues, violation of the wireless regulations and the waste of resources, in Wi-Fi backscatter networks. To solve these problems, we introduce channel independent packet detection and error vector demodulation. We first design a backscatter receiver accepting Wi-Fi frames on the listening channel as well as adjacent channels, because the backscatter tag responds to all incoming signals regardless of their frequencies. We then investigate how the error vectors of each subcarrier are changed in Wi-Fi backscatter systems. Based on the analysis, we propose a method that translates the error vectors into a backscatter frame. We implement and evaluate our design with commodity 802.11n access points as carrier sources, a software-defined radio as a receiver, and a 2.4 GHz backscatter tag. The results show that channel independent Wi-Fi backscatter is always better than channel dependent approaches.

The emerging deployment of IoT devices increasingly requires more energy-and-cost-efficient wireless links between devices. Nowadays backscatter networks, one of the most feasible technology to meet the requirement in IoT spaces, have evolved for better usability and wider coverage. The most likely consequence of the evolution is Wi-Fi backscatter networks that harmonize with widely deployed commercial devices. However recent Wi-Fi backscatter techniques are stuck in front of several hurdles. The backscatter techniques along with 802.11b devices impair the spectral efficiency of wireless channels and break backward compatibility. Meanwhile, the backscatter techniques along with the other types of 802.11 devices support only per-packet backscatter resulting poor performance. To tackle all these problems, we propose a flicker detector that achieves per-symbol in-band backscatter by exploiting residual channel of Wi-Fi packets. Our approach shows robust performance without any modification on the hardware and any side effect on wireless channels. Extensive experiments on a software-defined radio testbed demonstrate that our approach overcomes the hurdles of existing Wi-Fi backscatter networks.

This paper conducts the feasibility study for discussing about the interference impacts in advanced fog computing (FC) networks with 60 GHz millimeter-wave wireless technology. With the concept of FC, cloud computing services can be utilized with local computing devices (FC devices) those are located nearby user terminals [edge devices (EDs)] for low-latency communications. Since EDs can be densely deployed in urban areas, wireless hyperconnection should be supportable in FC networks. For the system, 60 GHz millimeter-wave technology can be used as one of wireless networking methods because it can provide: 1) high rates for visual information delivery and 2) high directionality for spatial reuse in hyperconnected FC networks. Therefore, this performance simulation study under the consideration of interference impacts determines whether utilizing 60 GHz millimeter-wave wireless technology for hyperconnected FC networks is feasible or not. Under the consideration of various interference scenarios, the interference impacts are calculated. As presented in simulation-based performance evaluation results, we verify that 1.5 Gb/s high rate can be supportable even though more than 1000 EDs are deployed in the 100 m-by-100 m size small-scale networks (upper bound). Therefore, we confirm that hyperconnection can be realized with 60 GHz millimeter-wave technology for FC networks.

Recently, the concept of barrier-coverage of wireless sensor network has been introduced for various civilian and military defense applications. This paper studies the problem of how to organize hybrid sensor network, which consists of a number of energy-scarce ground sensors with homogenous initial battery level and energy-plentiful mobile sensors, to maximum the lifetime of barrier-coverage. Two key observations are (a) as the lifetime of each mobile sensor is much longer than that of the static ground sensors, each mobile sensor is capable of contributing multiple sensor barrier formations, and (b) no mobile sensor node can join two hybrid barriers which will be successively used to continuously protect the area of interest due to the moving delay. Based on these, we introduce a new maximum lifetime barrier-coverage problem in hybrid sensor network. We first propose a simple heuristic algorithm by combining existing ideas along with our own. Then, we design another efficient algorithm for the problem and prove that the lifetime of hybrid barrier constructed by this algorithm is at least three times greater than the existing one on average. Our simulation result shows that the second algorithm outperforms the first algorithm at least 33 percent and up to 100 percent.

Radio frequency identification (RFID) technology provides a promising solution to the problem of missing object identification in large-scale systems, such as warehouses and bookstores by employing RFID readers to communicate with numerous RFID tags, each of which is attached to a monitored object. To achieve prompt identification of missing tags/objects, extensive research is carried out while the transmission of expatiatory bits from each tag and the occurrence of substantial tag collisions critically degrade the time efficiency. Therefore, this motivates us to propose ProTaR, a probabilistic tag retardation-based protocol, which addresses the missing tag identification problem in a more time-efficient way than the prior work. Based on an improvement of conventional frame-slotted ALOHA algorithm, ProTaR aims at alleviating the tag collision problem and achieving compact tag transmissions. The novelty of ProTaR is manifested mainly in two aspects. ProTaR leverages a mask at a reader to distill partial bits from 96-bit identifier (ID) of each tag for the characterization of tag uniqueness. In this context, ProTaR averts the transmission of redundant bits from both the tags and reader. A bit vector is constructed by the reader to inform each tag of the transmissions of others. This idea successfully eliminates the tag collisions, and hence makes full utilization of tag responses. Experimental results validate that ProTaR achieves 100% identification accuracy regardless of missing tag ratio. Furthermore, extensive simulations present that ProTaR enables the time efficiency improvement of up to 88% compared with benchmarks while merely degrading the optimum by 15%.

This paper proposes two novel algorithms for adaptive crowdsourcing in 60-GHz medical imaging big-data platforms, namely, a max-weight scheduling algorithm for medical cloud platforms and a stochastic decision-making algorithm for distributed power-and-latency-aware dynamic buffer management in medical devices. In the first algorithm, medical cloud platforms perform a joint queue-backlog and rate-aware scheduling decisions for matching deployed access points (APs) and medical users where APs are eventually connected to medical clouds. In the second algorithm, each scheduled medical device computes the amounts of power allocation to upload its own medical data to medical big-data clouds with stochastic decision making considering joint energy-efficiency and buffer stability optimization. Through extensive simulations, the proposed algorithms are shown to achieve the desired results.

We propose employing receiver cooperation in centralized topology control to improve energy efficiency as well as network connectivity. The idea of transmitter cooperation has been widely considered in topology control to improve network connectivity or energy efficiency. However, receiver cooperation has not previously been considered in topology control. In particular, we show that we can improve both connectivity and energy efficiency if we employ receiver cooperation in addition to transmitter cooperation. Consequently, we conclude that a system based both on transmitter and receiver cooperation is generally superior to one based only on transmitter cooperation. We also show that the increase in network connectivity caused by employing transmitter cooperation in addition to receiver cooperation is at the expense of significantly increased energy consumption. Consequently, system designers may opt for receiver-only cooperation in cases for which energy efficiency is of the highest priority or when connectivity increase is no longer a serious concern.

Effectiveness of MapReduce as a big data processing framework depends on efficiencies of scale for both map and reduce phases. While most map tasks are preemptive and parallelizable, the reduce tasks typically are not easily decomposed and often become a bottleneck due to constraints of data locality and task complexity. By assuming that reduce tasks are non-parallelizable, we study offline scheduling of minimizing makespan and minimizing total completion time, respectively. Both preemptive and non-preemptive reduce tasks are considered. On makespan minimization, for preemptive version we design an algorithm and prove its optimality, for non-preemptive version we design an approximation algorithm with the worst ratio of 3/2-1/2h where h is the number of machines. On total complete time minimization, for non-preemptive version we devise an approximation algorithm with worst case ratio of 2-1/h, and for preemptive version we devise a heuristic. We confirm that our algorithms outperform state-of-art schedulers through experiments.

One type of distributed systems is the client/server system consist of clients and servers. In order to improve the performance of such a system, client assignment strategy plays an important role. There are two criteria to evaluate the load on the servers - total load and load balance. The total load increases when the load balance decreases, vice versa. It has been proved that finding the best client assignment is NP-hard. In this paper, we propose a new model for the client assignment problem and design an algorithm based on Semidefinite programming (SDP). Our method has a (relaxed) performance ratio 0.87 when only 2 servers exist. In general case, our method becomes a heuristic, and the ratio of each iteration is 0.87. We are the first one to give these bounds. Our simulation results are compared with the state-of-art client assignment method, and our strategy outperforms it in terms of running time while keeps the load in similar level.

Cloud computing enables larger classes of application service providers to distribute their services to world-wide users in multiple regions without their own private data centers. Heterogeneity and resource limitation of geo-graphically distributed cloud data centers impose application service providers to have incentives to optimize their computing resource usage while guaranteeing some level of quality of service. Recent studies proposed various techniques for optimization of computing resource usage from cloud users (or application service providers) perspective with little consideration of competition. In addition, optimization efforts of application service providers motivate cloud service providers owning multiple geo-distributed clouds to decide their computing resource prices considering their efforts. In this context, we formulate this problem for cloud service providers as a game of resource pricing in geo-distributed clouds. One of the main challenges in this problem is how to model the best responses of application service providers, given resource price information of clouds in non-overlapped regions. We propose a novel concave game to describe the quantity competition among application service providers reducing payment while guaranteeing fair service delay to end users. Furthermore, we optimize the prices of computing resources to converge to the equilibrium. In addition, we show several characteristics of the equilibrium point and discuss their implications to design computing resource markets for geo-distributed clouds.

Given a requested area, the Minimum Connected Sensor Cover problem is to find a minimum number of sensors such that their communication ranges induce a connected graph and their sensing ranges cover the requested area. Several polynomial-time approximation algorithms have been designed previously in the literature. Their best known performance ratio is O(r ln n) where r is the link radius of the sensor network and n is the number of sensors. In this paper, we will present two polynomial-time approximation algorithms. The first one is a random algorithm, with probability 1 - ε, producing an approximation solution with performance ratio O(log3n log log n), independent from r. The second one is a deterministic approximation with performance ratio O(r), independent from n.

The development of vehicular communication technology can make more intelligent transportation systems (ITSs) by enabling a large number of potential applications. In particular, infrastructure-to-vehicle (I2V) communication will support ITS applications and provide inexpensive high-rate Internet access as well. Thus, a study on I2V communications may improve the quality of experience of end users in vehicles, such as drivers and passengers. To this end, we propose a medium access control (MAC) protocol for I2V communications to improve the fairness of node throughput while maximizing the expected system throughput. We derive the way of estimating road traffic to precisely control the transmission probability of vehicles for maximizing system throughput. The estimation is performed by utilizing the spacing distribution model in transportation systems. Furthermore, we present a threshold to limit the number of transmitted packets for the fairness of the vehicles. The threshold is set based on the achievable node throughput and the estimated sojourn time. Through extensive simulations based on the empirical vehicular trajectory data, we demonstrate the improved performance of the proposed MAC protocol. The test results show that the expected system throughput is increased by more than 21.3% and that Jain's fairness index with regard to the number of transmitted packets among the nodes is close to 1.

Inspired by the backbone concept in wired networks, virtual backbone is expected to bring substantial benefits to routing in wireless sensor networks (WSNs). Virtual backbone construction based on Connected Dominating Set (CDS) is a competitive approach among the existing methods used to establish virtual backbone in WSNs. Traditionally, CDS size was the only factor considered in the CDS-based approach. The motivation was that smaller CDS leads to simplified network maintenance. However, routing cost in terms of routing path length is also an important factor for virtual backbone construction. In our research, both of these two factors are taken into account. Specifically, we attempt to devise a polynomial-time constant-approximation algorithm that leads to a CDS with bounded CDS size and guaranteed routing cost. We prove that, under general graph model, there is no polynomial-time constant-approximation algorithm unless P = NP. Under Unit Disk Graph (UDG) model, we propose an innovative polynomial-time constant-approximation algorithm, GOC-MCDS-C, that produces a CDS D whose size I D is within a constant factor from that of the minimum CDS. In addition, for each node pair u and v, there exists a routing path with all intermediate nodes in D and path length at most 7 · d(u, v), where d(u, v) is the length of the shortest path between u and v. Our theoretical analysis and simulation results show that the distributed version of the proposed algorithm, GOC-MCDS-D, outperforms the existing approaches.

ABSTRACT In wireless communications research, a number of literature assume that every node knows all of its neighbor nodes. To this end, neighbor discovery research has been conducted, but it still has room for improvement in terms of discovery delay. Furthermore, prior work has overlooked energy efficiency, which is considered as the critical factor in wireless devices or appliances. For better performance with respect to the discovery delay and energy efficiency, we proposed a novel p‐persistent‐based neighbor discovery protocol and devised a simple and light algorithm estimating the number of neighbor nodes to support the proposed protocol. Our protocol requires a lower delay and a smaller number of messages for the discovery process than the existing protocols. For extensive performance evaluation, we adopted extra comparison targets from other research areas within the same context. Copyright © 2011 John Wiley & Sons, Ltd.

When a large amount of sensors are randomly deployed into a field, how can we make a sleep/activate schedule for sensors to maximize the lifetime of target coverage in the field? This is a well-known problem, called Maximum Lifetime Coverage Problem (MLCP), which has been studied extensively in the literature. It is a long-standing open problem whether MLCP has a polynomial-time constant-approximation. The best-known approximation algorithm has performance ratio 1 + ln n where n is the number of sensors in the network, which was given by Berman et. al [1]. In their work, MLCP is reduced to Minimum Weight Sensor Coverage Problem (MWSCP) which is to find the minimum total weight of sensors to cover a given area or a given set of targets with a given set of weighted sensors. In this paper, we present a polynomial-time (4 + ∈)-approximation algorithm for MWSCP and hence we obtain a polynomial-time (4 + ξ)-approximation algorithm for MLCP, where ∈ >; 0, ξ >; 0.

The broadcast is a fundamental operation in computer and communication networks. We study broadcast in multiradio multichannel multi-hop wireless networks. Suppose through configuration, each node is already assigned with a transmission power level and a set of radio channels for receiving and forwarding data. Our problem is to select a forward scheme for broadcasting from a given source node and to minimize total energy consumption. This is a known NP-hard minimization problem. In this paper, we construct a polynomial-time (1.35 + ϵ)(1+ln(n-1))-approximation algorithm where n is the number of nodes in given network and ϵ is any positive constant. We also show that there is no polynomial-time (ρ ln n)-approximation for 0O(log log n)).

Topology control is to determine the transmission power of each node so as to maintain network connectivity and consume the minimum transmission power. Cooperative Communication (CC) is a new technology that allows multiple nodes to simultaneously transmit the same data. It can save transmission power and extend transmission coverage. However, prior research work on topology control considers CC only in the aspect of energy saving, not that of coverage extension. We observe that CC can bridge (link) disconnected networks and therefore identify the challenges in the development of a centralized topology control scheme, named shape Cooperative Bridges, which reduces transmission power of nodes as well as increases network connectivity. We propose three algorithms that select energy efficient neighbor nodes, which assist a source node to communicate with a destination node: an optimal method and two greedy heuristics. In addition, we consider a distributed version of the proposed topology control scheme. Our findings are substantiated by an extensive simulation study, through which we show that the shape Cooperative Bridges scheme substantially increases the connectivity with tolerable increase of transmission power compared to other existing topology control schemes, which means that it outperforms in terms of a connectivity-to-power ratio.

Directional antennas can divide the transmission range into several sectors. Thus, through switching off sectors in unnecessary directions in wireless networks, we can save bandwidth and energy consumption. In this paper, we will study a directional virtual backbone (VB) in the network where directional antennas are used. When constructing a VB, we will take routing and broadcasting into account since they are two common operations in wireless networks. Hence, we will study a VB with guaranteed routing costs, named α Minimum rOuting Cost Directional VB (α-MOC-DVB). Besides the properties of regular VBs, α-MOC-DVB also has a special constraint - for any pair of nodes, there exists at least one path all intermediate directions on which must belong to α-MOC-DVB and the number of intermediate directions on the path is smaller than α times that on the shortest path. We prove that construction of a minimum α-MOC-DVB is an NP-hard problem in a general directed graph. A heuristic algorithm is proposed and theoretical analysis is also discussed in the paper. Extensive simulations demonstrate that our α-MOC-DVB is much more efficient in the sense of VB size and routing costs compared to other VBs.

It is well-known that the application of directional antennas can help conserve bandwidth and energy consumption in wireless networks. Thus, to achieve efficiency in wireless networks, we study a special virtual backbone (VB) using directional antennas, requiring that from one node to any other node in the network, there exists at least one directional shortest path all of whose intermediate directions should belong to the VB, named as Minimum rOuting Cost Directional VB (MOC-DVB). In addition, VB has been well studied in Unit Disk Graph (UDG). However, radio wave based communications in wireless networks may be interrupted by obstacles (e.g., buildings and mountains). Thus, in this paper, we model a network as a general directed graph. We prove that construction of a minimum MOC-DVB is an NP-hard problem in a general directed graph and in term of the size of MOC-DVB, there exists an unreachable lower bound of the polynomial-time selected MOC-DVB. Therefore, we propose a distributed approximation algorithm for constructing MOC-DVB with approximation ratio of 1 + ln K + 2ln δD, where K is the number of antennas on each node and δDis the maximum direction degree in the network. Extensive simulations demonstrate that our constructed MOC-DVB is much more efficient in the sense of MOC-DVB size and routing cost compared to other VBs.

In wireless sensor networks, virtual backbone construction based on connected dominating set is a competitive issue for routing efficiency and topology control. Assume that a sensor networks is defined as a connected unit disk graph (UDG). The problem is to find a minimum connected dominating set of given UDG with minimum routing cost for each node pair. We present a constant approximation scheme which produces a connected dominating set D, whose size |D| is within a factor α from that of the minimum connected dominating set and each node pair exists a routing path with all intermediate nodes in D and with length at most 5 · d(u,v), where d(u,v) is the length of shortest path of this node pair. A distributed algorithm is also provided with analogical performance. Extensive simulation shows that our distributed algorithm achieves significantly than the latest solution in research direction.

In this paper, we propose a new multiple-sink positioning problem in wireless sensor networks to best support real-time applications. We formally define this problem as thek-Sink Placement Problem (k-SPP) and prove that it is APX-complete. We show that an existing approximation algorithm for the well-knownk-center problem is a constant factor approximation ofk-SPP. Furthermore, we introduce a new greedy algorithm fork-SPP and prove its approximation ratio is very near to the best achievable, 2. Via simulations, we show our algorithm outperforms its competitor on average.

Topology control is one vital factor to a wireless network's efficiency. A Connected Dominating Set (CDS) can be a useful basis of a backbone topology construction. In this paper, a special CDS, named \alpha Minimum rOuting Cost CDS (\alpha-MOC-CDS), will be studied to improve the performance of CDS based broadcasting and routing. In this paper, we prove that construction of a minimum \alpha-MOC-CDS is NP-hard in a general graph and we propose a heuristic algorithm for construction of \alpha-MOC-CDS.

A cognitive radio (CR) is very significant technology to use a spectrum dynamically in wireless communication networks. However, very little has been done on using the spectrum usage patterns to handle with the problem of spectrum allocation in dynamic spectrum access. We suggest a scheme by exploiting spectrum usage patterns for the efficient spectrum management and reduce the communication cost in cognitive radio networks (CRNs). We propose the following three factors into account: spectrum sensing scheme with a sleep mode, spectrum decision scheme with a probability of spectrum access and spectrum handoff scheme with back-off time. All factors make use of spectrum usage patterns based on the statistical information. The first factor reduces the number of spectrum sensing. The second increases the opportunity of spectrum access and the last decreases the number of spectrum handoff. First of all, our proposed spectrum management scheme considers the analysis of the spectrum usage patterns and various factors obtained from the analysis is applied to lessen the communication cost in CRNs. The simulation results show that our proposed scheme improve the efficiency of spectrum management in dynamic spectrum access.

Network mobility (NEMO) basic support protocol enables seamless mobility in vehicular networks. In this paper, we analyze the session handoff probability in NEMO-based vehicular environments. We develop analytical models for the session handoff probability in two vehicular scenarios: 1) onboard time is deterministic (as in a subway) and 2) on-board time is variable due to traffic condition (as in a car). Numerical results are given to illustrate the effects of on-board time, cell residence time, and session duration.

In the future, most mobile nodes will have multiple radio interfaces, and this feature can be exploited to reduce the transmission cost in wireless data access applications. In this work, we propose cooperative wireless data access algorithms with strong consistency in multi-radio wireless networks. It can be shown that cooperation with neighbor nodes can reduce the expensive transmission cost over wireless links.

Resource management in vehicular WiFi networks is an interesting and challenging issue. In this paper, we propose a mobility-aware call admission control (MA-CAC) algorithm where different admission control policies are employed depending on the mobility. Specifically, when a vehicle is static, a handoff priority scheme with guard channels is examined to protect vehicular handoff users. On the other hand, for a moving vehicle, no guard channels for handoff users are allocated for maximizing channel utilization since there are no vehicular handoff users. By means of Markov chains, we evaluate the MA-CAC algorithm in terms of new call blocking probability, handoff call dropping probability, and channel utilization. Numerical results demonstrate that the MA-CAC algorithm can lower the handoff call dropping probability while maintaining high channel utilization.

In this paper, we will study a special Connected Dominating Set (CDS) problem - between any two nodes in a network, there exists at least one shortest path, all of whose intermediate nodes should be included in a special CDS, named Minimum rOuting Cost CDS (MOC-CDS). Therefore, routing by MOC-CDS can guarantee that each routing path between any pair of nodes is also the shortest path in the network. Thus, energy consumption and delivery delay can be reduced greatly. CDS has been studied extensively in Unit Disk Graph (UDG) or Disk Graph (DG). However, nodes in networks may have different transmission ranges and some communications may be obstructed by obstacles. Therefore, we model network as a bidirectional general graph in this paper. We prove that constructing a minimum MOC-CDS in general graph is NPhard. We also prove that there does not exist a polynomial-time approximation algorithm for constructing a minimum MOCCDS with performance ratio plnδ, where p is an arbitrary positive number (p <; 1) and δ is the maximum node degree in network. We propose a distributed heuristic algorithm (called as FlagContest) for constructing MOC-CDS with performance ratio (1 - ln2) + 2lnδ. Through extensive simulations, we show that the results of FlagContest is within the upper bound proved in this paper. Simulations also demonstrate that the average length of routing paths through MOC-CDS reduces greatly compared to regular CDSs.

Cooperative Communication (CC) is a technology that allows multiple nodes to simultaneously transmit the same data. It can save power and extend transmission coverage. However, prior research work on topology control considers CC only in the aspect of energy saving, not that of coverage extension. We identify the challenges in the development of a centralized topology control scheme, named Cooperative Bridges, which reduces transmission power of nodes as well as increases network connectivity. We observe that CC can bridge (link) disconnected networks. We propose two algorithms that select the most energy efficient neighbor nodes, which assist a source to communicate with a destination node; an optimal method and a greedy heuristic. In addition we consider a distributed version of the proposed topology control scheme. Our findings are substantiated by an extensive simulation study, through which we show that the Cooperative Bridges scheme substantially increases the connectivity while consuming a similar amount of transmission power compared to other existing topology control schemes.

It is usually possible to associate with more than one Access Point (AP) in IEEE 802.11 Wireless LANs. AP selection is a crucial issue because the performance achieved by a user heavily depends on the AP selected. A received signal strength (RSS)-based association mechanism is specified by the IEEE 802.11 standard. However, this does not consider the channel conditions and AP load, which leads to a low throughput and a low user transmission rate. An alternative to using the RSS is to exploit the airtime metric, which provides users with information on how busy the channel is, but the results of our simulations show that the airtime metric cannot indicate the exact status of the channel. In this paper, we present a new association framework using channel occupancy in order to provide users with exact channel status information of APs. Via the proposed scheme, users can compare the achievable throughput provided by each AP and select the best AP. We validate our proposed association method via simulation results, which show that the throughput improvement of the method is worthy of notice.

A signal space diversity (SSD) scheme is one of techniques to achieve diversity gain in fading channels. This method consists of two key operations: constellation rotation and component-wise interleaving. Because of these operations, the decision boundaries for the SSD are no longer perpendicular, and thus, different coordination approaches are required for the analysis of error rates compared to conventional rectangular coordinates. In this letter, we derive an exact expression of the symbol error rate for the SSD scheme in Rician fading channels with M-QAM and M-PSK. By defining the ratio of the standard deviation of the inphase and quadrature components, we introduce a new signal model for the SSD. Based on this signal model, we can compute the exact symbol error rate using polar coordinates. The computer simulation results confirm the accuracy of our analysis for fading channels.

Recently, the IETF NETLMM working group is standardizing a network-based localized mobility management (NETLMM) protocol called proxy mobile IPv6 (PMIPv6), yet the research on NETLMM is still in its early stage while it has attracted a fair amount of critical attention both in the telecommunication and the Internet communities. Unlike previous host-based mobility management protocols such as mobile IPv6 (MIPv6), hierarchical mobile IPv6 (HMIPv6), and fast handover for mobile IPv6 (FMIPv6), PMIPv6 has salient features and is expected to expedite the real deployment of IP mobility support protocol by using only collaborative operations between the network entities without mobile node (MN) being involved. In this paper, we analyze and compare the handover latency of PMIPv6 with those of the various existing host-based IP mobility management protocols. In addition, we show good efficacy of the desirable features and key strengths of PMIPv6. Numerical results demonstrate that (1) the handover latency of PMIPv6 is much lower than those of MlPv6 and HMIPv6, and (2) the handover latency of PMIPv6 becomes lower than that of FMIPv6 in case the wireless link delay is greater than the delay between mobile access gateway (MAG) and local mobility anchor (LMA).

Mobile RFID, the technology of a cellular phone equipped with a RFID reader, allows users to read RFID tags anywhere. However, signals from more than two readers can interfere with one another, i.e., reader collision problem; reliable tag reading is necessary. This paper proposes Gentle protocol to use beacon messages and multi-channel for increasing throughput. In addition, Gentle protocol can put tag ID information into the beacon message and share it among close readers. Simulation results show that Gentle protocol outperforms existing reader anti-collision protocols.

In wireless sensor networks and wireless ad-hoc networks, localization systems have used diverse signal metrics such as Received Signal Strength Indicator (RSSI) and Time Difference of Arrival (TDoA) for accurate assignment of a node position. We propose a novel scheme that applies two signal metrics, which are TDoA and RSSI exclusively, into time- based positioning scheme (TPS). For energy-efficient coverage extension, the proposed scheme uses range check technique that reduces the communication energy consumption of nodes. With two location information of neighbor nodes, the node can calculate two candidate positions through bilateration. Without an additional beacon message reception, range check is applied to find the unique position between two candidate positions. Range check also can be carried out collaboratively in general environment with the information of two-hop neighbor nodes. At the performance evaluation, we analyze and test the reduced communication cost of nodes in the extended area. Also, it is shown that the ratio of unique position assignment is increased in the general environment by range check technique.

This paper describes a dynamic service differentiation scheme based on access category (AC)'s traffic flow for QoS provisioning in the IEEE 802.11 wireless local area network (WLAN). The proposed scheme adjusts contention window sizes by considering the contributions of each traffic instead of each node on the network contention rate. There have been research efforts to improve IEEE 802.11 EDCF. However, these approaches have some limitations in that they do not consider that how much each AC traffic affects the packet collision rate. We propose a novel scheme based on traffic flow named T-EDCF. The difference between T-EDCF and existing schemes is that the former considers traffic categories' effects on the throughput, jitter, and delay of a node. When there are a lot of flow and nodes in WLAN, T- EDCF outperforms other schemes proposed for enhancing the IEEE 802. lie.

Localization is one of the critical issues on wireless sensor networks. Localization schemes are classified into range-based and range-free according to the method of whether to use range information. In this paper, we propose a novel range-based localization scheme which involves a movement strategy of mobile beacon, called mobile beacon-assisted localization (MBAL). Contrary to many research activities which have been carried out to design localization schemes using mobile beacons only based on random movement method, we consider totally a new scheme providing movement path selection with a low computational complexity. A new range check technique is also adopted into the MBAL as a useful solution to the position-ambiguity problem of bilateration in order to improve the performance of the proposed localization scheme. Simulation results verify that the MBAL impressively achieves energy efficiency because of its mobile beacon based approach using the proposed movement strategy and range check technique.

Tag identification is an important tool in RFID systems with applications for monitoring and tracking. A RFID reader recognizes tags through communication over a shared wireless channel. When multiple tags transmit their IDs simultaneously, the tag-to-reader signals collide and this collision disturbs a reader's identification process. Therefore, tag collision arbitration for passive tags is a significant issue for fast identification. This paper presents two adaptive tag anticollision protocols: an adaptive query splitting protocol (AQS), which is an improvement on the query tree protocol, and an adaptive binary splitting protocol (ABS), which is based on the binary tree protocol and is a de facto standard for RFID anticollision protocols. To reduce collisions and identify tags efficiently, adaptive tag anticollision protocols use information obtained from the last process of tag identification. Our performance evaluation shows that AQS and ABS outperform other tree-based tag anticollision protocols

In ad hoc networks with Internet connectivity, an Internet gateway (IG) is used to connect ad hoc mobile nodes to the Internet. Multiple Internet gateways may be deployed in order to provide more scalable and robust ubiquitous coverage. In this case, we need to solve the Internet gateway selection problem in order for successful integration of the Internet with mobile ad hoc networks. An ad hoc mobile node first discovers available Internet gateways, and then the node selects a serving gateway among those candidates for optimal performance. In this paper, we propose an adaptive Internet gateway selection scheme using redirecting selection method which is based on QoS attributes such as hop-count and residual capacity. Our objective is to design a selection method for providing enhanced performance. Simulation results show that our adaptive Internet gateway selection scheme achieves better performance as well as better load balancing than existing selection schemes.

Historical films usually have defects. We study the type of defects, and propose a series of solutions to detect defects before they are repaired by our inpainting algorithms. This paper focuses on a difficult issue to locate long vertical line defects in aged films. A progressive detection algorithm is proposed. We are able to detect more than 86% (recall rate) of effective line defects. These line defects are then removed step by step. The experiments use real historical video collected from national museum and public channel, instead of using computer generated noise. The results are visually pleasant based on our subjective evaluation by volunteers

Recent interesting issues in video inpainting are defect removal and object removal. We take one more step to replace the removed objects in a video sequence by implanting objects from another video. Before implant, we improve an exemplar-based image inpainting algorithm by using a new patch matching strategy which incorporates edge properties. The data term used in a priority computation of candidate patches is also redefined. We take varieties of temporal continuations of foreground and background into consideration. A motion compensated inpainting procedure is then proposed. The inpainted video backgrounds are visually pleasant with smooth transitions. A simple tracking algorithm is then used to produce a foreground video, which is implanted into the inpainted background video. Our results are available at http://www.mine.tku.edu.tw/inpainting.

Tag identification is an important tool in RFID systems with applications for monitoring and tracking. A RFID reader recognizes tags through communication over a shared wireless channel. When multiple tags simultaneously transmit their IDs to a reader, the tag signals collide and this collision disturbs the reader’s identification process. Therefore, tag collision arbitration for passive RFID tags is a significant issue for fast identification. This paper presents two adaptive tag anti-collision protocols, an Adaptive Query Splitting protocol (AQS), which is an improvement on the query tree protocol and an Adaptive Binary Splitting protocol (ABS), which is based on the binary tree protocol, which is a de facto standard for RFID anti-collision protocols. To reduce collisions and identify tags efficiently, adaptive splitting protocols use information obtained from the last process of tag identification. Our performance evaluation shows that AQS and ABS outperform other tree based tag anti-collision protocols.

This paper proposes an energy-aware distributed topology control (EDTC) algorithm for coverage-time optimization unique to clustering-based heterogeneous sensor networks. The coverage-time is defined as the time until one of cluster heads (CHs) runs out of energy. CHs which are operated by EDTC move virtual picket nodes, indicators that determine the boundaries of cluster regions, for the load-balanced regulation of cluster regions in a distributed manner. Regulation of cluster regions leads the load-balanced energy consumption of CH which is in the region for coverage-time maximization. Through a performance evaluation of EDTC, we show that our algorithm for clustering-based heterogeneous sensor networks achieves desired properties.

A radio frequency identification (RFID) reader recognizes objects through wireless communications with RFID tags. Tag collision arbitration for passive tags is a significant issue for fast tag identification due to communication over a shared wireless channel. This paper presents an adaptive memoryless protocol, which is an improvement on the query tree protocol. Memoryless means that tags need not have additional memory except ID for identification. To reduce collisions and identify tags promptly, we use information obtained from the last process of tag identification at a reader. Our performance evaluation shows that the adaptive memoryless protocol causes fewer collisions and takes shorter delay for recognizing all tags while preserving lower communication overhead than other tree based tag anticollision protocols

Efficient transmission methods for fading radio channels often require an iterative decoder. This is for example the case for systems using turbo codes. Receiver decoder iterations could potentially lead to a latency problem which impacts the performance of the medium access control protocol. In this paper, we present modifications based on the carrier sense multiple access with collision avoidance (CSMA/CA) medium access control (MAC) protocol to accommodate the increased latency in the iterative processing. One area of applications is wireless local area networks (WLANs) with high data rate. The simulation results performed in the IEEE 802.11a WLAN environment by replacing the 802:11a's convolutional coding with turbo coding demonstrate that the proposed algorithm provides a throughput gain over the conventional method.

In the RFID system, a reader recognizes tags through communication over a shared wireless channel. When more than one tag transmits their IDs at the same time, the tag-to-reader signals lead to collide and collision disturbs the reader's identification process. Therefore, tag collision arbitration for passive RFTD tags is significant for fast identification. This paper presents an adaptive binary splitting (ABS) protocol which is an improvement on the binary tree protocol. To reduce collisions and identify tags efficiently, ABS use information which is obtained from the last processes of tag identification. Our performance evaluation shows that ABS outperforms existing tree based tag anti-collision protocols.

This paper proposes an adaptive and dynamic localized scheme unique to hierarchical clustering in RFID networks, while reducing the overlapping areas of clusters and consequently reducing collisions among RFID readers. Drew on our LLC scheme that adjusts cluster coverage to minimize energy consumption, low-energy localized clustering for RFID networks (LLCR) addresses RFID reader anti-collision problem in this paper. LLCR is a RFID reader anti-collision algorithm that minimizes collisions by minimizing overlapping areas of clusters that each RFID reader covers. LLCR takes into account each RFID reader's energy state as well as RFID reader collisions. For the energy state factor, we distinguish homogeneous RFID networks from heterogeneous ones according to computing power of each RFID reader. Therefore, we have designed efficient homo-LLCR and hetero-LLCR schemes for each case. Our simulation-based performance evaluation shows that LLCR minimizes energy consumption and overlapping areas of clusters of RFID readers.

One of the major issues raised by digital rights management (DRM) systems concerns the protection of the user's privacy and anonymous consumption of content. However, most existing DRM systems do not support the protection of each user's personal information. This paper suggests a privacy-enhancing license management protocol, named PrecePt (privacy-enhancing license management protocol), which is a more powerful protocol to protect personal information in DRM. To protect the exposure of user identifier, this protocol uses temporary ID and token to guarantee anonymity. The proposed scheme also uses a session key form ECDH cryptography and public-key so that it can protect the revelation of personal information and user privacy.

In this paper, we propose an efficient micropayment protocol by improving PayWord, which is one of the representative micropayment protocols. In the original PayWord system, it was designed for a customer who generates paywords by performing hash chain operation for payments to an only designated vendor. In other words, the customer has to create new paywords in order to establish commercial transactions with different vendors on the Internet. To supplement this drawback, our proposed scheme provides a useful method to do business with multiple vendors for a customer with only one hash chain operation. In our proposed protocol, a broker creates a new series of hash chain values along with a certificate for the certificate request of a customer. This certificate is signed by the broker to give authority enabling the customer to make paywords. Our proposed scheme provides an efficient means for the customer to do business with multiple vendors.

The last decade has seen an explosive growth in multimedia applications and considerable research in related technologies, with special emphasis on Quality of Service (QoS) requirements, such as timeliness, precision, and accuracy [12]. Meeting QoS guarantees in a distributed real-time multimedia systems is an end-to-end issue because the users are interested in the end results � i.e., from application to application. Allocating proper resources to the applications with respect to QoS pro visioning to maximize the total system utilization or bene t, is a fundamental probleminallmultimedia systems today. The term utility or bene t may take on the meaning of usefulness, satisfaction, or of pleasure, depending on the context.

In this paper we present a novel admission control algorithm that exploits the degradability property of continuous media applications to improve the performance of the system. The algorithm is based on setting aside a portion of the resources as reserves and managing it intelligently so that the total utility of the system is enhanced. This reserve-based admission control strategy (RAC) is a compromise between purely greedy and non-greedy strategy, and it leads to an efficient protocol that improves the performance of the system. While the protocol is simple for admission decision, it also results in better performance for the system by reserving some resources for important future applications.

Soft-real time applications, such as continuous media (CM) systems, have an important property, namely, they allow for graceful adaptation of the application Quality-of-Service (QoS), and therefore are able to have acceptable performance with reduced resource utilization. This can be used by the admission control process to decide if an application can be admitted, even if the resource is congested. In this paper, we present a Soft-QoS framework for Continuous Media servers, which provides a dynamic and adaptive admission control and scheduling algorithm. Using our policy, we could increase the number of simultaneously running clients that could be supported and could ensure a good response ratio and better resource utilization under heavy traffic requirements. The observations and findings from the model are validated with simulation studies.

Describes the design, implementation and evaluation of CORBA- and socket-based continuous media (CM) systems. TCP/IP is not suitable for distributed applications which require high network bandwidth and timing criticality. UDP/IP is one of the alternatives. However, due to the fact that UDP is a lossy protocol, many issues arise when implementing distributed CM applications. Most of the QoS (quality of service) metrics known so far assume that the communication channel is lossless. In this paper, since we use UDP for CM data transmission, we adopt a new QoS metric that is applicable to lossy streams to evaluate the performance of our CM server. To reduce QoS loss factors and drift factors, we adopt a new strategy, called the QoS-driven dropping mechanism, for the CM server. Besides the traditional C-socket (TCP-UDP/IP) based CM server mechanisms, we implemented our CM server on CORBA. It turns out that the CORBA-based implementation runs considerably slower than the UDP-version, but faster than the TCP version.

Article Experimental evaluation of PFS continuous media file system Share on Authors: Wonjun Lee Department of Computer Science, University of Minnesota, Minneapolis, MN Department of Computer Science, University of Minnesota, Minneapolis, MNView Profile , Difu Su Department of Computer Science, University of Minnesota, Minneapolis, MN Department of Computer Science, University of Minnesota, Minneapolis, MNView Profile , Duminda Wijesekera Department of Computer Science, University of Minnesota, Minneapolis, MN Department of Computer Science, University of Minnesota, Minneapolis, MNView Profile , Jaideep Srivastava Department of Computer Science, University of Minnesota, Minneapolis, MN Department of Computer Science, University of Minnesota, Minneapolis, MNView Profile , Deepak Kenchammana-Hosekote IBM Almaden Research Center, San Hose CA IBM Almaden Research Center, San Hose CAView Profile , Mark Foresti Rome Laboratory, Griffs Air Force Base, Rome NY Rome Laboratory, Griffs Air Force Base, Rome NYView Profile Authors Info & Claims CIKM '97: Proceedings of the sixth international conference on Information and knowledge managementJanuary 1997 Pages 246–253https://doi.org/10.1145/266714.266905Published:01 January 1997 8citation342DownloadsMetricsTotal Citations8Total Downloads342Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper provides details and implementation experiences of a multimedia programming language and associated toolkits. The language, a data-flow paradigm for multimedia streams, consists of blocks of code that can be connected through their data ports. Continuous media flows through these ports into and out of blocks. The blocks are responsible for the processing of continuous media data. Examples of such processing include capturing, displaying, storing, retrieving and analyzing their contents. The blocks also have parameter ports that specify other pertinent parameters, such as location, and display characteristics such as geometry, etc. The connection topology of blocks is specified using a graphical editor called the Program Development Tool (PDT) and the geometric parameters are specified by using another graphical editor called the User Interface Development Tool (UIDT). Experience with modeling multimedia presentations in our environment and the enhancements provided by the two graphical editors are discussed in detail.