Existing crowdsourced indoor positioning systems (CIPSs) usually require prior knowledge about the site and a tedious calibration process. Moreover, they may require a large number of landmarks while ignoring the topology information that may be contained in the crowdsourced data. In this paper, we present Leto, a system that useslearnedtopology information from combined user traces to construct a radio map. Leto relies on crowdsourced WiFi and accelerometer signals only without requiring any prior knowledge about the site. Our key idea is that learned topology information can reduce the required number of landmarks, while available landmarks can transform the topology into a map. We propose a novel framework that efficiently learns the map topology by a hybrid multidimensional scaling (HMDS) algorithm and accurately rectifies the map using only a few anchors by an adaptive force-directed (AFD) algorithm. We also provide a theoretical convergence analysis of the HMDS algorithm. Experimental results on real-world datasets show that Leto can capture useful topology information and achieve significant improvements in radio map construction compared to existing systems.

In many survey-free Wi-Fi indoor localization systems, including the Adaptive indoor Wi-Fi Positioning System (AWPS) we proposed earlier, there is a need to associate unlabeled measurements to a floor plan. In this paper, we address the problem of how to associate a topological radio graph generated by crowd-sourced RSS measurements to an isomorphic Euclidean graph representing the physical space which may come from a geographic information system (GIS) or through automatic image analysis of a paper floor plan. We introduce the concept of Minimum Symmetric Structures (MSS) and Co-rooted Congruent Structures (COCS) as new ways of characterizing automorphism which prevent unambiguous association, and present a structure analysis algorithm for detecting these structures. Then, we derive rules on the number and locations of markers, or RSS measurements with location labels, needed for resolving the automorphism. Applying the analysis proposed in this paper to hypothetical floor plans as well as floor plans used in AWPS and other existing systems, we will demonstrate that often very few location labels are needed in a SLAM system.

Peer-to-peer (P2P) systems are imposing a heavy burden on internet services providers (ISPs). P2P caching is an effective way of easing this burden. We focus on the cache deployment problem as it has a significant impact on the effectiveness of caching. An ISP backbone network is usually abstracted to a graph comprising nodes representing core routers and links connecting adjacent core routers. While deploying P2P caches at nodes (NCD, node-based cache deployment) can reduce the amount of P2P traffic transmitted from access networks to the ISP backbone network, deploying P2P caches on links (LCD, link-based cache deployment) can directly reduce the amount of P2P traffic on the ISP backbone network. However, neither NCD nor LCD maximizes the performance of P2P caches. In this paper, we propose a node-link-based cache deployment method (NLCD), which optimally selects nodes or links as deployment locations during the cache deployment process. First, we propose an analysis model and define an optimal cache deployment problem for NLCD. Then, we prove that this problem is NP complete and develop a corresponding deployment algorithm. Experimental results show that the average link utilization of NLCD is 5–15% lower than that of LCD, and 7–30% lower than that of NCD.

P2P live streaming systems have been widely adopted nowadays. In such systems, flash crowds still remains a big challenge, which often occur when an enormous number of users suddenly arrive to view a newly released program. In a flash crowd scenario, users often suffer from a long startup delay and a high failure rate. In this paper, we propose a topology-construction-based algorithm to alleviate the flash crowd. Specifically, first the tracker server constructs a multiple tree topology with total new peers. Then according to the topology, all new peers join the current P2P system in form of multiple trees. When constructing the topology, the tracker server puts new peers with higher bandwidth and longer waiting time more closer to the root in each tree, in order to reduce the average waiting time of new peers. Moreover, a new analytical model is also devised to evaluate our algorithm. Model analysis and simulation indicate that our method can enhance the joining process of new peers and improve their startup delay and failure rate.

Real-time group communication is fundamental to many emerging interactive multimedia applications. Communication among the group members is N-to-N in that any number of group members may generate data and control packets destined to all the other members at the same time. Redundancy Reduction Gossip (RRG) is a highly effective real-time N-to-N dynamic group protocol over the Internet and demonstrates churn and sporadic traffic coping capability. In this paper, a peer-to-peer (P2P) real-time group communication protocol based on RRG is proposed for Content-Centric Network (CCN). A highly effective synergy between RRG and the capability of CCN is exploited. Effects include connectivity expansion, traffic reduction and latency improvement. The proposed protocol allows information distributed from an arbitrary number of dynamic sources in a group. It has low latency and minimal membership maintenance.

Peer-to-Peer (P2P) live streaming systems are becoming popular and are imposing a heavy burden on Internet Services Providers (ISPs). Proxy caching has been shown to be an effective means of reducing operation costs for ISPs. Although many caching algorithms for conventional web applications and P2P file sharing systems have been proposed and deployed, there have been few works on the caching for P2P live streaming. Data requests in P2P live streaming have distinct characteristics; for example, they are concentrated in a limited window which progresses rapidly with time in a monotonic mode. In this paper, we propose a novel caching algorithm for P2P live streaming called Lazy Caching (LC), which is designed based on the characteristics of P2P live streaming. In LC, data requests that encounter cache misses are stored in a Request Buffer (RB) that is processed periodically. LC can better utilize the cache space than traditional caching algorithms at the cost of introducing a response latency which is at most one RB processing period. Experimental results show that the hit ratio of LC, at a processing period of 0.5 second, can be as much as 20 percent higher than that of SLW, and 9 percent higher than that of OPT. We believe that it is worthwhile to achieve this higher hit ratio at the cost of a small response latency increase.

For indoor location estimation based on wireless local area networks fingerprinting, how to reduce the offline calibration effort while maintaining high location estimation accuracy is of major concern. In this paper, a hybrid generative/discriminative semi-supervised learning algorithm is proposed that utilizes a large number of unlabeled samples to supplement a small number of labeled samples. This hybrid method allows us to combine the modeling power and flexibility of generative models with the superior performance of discriminative approaches. Other related issues, such as learning efficiency enhancement and distribution estimation smoothing, are also discussed. Extensive experimental results show that our proposed method can effectively reduce the calibration effort and exhibit superior performance in terms of localization accuracy and robustness.

Location and tracking of healthy or infirm elders is a potentially useful application as society aging is accelerating worldwide and as technologies such as cellular positioning and Assisted Global Positioning System (AGPS) are maturing. For a wearable device to be used in such an application, the battery operating hour is often a key consideration. This paper describes an energy-efficient cellular and AGPS tracking algorithm based on the concept of Personal Common Location (PCL) that we define as the locations at which an elder spends most of his/her time, as recognized from historic cell ID record. During the tracking process, AGPS fixes are avoided if the elderly carrier is determined to be located within a PCL, if the destination PCL can be predicted, or if AGPS signals are likely to be unavailable. This paper also describes our approach for off-line PCL recognition, the necessity of cell ID clustering, as well as the results from our tracking experiments.

Peer-to-Peer (P2P) systems are generating a large portion of the total Internet traffic and imposing a heavy burden on Internet Services Providers (ISPs). Proxy caching for P2P traffic is an effective means of reducing network usage, thereby reducing operation costs for ISPs. Proxy cache storage design has a significant impact on ISPs. While there are several works on how to optimally design cache locations and capacity allocation to each location given a total capacity, few works tell ISPs what is the optimal total P2P cache storage capacity. In this paper, we propose an analysis method to the problem of optimally determining P2P cache size. An analysis methodology is proposed to determine the optimal cache size by considering the monetary costs of cache storage and bandwidth. Guided by our model, a close-form expression is developed to guide an ISP in the cache capacity design. Numerical evaluation results show that ISPs can achieve significant cost saving by deploying P2P cache and by allocating the cache capacity optimally.

In the use of a wearable GPS and cellular tracker for applications such as elderly tracking, device power consumption is an important consideration. To save power, assisted GPS (AGPS) location fixes should not be performed frequently. On the other hand, we also do not want to lose important information about the user's mobility patterns and routines. To solve this dilemma, in this paper, we present the design of a system that intelligently schedules on-line AGPS location fixes only when necessary based on information extracted from user's historical mobility data, and then reconstruct the user path based on these sparsely taken on-line location fixes. Experimental results show that our on-line algorithm can significantly reduce the number of AGPS fixes needed and the reconstruction method works well without a priori knowledge of a map and streets information.

This paper explores the use of terrestrial time of arrival (TOA) measurements to improve the initial Global Positioning System (GPS) location fix accuracy. First, we present a geometric approach when a GPS location fix and one TOA measurement are available. Then, a more general hybrid GPS/TOA method via the Weighted Least Square Estimator (WLSE) is proposed. To simplify the calculation, a closed-form solution based on the two-step Least Square approach is also designed. The Cramer-Rao Lower Bound (CRLB) is derived as a performance benchmark. Simulation results exhibit excellent performance of the proposed methods which attain the CRLB in different scenarios. The proposed methods work even if only one TOA measurement (in addition to a GPS location fix) is available and the corresponding accuracy improvement (compared with the initial GPS location fix) can be as much as 30%.

For Wireless Sensor Networks (WSNs), utilizing the same set of measurement data for joint localization and time synchronization is potentially useful for achieving higher estimation accuracy, lower communication overhead and power consumption. In this paper, we first formulate the Maximum Likelihood (ML) estimator, and then propose a Closed-form Weighted Least Square (CF-WLS) approach which can theoretically achieve the Cramer-Rao Lower Bound (CRLB) and is computationally efficient. Simulation results show that the performance of CF-WLS is similar to that of ML most of the time when a sufficient number of beacons are involved, and CF-WLS can attain the CRLB with only three-way message exchange when more than three beacons are present. CF-WLS offers reduced computational complexity over ML while maintaining similar estimation accuracy, and outperforms the Constrained Weighted Least Square (CWLS) approach, proposed in another paper, in higher estimation accuracy especially for timing parameters when only three-way message exchange is employed. The reduced complexity, communication overhead and power consumption make CF-WLS an attractive solution to the simultaneous localization and time synchronization problem in WSNs.

Push-to-Talk over Cellular (PoC) is a one-to-one or one-to-many Push-To-Talk (PTT) service designed to work over the cellular network. In the PTT, a participant may speak as soon as he/she has obtained the permission through pushing a “talk” button. The typical telephone setup delay is avoided. In the traditional floor control protocol defined in the Open Mobile Alliance standard (FCP-OMA) for PoC, at any time only one participant is permitted to speak. The permitted speaker is totally “deaf” and the listeners are fully “dumb” until the speaker releases or is revoked the floor. In this article, we propose an enhanced floor control protocol (EFCP) for PoC application in a packet voice scenario where full-duplex communications can be supported. The proposed protocol is divided into two categories: EFCP-M and EFCP-NM depending on whether media mixing is needed or supported. Through a queuing model, we compare the performance of EFCP against FCP-OMA. Experimental results show that our scheme can significantly reduce the probability that floor requests are denied and the expected waiting time in queue.

Hybrid content distribution network (HCDN) makes use of the highly complementary advantages of conventional CDN (content distribution network) and pure P2P (peer-to-peer). In HCDN, clients can concurrently retrieve content from both CDN and P2P networks. In this paper, service differentiation is formulated as a constraint optimization problem, in which two critical factors are taken into consideration: quality factor of a link and demand factor of a file. With the convex optimization theory, two bandwidth allocation algorithms, HBAA-P for source peer and HBAA-S for surrogate server, are proposed and proved for service differentiation in the hybrid architecture. Some experimental results are illustrated to make sense of the performance features of our approaches.

Automatic Repeat Request (ARQ) is an effective technique for reliable transmission of packets in wireless networks. In ARQ, however, only a few erroneous bits in a packet will cause the entire packet to be discarded at the receiver. In this case, it's wasteful to retransmit the correct bit in the received packet. The partial packet recovery only retransmits the unreliable decoded bits in order to increase the throughput of network. In addition, the cooperative transmission based on Interleave-division multiple-access (IDMA) can obtain diversity gains with multiple relays with different locations for multiple sources simultaneously. By exploring the diversity from the channel between relay and destination, we propose a relay-assisted partial packet recovery in CDMA wireless network to improve the performance of throughput. In the proposed scheme, asynchronous IDMA iterative chip-by-chip multiuser detection is utilized as a method of multiple partial recovery, which can be a complementarity in a current CDMA network. The confidence values' concept is applied to detect unreliable decoded bits. According to the result of unreliable decoded bits' position, we use a recursive algorithm based on cost evaluation to decide a feedback strategy. Then the feedback request with minimum cost can be obtained. The simulation results show that the performance of throughput can be significantly improved with our scheme, compared with traditional ARQ scheme. The upper bound with our scheme is provided in our simulation. Moreover, we show how relays' location affects the performance.

For Wireless Sensor Networks (WSNs), utilizing the same set of measurement data for simultaneous localization and time synchronization is potentially useful for achieving higher estimation accuracy, lower communication overhead and power consumption. However, localization and time synchronization are traditionally treated as two separate problems. In this paper, we propose to use Semidefinite Programming (SDP) to jointly solve the two problems at the same time. Two scenarios, Sensor Nodes (SNs) with sufficient and insufficient number of neighboring beacons, are considered. The Cramer-Rao Lower Bound (CRLB) is then derived. Simulation results are presented to contrast the performance of the proposed Simultaneous Localization and Time Synchronization-SDP (SLTS-SDP) and Generalized SLTS-SDP (GSLTS-SDP) algorithms with the conventional SDP method and the corresponding CRLBs.

This paper proposes a hybrid TOA/AOA (Time of Arrival/Angle of Arrival)-based localization algorithm for Code Division Multiple Access (CDMA) networks. The algorithm extends the Taylor Series Least Square (TS-LS) method originally developed for TOA-based systems to incorporate AOA measurements. In addition, tracking algorithms utilizing velocity and acceleration measurements are investigated. Simulation results illustrate that the proposed TOA/AOA TS-LS can provide better performance than conventional schemes in localization accuracy and in reduced likelihood of encountering non-convergence problem compared with TOA TS-LS. Tracking algorithms using the Extended and Unscented Kalman Filter (EKF and UKF) can track the objects relatively well, further decreasing the positioning error. UKF is found to provide closer tracking of the trajectory than EKF, for it truly captures the statistical mean and variance of the noises.

Wireless localization has drawn significant attention over the past decade and the received signal strength (RSS) based localization scheme provides a low-cost, low-complexity and easy-implementation solution. When the statistics of the RSS measurement error is known, the Maximum Likelihood (ML) estimator is asymptotically optimal. However, due to the nature of the localization problem itself, the formed ML estimator is nonconvex, causing the search for the global minimum very difficult. In addition, its performance highly depends on the initial point provided if a local optimization method is applied to find the solution. To circumvent this problem, we apply the Semidefinite Programming (SDP) relaxation technique to the RSS-based localization problem. After reformulation and relaxation, we finally form a convex SDP estimator. A superior property of a convex estimator is that the solution is not affected by the initial point provided since any local minimum is also its global minimum. The Cramer-Rao Lower Bound (CRLB) is then derived as a benchmark for the performance comparison. Simulation results show that the proposed SDP estimator exhibit excellent performance in the RSS-based localization system and it is very suitable for the case when there are only very limited base stations hearable.

The Hybrid CDN-P2P architecture, or HCDN, which combines the complementary advantages of CDN and P2P networks, has been proposed to reduce the deployment cost and to improve the quality of service in file sharing and video streaming applications. A replica placement algorithm (RPA) decides where to replicate the specific data. Existing RPAs for pure CDN do not work efficiently in the HCDN architecture because they do not take into consideration the contribution of the peers at the P2P distribution level. In this article, a heuristic RPA that takes into account the effects of P2P distribution is proposed for HCDN. The performance of our proposed algorithm is evaluated and the impact of some key metrics is analyzed. The experimental result shows the clear performance benefits of our approach.

Non-Line-Of-Sight (NLOS) signal propagation is the major source of error in conventional Time-Of-Arrival (TOA) based wireless location estimation algorithms. Previous research has mainly sought to address this problem in two ways: NLOS identification and NLOS mitigation. This paper focuses on the latter issue. It deals with the problem that even when NLOS measurements can be identified, among all the measurements obtained, there may still be not enough Line-Of-Sight (LOS) measurements for accurate location estimation using traditional TOA-based algorithms. With the assumptions that the total number of the measurements is greater than the minimum required and the NLOS measurements are identifiable, this paper proposes an enhanced TOA-based localization algorithm. It contains two parts: a combination stage and a Maximum Likelihood (ML) estimator. The proposed algorithm has an advantage that it does not require the information of the distribution of the NLOS bias. Simulation results show that the proposed algorithm outperforms all the other algorithms compared in dense NLOS environment.

In this paper, a novel nonlinear programming (NLP) approach for non-line-of-sight (NLOS) localization in severe multipath environments is proposed. It leverages on the bidirectional estimation of the angle of arrival (AOA) and the time of arrival (TOA) of signals between the mobile station (MS) and the reference stations (RSs), and has the ability to work with just two paths. Basic approach (BA) and extended approach (EA) are addressed, and the latter employs a simple method to identify one-bound path with high probability. Simulation results illustrate that the proposed algorithm can improve the localization accuracy greatly, especially when only few one-bound scattering paths exist.

This paper presents GConf, a peer-to-peer Gossip-based delay sensitive N-to-N information dissemination protocol, intended for applications such as real-time multiparty conferencing. Through 3-way gossip-based exchanges with randomly selected peers, information frames can be spread throughout the whole community within a delay of 1.5 round-trip-times. The non-delivery probability can be improved exponentially as a function of the peer fanout. Performance evaluations based on a mathematical model and simulations are presented.

In this paper, a novel time-of-arrival estimation algorithm is proposed for impulse radio-based UWB systems in dense multipath environment. In particular, a dedicated ranging sequence with good cross-correlation property is proposed and a threshold-based search-back unit is introduced, with the purpose of supporting high-precision ranging even at low signal-to-noise ratio. An approximate closed-form expression on the optimal threshold is derived based on the Rayleigh statistical analysis, and its accuracy and tightness are verified by simulations. Results show that the proposed ranging scheme achieves an excellent mean absolute error performance in the order of nanoseconds without introducing too much latency.

Maximizing the rate of transmission over a network with fixed amount of power gives the most economic way to communicate in a network. This paper investigates accumulative repetition forwarding strategy in a wireless ad-hoc network using cooperative forwarding approaches that allow adaptive power allocation among nodes. We analyze the feasibility and performance gain of channel reuse over this network, where multiple transmit-and-receive pairs coexist simultaneously using the same channel. Under this framework, we present the jointly optimal power allocation and channel reuse solution. This solution can be computed in polynomial time and brings significant improvement in network performance.

In this paper, we explore new optical time-division multiplexing (OTDM) ring architectures. The objective of our study is to achieve high space-reuse efficiency of each time slot without using time-slot interchanges, which are expensive and difficult to implement in the optical domain. Although a TDM slot is often compared to a wavelength channel in a wavelength-division multiplexing (WDM) network, we show that the intrinsic propagation delay in an OTDM network will lead to a phenomenon, called a slot cycle in the paper, that has no counterpart in WDM networks. By exploring the concept and the algebraic relationship between the frame size and the total propagation delay of the ring, we discover a novel OTDM ring architecture that achieves a high space-reuse efficiency without using time-slot interchanges. The equivalent of this architecture in the WDM domain can only be achieved with the use of many wavelength converters. We also study the efficiency of the architecture based on different types of traffic demand models in the network.

Optical TDM allows multiple traffic streams to share the bandwidth of a wavelength. This paper presents a framework for determining the capacity and routing strategy needed to establish different logical topologies on an optical TDM ring network with propagation delay but no Optical Time Slot Interchange (OTSI); OTSI requires optical buffering which is not practical at the current time. We show that an optical TDM ring is characterized by a parameter called cycle length. The impact of the cycle length on the capacity of a bi-directional optical TDM ring is evaluated and joint routing and time-slot assignment strategies are developed.

Internet applications such as voice over IP and instant messaging require the support of efficient person search. In these applications, a user often has a list of people whom he/she often calls, the so-called "hot list." Traditional structured peer-to-peer networks for file sharing, despite of their support of unique item search, are not efficient for person search. This is mainly because they do not take into account human communication characteristics such as close social network, user-dependent hot list, and high skewness in access popularity. We show in this paper that person search can be much more efficient by taking into consideration of our communication features. Based on Pastry, our system makes use of hot lists in the routing process and clusters people of the same community together in the search graph, thereof creating a "small-world" effect. Simulation results show that our scheme achieves significantly lower search time than Pastry (by as much as 50%).

This paper investigates a novel active buffer management scheme, "Jitter Detection" (JD) for gateway-based congestion control to stream multimedia traffics in packet-switched networks. The quality of multimedia presentation can be greatly degraded due to network delay variation or jitter when transported over a packet-switched network. Jitter degrades the timing relationship among packets in a single media stream and between packets from different media streams and, hence, creates multimedia synchronization problems. Moreover, too much jitter will also degrade the performance of the streaming buffer in the client. Packets received by the client will be rendered useless if they have accumulated enough jitter. The proposed active buffer management scheme will improve the quality of service in multimedia networking by detecting and discarding packets that accumulated enough jitter, such as to maintain a high bandwidth for packets within the multimedia stream's jitter tolerance. Simulation results have shown that the proposed scheme can effectively lower the average received packet jitter and increase the goodput of the received packets when compared to random early detection (RED) and DropTail used in gateway-based congestion control. Furthermore, simulation results have also revealed that the proposed scheme can maintain the same TCP friendliness when compared to that of RED and DropTail used for multimedia streams.

Buffer minimization is an important design issue in optical circuit switching networks because of the high cost of optical buffers. In this paper, we show how to design routing strategies that can reduce buffer requirement in such networks. We propose two classes of buffer-efficient routing schemes and compare their performance in terms of complexity, buffer requirement and blocking probability.

Optical TDM (O-TDM) networks can provide a finer bandwidth granularity than WDM networks, and will play an important role in future all-optical networks. Since optical buffers are expensive, a small buffer size is characteristic of O-TDM systems. This paper analyzes the problem of routing and time-slot assignment in O-TDM networks. The results lead to the proposal of a Dijkstra-like shortest-path routing scheme that intends to maximize the performance of an optical network with a small number of optical buffers. Performance evaluation of the proposed scheme is also presented.

Optical time-division multiplexing (O-TDM) networks can provide a finer bandwidth granularity than wavelength-division multiplexing networks, and will play an important role in future all-optical networks. Since optical buffers are expensive, a small buffer size will be the characteristic of O-TDM systems. This paper analyzes the problem of routing and time-slot assignment in O-TDM networks. The results lead to the proposal of a Dijkstra-like shortest-path routing scheme that intends to maximize the performance of an optical network with a small number of optical buffers. Performance evaluation of the proposed scheme is also presented.

This paper investigates a novel active buffer management scheme, "jitter detection" (JD) for gateway-based congestion control to stream multimedia traffics in packet-switched networks. The proposed active buffer management scheme will improve the quality of service in multimedia networking by detecting and discarding useless packets that accumulated large enough jitter. Such as to maintain a high bandwidth for packets within the multimedia stream's jitter tolerance. Simulation results have shown that the proposed scheme can effectively lower the average packet jitter and increase the goodput of the received packets when compared to random early detection (RED), and droptail used in gateway-based congestion control. Furthermore, simulation results have also revealed that the proposed scheme can maintain the same TCP-friendliness when compared to that of RED and droptail used for multimedia streams.

This paper presents cost-based QoS routing and compares its performance with the commonly used widest-shortest-path routing. The advantages of cost-based routing are demonstrated in two major areas. First, it is stable under heavy-loaded conditions. Second, it requires a lower state-update overhead and is more robust to the inaccuracy of state information. The concept presented in the paper can be applied to any reservation-based QoS approach - like IntServ or MPLS type networks.

We introduce the notion of photonic circuit switching (PCS) networks and investigate the routing and time-slot assignment (RTA) problem for such networks. PCS is analogous to TDM circuit switching in electronic switching networks. It provides a way for sub-division of the capacity of a wavelength channel in optical networks. By finding routes and assigning time slots carefully, the optical buffering requirement in such networks can be greatly reduced.

Mixed continuous-bit-rate (CBR) and bursty traffic contending for transmission on any output line of a broadband switch based on the asynchronous transfer mode (ATM) is modeled as a superposition of traffic from a number of independent random and binary sources. With the use of a recursive algorithm, a complete queuing analysis is presented. The queue length distribution, the delay distribution, and the cell loss probability for a finite buffer system are exactly calculated. Cases considered and analyzed include: delay priority for CBR traffic, absolute cell loss priority for DS1/DS3 emulation or guaranteed bandwidth CBR traffic with a stringent cell loss requirement, and threshold cell dropping for voice CBR traffic with a high degree of cell loss tolerance.>