Search

One of the most fundamental topics in subspace coding is to explore the maximal possible value ${\bf A}_q(n,d,k)$ of a set of $k$-dimensional subspaces in $\mathbb{F}_q^n$ such that the subspace distance satisfies $\operatorname{d_S}(U,V) = \dim(U+V)-\dim(U\cap V) \geq d$ for any two different $k$-dimensional subspaces $U$ and $V$ in this set. In this paper, we propose a construction for constant dimension subspace codes by inserting a composite structure composing of an MRD code and its sub-codes. Its vast advantage over the previous constructions has been confirmed through extensive examples. At least $49$ new constant dimension subspace codes which exceeds the currently best codes are constructed., an error in the proof

Wireless magnetic sensor networks provide a low-cost technology for the outdoor real-time parking tracking system. However, the magnetic sensor is susceptible to the interference caused by vehicles parked in adjacent spaces. Most existing detection systems are solely based on local sampled data from the sensor node and they are prone to high false and missed detection rates in the case of a low signal-to-noise ratio. This paper proposes a collaborative sensing parking tracking system by fusing the signals of the adjacent sensors to eliminate the interference. Sensor nodes convert magnetic signals into signatures represented by peak values, and then the base station computes the spatial relationships between adjacent signatures to identify parking event or interference. An experiment system includes sixty sensor nodes that were deployed in bay parking spaces. Experiment results verified that the proposed system has better detection accuracy than existing systems.

In a large-scale computing cluster, the job completions can be substantially delayed due to two sources of variability, namely, variability in the job size and that in the machine service capacity. To tackle this issue, existing works have proposed various scheduling algorithms which exploit redundancy wherein a job runs on multiple servers until the first completes. In this paper, we explore the impact of variability in the machine service capacity and adopt a rigorous analytical approach to design scheduling algorithms using redundancy and checkpointing. We design several online algorithms which can dynamically vary the number of redundant copies for jobs. We also provide new theoretical performance bounds for these algorithms in terms of the overall job flowtime by introducing the notion of a speedup function, based on which a novel potential function can be defined to enable the corresponding competitive ratio analysis. In particular, by adopting the online primal-dual fitting approach, we prove that our SRPT+R Algorithm in a non-multitasking cluster is $(1+\epsilon)$ ( 1 + e ) ( 1 + e ) -speed, $\ O(\frac{1}{\epsilon })$ O ( 1 e ) O ( 1 e ) -competitive. We also show that our proposed Fair+R and LAPS+R( $\beta$ β β ) Algorithms for a multitasking cluster are $(4+\epsilon)$ ( 4 + e ) ( 4 + e ) -speed, $\ O(\frac{1}{\epsilon })$ O ( 1 e ) O ( 1 e ) -competitive and ( $2 + 2\beta + 2\epsilon)$ 2 + 2 β + 2 e ) 2 + 2 β + 2 e ) -speed $O(\frac{1}{\beta \epsilon })$ O ( 1 β e ) O ( 1 β e ) -competitive respectively. We demonstrate via extensive simulations that our proposed algorithms can significantly reduce job flowtime under both the non-multitasking and multitasking modes.

Many efforts have been done to better exploit multiple radios and multiple channels to improve system performance in wireless mesh networks. However, in the case of the IEEE 802.11b/g/n family of standards, there are only three non-overlapping channel, the simple use of orthogonal channels cannot effectively eliminate the interference. The simultaneous use of multiple partially overlapping channels has been certified as an effective way to further eliminate interference and improve network performance in 802.11-based wireless mesh networks. Good network topological structure can lead to low interference, load balancing and high throughput. This research looks into the problem of topology control and partially overlapping channel assignment to improve the performance of multi-radio multi-channel multirate wireless mesh networks. We propose an optimal topology control algorithm and greedy channel assignment algorithm to maximize the network capacity (in term of each node’s traffic delivery ratio). Simulation results present that our topology control and partially overlapping channel assignment method can dramatically improve system throughput.

In cognitive radio ad hoc networks (CRAHNs), the secondary users' links are interrupted by the arrival of primary users, which leads to a significant increase of the number of transmissions per packet. Since network coding and opportunistic routing can reduce the number of transmissions over unreliable wireless links, they are more suitable for CRAHNs. Network coding-based opportunistic routing has been well studied in previous works for traditional ad hoc networks. However, existing approaches have limitations to handle CRAHNs. First, the routing decisions of these methods aim to find one optimal forwarding set for the whole path from the source to the destination. If the channel conditions change dynamically, the pre-selected forwarding set may become unavailable or non-optimal. Second, their coding schemes are not efficient enough to cope with the dynamic spectrum variation in CRAHNs. In this paper, we attempt to overcome these limitations and propose a network-coding-based geographic segmented opportunistic routing scheme for CRAHNs, by fully embracing its characteristics. In our scheme, the whole path from the source to the destination is cut down into several smaller opportunistic route segments, where the packets are transmitted through multiple segments based on a step-by-step forwarding procedure until all the packets are delivered to the destination. Since our scheme utilizes only local spectrum opportunities, topology information, and geometric conditions to compute the forwarding set for each short-term opportunistic route segment, it can better adapt to dynamic spectrum environments and changing network topologies in CRAHNs. Furthermore, we construct a coding graph to show that our coding problem is a reduction from the maximum clique problem, and we propose an efficient network coding strategy to solve it. Simulation results show that our scheme can achieve a considerable performance, compared with the latest opportunistic routing protocols designed for CRAHNs.

Motivated by various settings, we study a new Influence Maximization problem at the Community level (IMC) which aims at finding k users to maximize the benefit of influenced communities where a community is influenced iff the number of influenced users belong to this community exceeds its predefined threshold. In general, IMC objective function is not submodular nor supermodular, thereby making it very challenging to apply existing greedy solutions of the classic influence maximization (IM) where submodular function is required. Furthermore, the major challenge in the traditional methods for any related IM problem is the inefficiency in estimating the influence spread. IMC brings this difficulty to a higher level when considering influenced communities instead of influencing each individual user. In this paper, we propose different approximation algorithms for IMC: (1) Using Sandwich approach with a tight submodular function to bound the IMC objective function, (2) Activating the top-k influencing nodes found from network sampling. Furthermore, when the activated thresholds of communities are bounded by a constant, we propose an algorithm with performance guarantee tight to the inapproximability of IMC assuming the exponential time hypothesis. Each algorithm has its own strengths in a trade-off between effectiveness and running time, which are illustrated both in theory and comprehensive experimental evaluation.

In this paper, we discuss the QoS guaranteed causal ordering group communication for cognitive radio (CR) ad hoc networks. The issue of causal ordering has been studied extensively by previous works. However, these works considered the problem at the transport layer and the methods in the works incurred high communication overhead and the long latency for message delivery. In this paper, we discuss the causal ordering at the network layer. The problem of our concern is: given a QoS group communication request in a CR ad hoc network, how to set up the connection so that the causal ordering of the group communication can be preserved, and the bandwidth consumption of the communication is minimized under the condition that the QoS requirement is satisfied. In this paper, we focus on the bandwidth requirement. We propose a two-phase method to solve the problem. In the method, we first construct a multicast tree for the communication, and then assign slots for all tree links. It is proved that the method can preserve the causal ordering of messages without extra communication overhead nor the latency for delivering messages. Simulations are conducted to show the performance of our proposed method.

Due to the limited number of orthogonal channels in IEEE 802.11 b/g standards, the simple application of non-overlapping channels cannot completely eliminate the interference. POCs-based channel assignment has been identified as an emerging technology to further eliminate interference and improve system throughput. This research looks into the problem of partially overlapping channel assignment to improve the performance of multi-radio multi-channel multirate wireless mesh networks. Based on the analysis of the existing methods, we propose a greedy channel assignment method to maximize system throughput. Simulation results presents that our partially overlapping channel assignment method can be dramatically improved by fully exploiting partially overlapping channels as well as orthogonal channels.

Using directional antennas to reduce interference and improve throughput in multihop wireless networks has attracted much attention from the research community in recent years. In this paper, we consider the issue of minimum delay broadcast in multirate wireless mesh networks using directional antennas. We are given a set of mesh routers equipped with directional antennas, one of which is the gateway node and the source of the broadcast. Our objective is to minimize the total transmission delay for all the other nodes to receive a broadcast packet from the source, by determining the set of relay nodes and computing the number and orientations of beams formed by each relay node. We propose a heuristic solution with two steps. Firstly, we construct a broadcast routing tree by defining a new routing metric to select the relay nodes and compute the optimal antenna beams for each relay node. Then, we use a greedy method to make scheduling of concurrent transmissions without causing beam interference. Extensive simulations have demonstrated that our proposed method can reduce the broadcast delay significantly compared with the methods using omnidirectional antennas and single-rate transmission. In addition, the results also show that our method performs better than the method with fixed antenna beams. Copyright © 2012 John Wiley & Sons, Ltd.

In this paper, we discussed the issues of QoS multicast routing in cognitive radio ad hoc networks. The problem of our concern was: given a cognitive radio ad hoc network and a QoS multicast request, how to find a multicast tree so that the total bandwidth consumption of the multicast is minimized while the QoS requirements are met. We proposed two methods to solve it. One is a two-phase method. In this method, we first employed a minimal spanning tree-based algorithm to construct a multicast tree and then proposed a slot assignment algorithm to assign timeslots to the tree links such that the bandwidth consumption of the tree is minimized. The other is an integrated method that considers the multicast routing together with the slot assignment. Extensive simulations were conducted to show the performance of our proposed methods. Copyright © 2011 John Wiley & Sons, Ltd.

Language models are fundamental to many applications in natural language processing. Most language models are trained on training data that do not support discount parameters tuning. In this work, we present novel language models based on tunable discounting mechanisms. The language models are trained on a large training set, but their discount parameters can be tuned to a target set. We explore tunable discounting and polynomial discounting based on modified Kneser-Ney models. With the resulting implementation, our language models achieve perplexity improvements in in-domain and out-of-domain evaluation. The experimental results indicate that our new models significantly outperform the baseline model and are especially suited for domain adaptation.

In multi-hop WLANs, it is more efficient to let some clients relay traffic for the clients whose distances are a bit far away from the AP, which increases the transmission efficiency. The existing solutions for multi-hop WLANs try to choose one or two fixed best relays to forward packets. However, the links between far-away clients and the AP are intermittently connected, and end-to-end paths may not exit. In order to fill this gap, using opportunistic forwarding, our solutions do not fix a relay; the source simply broadcasts its signal, any client who received the signal will relay the traffic. In this paper, our object is to extend the connectivity by opportunistic forwarding for far-away clients in multi-hop WLAN accesses. The original contributions made by this paper include: 1) We develop a general model to analyze the throughput of opportunistic forwarding in multi-hop WLANs. 2) We classify the clients into three groups, and propose a centralized opportunistic routing relay algorithm for each group of clients to achieve the optimal system throughput. 3) We propose a distributed opportunistic routing relay protocol for clients' disconnected and connected actions. Extensive simulations have been done in NS-2. The simulation results show that our protocol can significantly increase the service's coverage and connectivity of the entire network, compared with those methods by traditional one-hop and multi-hop relay.

The use of multiple channels in 802.11 wireless local area networks can improve network performance. Many efforts have been done to better exploit multiple non-overlapped channels. However, the number of orthogonal channels in the Institute of Electrical and Electronics Engineers 802.11 standards is very much limited. Recent studies indicate that we can improve the full-range channel utilization and the network throughput by properly utilizing the partially overlapping channels. However, little work was focused on channel assignment for partially overlapping channels. In this paper, we investigate the problem of partially overlapping channel assignment to improve the performance of 802.11 wireless networks based on the Signal to Interference-Noise Ratio interference model. Using the Signal to Interference-Noise Ratio model, we deduce a direct relationship between maximizing system throughput and minimizing total interference when partially overlapping channels are employed. After that, we propose a greedy method to minimize the total interference for throughput maximization. We evaluate our algorithm through extensive simulations and compare its performances with those of the state-of-the-art. Copyright © 2013 John Wiley & Sons, Ltd.

In this paper, we address the problem of joint power control and scheduling for minimizing broadcast delay in wireless mesh networks. Given a set of mesh routers and a routing tree rooted from the gateway node, our task is to assign power for each relay node and compute an optimal transmission schedule such that the longest delay for a packet broadcast from the root node to all the other routers is minimized. We consider rate adaption in our scheme. This is a difficult issue. On one hand, if we increase the transmission power, the packet can be transmitted out at a higher data rate, which leads to less delay; on the other hand, a high transmission power would have larger interference range, which makes less nodes that can transmit concurrently and thus cause longer delay to deliver the packet to farther routers. We study the tradeoff between the two parameters, data rate and concurrency, and propose a balanced method for power control and transmission scheduling. We introduce a metric called standard deviation of remaining broadcast time of nodes to determine the priority of the two parameters. When this standard deviation is above a threshold, the transmitting nodes will take the data-rate-first approach to increase the data rate; otherwise the concurrency-first approach will be used to increase the number of concurrent transmissions in the system. Extensive simulations have demonstrated that our proposed method can reduce the broadcast delay significantly compared with the methods using fixed transmission power. In addition, the results also show that our balanced method performs better than both pure data-rate-first method and concurrency-first method.

It has been believed that the simultaneous use of multiple channels in 802.11 wireless local area networks (WLANs) can improve network performance. Many efforts have been done to better exploit multiple non-overlapped channels. However, due to the limited number of orthogonal channels in IEEE 802.11 b/g standards, using only non-overlapping channels cannot completely eliminate the interference. Recent studies indicate that we can improve the full-range channel utilization and the network throughput by properly utilizing the partially overlapping channels. However, there are only limited studies of channel assignment algorithms for partially overlapping channels. In this paper, we investigate the problem of partially overlapping channel assignment to improve the performance of 802.11 wireless networks based on SINR model. Using the SINR model, we deduce a direct relationship between maximizing system throughput and minimizing total interference when partially overlapping channels are employed. After that, we propose a greedy method to minimize the total interference for throughput maximization. We evaluate our algorithm through extensive simulations and compare its performances with those of the state-of-the-art.

In this paper, we discuss the issue of unicast routing in dynamic CR networks. The problem of our concern is: given a set of CR nodes with geographical positions and temporarily available channels, how to design a protocol so that the average number of transmissions per packet for a unicast transmission is minimized. We propose a novel distributed protocol where packets are transmitted through successively geographic closer intermediate destination nodes, until eventually destination is reached. The intermediate destination nodes are within a two-hop neighborhood and locally chosen by a heuristic algorithm we develop. A priority-based opportunistic routing method is adopted to forward the packets between two nearby intermediate destination nodes. Extensive simulations are conducted to show the performance of our protocol.

In this paper, we study the problem of enhancing the fault tolerance of IEEE 802.11 wireless local area networks in the design stage. Our goal is to place minimal number of APs (access points), such that the system can tolerate AP failures while guaranteeing QoS requirement. Given a set of clients (end-users) in a region, each client has a traffic demand for Internet access. Our concern is to find out minimal number of APs and their locations, so that both fault tolerance and QoS constraints can be satisfied. That is, when there is no AP failure, all clients' traffic demands should be met. When one AP fails, the clients it serves shall switch to other APs and a certain percentage of traffic demands of these clients affected shall still be met. We proposed a heuristic algorithm to solve this problem. Firstly we place minimal number of APs to ensure that connection requirements and per-client degrading traffic demand can be met. Secondly, we continue to add APs to meet per-client normal traffic demand. Finally, we place more APs to tolerate failure of the APs placed in the first step. Simulation are conducted to show the performance of our proposed method.

In this paper, we discuss the causal ordering group communication for cognitive radio (CR) networks. The issue of causal ordering has been studied extensively by previous works. However, these works considered the problem at the application layer and the methods in the works incurred high communication overhead and the long latency for message delivery. In this paper, we discuss the causal ordering at the network layer.The problem of our concern is: given a group communication request in a CR network, how to set up the connection so that the causal ordering of the group communication can be preserved, and the bandwidth consumption of the communication is minimized. We propose a two-phase method to solve it. In the method, we first construct a multicast tree for the communication, and then assign slots for all tree links. It is proved that the method can preserve the causal ordering of messages without extra communication overhead nor the latency for delivering messages. Simulations are conducted to show the performance of our proposed method.

The survivability evaluation of MANET includes many metrics. Among them, path reliability is the fundamental one. However, most existing work on it has focused either on connectivity or the link duration time solely. Due to the special features of MANET, the radio coverage and node energy also have high effluence on the reliability of the path. Usually, tradeoffs should be considered among these features to obtain the largest survivability. So, this paper presents a survivability model that integrates these metrics together and evaluates the MANET survivability fairly. Simulation shows how the individual metric or the total metrics affect the survivability of MANET. This paper also points out that the proposed analytical method can evaluate the survivability of MANET fairly well.