13122574
Bandwidth guaranteed call admission in TDMA/CDMA ad hoc wireless networks
This paper first studied the timeslot assignment problem in time division multiple access/code division multiple access (TDMA/CDMA) wireless ad hoc networks. Given a path P, we prove that a timeslot assignment providing one unit of bandwidth on P can be found in O(|P|) time if such an assignment exists. The results have been extended to the case that P can provide two units of bandwidth. Based on the timeslot assignment for the special cases, an efficient slot assignment algorithm with O(|P|^2k) is proposed for general cases, where k is the number of slots in a TDMA frame. Then, the timeslot assignment algorithm is integrated into a quality of service (QoS) call admission scheme for QoS call requests. Extensive simulations are conducted and the results have demonstrated the superior performance of our method.
11860267
On optimal placement of relay nodes for reliable connectivity in wireless sensor networks
The paper addresses the relay node placement problem in two-tiered wireless sensor networks. Given a set of sensor nodes in Euclidean plane, our objective is to place minimum number of relay nodes to forward data packets from sensor nodes to the sink, such that: 1) the network is connected, 2) the network is 2-connected. For case one, we propose a (6+ε)-approximation algorithm for any ε > 0 with polynomial running time when ε is fixed. For case two, we propose two approximation algorithms with (24+ε) and (6/T+12+ε), respectively, where T is the ratio of the number of relay nodes placed in case one to the number of sensors. We further extend the results to the cases where communication radiuses of sensor nodes and relay nodes are different from each other.
6771108
Fault-Tolerant Relay Node Placement in Wireless Sensor Networks
The paper addresses the relay node placement problem in two-tiered wireless sensor networks. Given a set of sensor nodes in an Euclidean plane, our objective is to place minimum number of relay nodes to forward data packets from sensor nodes to the sink, such that: 1 the network is connected, 2 the network is 2-connected. For case one, we propose a 6+e-approximation algorithm for any e>0 with polynomial running time when e is fixed. For case two, we propose two approximation algorithms with 24+e and 6/T+12+e, respectively, where T is the ratio of the number of relay nodes placed in case one to the number of sensors.
893749
A Distributed and Efficient Flooding Scheme Using 1-Hop Information in Mobile Ad Hoc Networks
Flooding is one of the most fundamental operations in mobile ad hoc networks. Traditional implementation of flooding suffers from the problems of excessive redundancy of messages, resource contention, and signal collision. This causes high protocol overhead and interference with the existing traffic in the networks. Some efficient flooding algorithms were proposed to avoid these problems. However, these algorithms either perform poorly in reducing redundant transmissions or require each node to maintain 2-hop (or more) neighbors information. In the paper, we study the sufficient and necessary condition of 100 percent deliverability for flooding schemes that are based on only 1-hop neighbors information. We further propose an efficient flooding algorithm that achieves the local optimality in two senses: 1) the number of forwarding nodes in each step is minimal and 2) the time complexity for computing forwarding nodes is the lowest, which is O(nlogn), where n is the number of neighbors of a node. Extensive simulations have been conducted and simulation results have shown the excellent performance of our algorithm
14550653
QoS Topology Control with Minimal Total Energy Cost in Ad Hoc Wireless Networks
This paper discusses the energy efficient QoS topology control problem in ad hoc wireless networks. Given a set of nodes in a plane, end-to-end traffic demands and delay bounds between node pairs, the problem is to find a network topology that can meet the QoS requirements and the total transmission power of nodes is minimized. We consider two cases of the problem: 1) the traffic demands are not splittable, and 2) the traffic demands are splittable. The first case is formulated as an integer linear programming problem. The latter case is formulated as a mixed integer linear programming problem. A greedy algorithm and an approximation algorithm with ratio n are proposed to solve the problem, where n is the number of nodes. Extensive simulations are conducted to evaluate the performance of proposed algorithms.
16781216
Fast hierarchical clustering and its validation
Clustering is the task of grouping similar objects into clusters. A prominent and useful class of algorithm is hierarchical agglomerative clustering (HAC) which iteratively agglomerates the closest pair until all data points belong to one cluster. It outputs a dendrogram showing all N levels of agglomerations where N is the number of objects in the dataset. However, HAC methods have several drawbacks: (1) high time and memory complexities for clustering, and (2) inefficient and inaccurate cluster validation. In this paper we show that these drawbacks can be alleviated by closely studying the dendrogram. Empirical study shows that most HAC algorithms follow a trend where, except for a number of top levels of the dendrogram, all lower levels agglomerate clusters which are very small in size and close in proximity to other clusters. Methods are proposed that exploit this characteristic to reduce the time and memory complexities significantly and to make validation very efficient and accurate. Analyses and experiments show the effectiveness of the proposed method.
15600947
Improving backpropagation learning with feature selection
There exist redundant, irrelevant and noisy data. Using proper data to train a network can speed up training, simplify the learned structure, and improve its performance. A two-phase training algorithm is proposed. In the first phase, the number of input units of the network is determined by using an information base method. Only those attributes that meet certain criteria for inclusion will be considered as the input to the network. In the second phase, the number of hidden units of the network is selected automatically based on the performance of the network on the training data. One hidden unit is added at a time only if it is necessary. The experimental results show that this new algorithm can achieve a faster learning time, a simpler network and an improved performance.
17123515
A Probabilistic Approach to Feature Selection - A Filter Solution
Feature selection can be de ned as a problem of nding a minimum set of M relevant at tributes that describes the dataset as well as the original N attributes do where M N After examining the problems with both the exhaustive and the heuristic approach to fea ture selection this paper proposes a proba bilistic approach The theoretic analysis and the experimental study show that the pro posed approach is simple to implement and guaranteed to nd the optimal if resources permit It is also fast in obtaining results and e ective in selecting features that im prove the performance of a learning algo rithm An on site application involving huge datasets has been conducted independently It proves the e ectiveness and scalability of the proposed algorithm Discussed also are various aspects and applications of this fea ture selection algorithm
2528293
Rule mining with prior knowledge - a belief networks approach
Some existing data mining methods, such as classification trees, neural networks and association rules, have the drawbacks that the user's prior knowledge cannot be easily specified and incorporated into the knowledge discovery process, and the rules mined from databases lack quantitative analyses. In this paper, we propose a belief networks method for rule mining, which takes the advantage of belief networks as the directed acyclic graph language and their function for numerical representation of probabilistic dependencies among the variables in the database, so that it can overcome the drawbacks. Since belief networks provide a natural representation for capturing causal relationship among a set of variables, our proposed method can mine more general correlation rules which can capture the relationship of more than two attribute variables. The potential application of the proposed method is demonstrated through the detailed case studies on benchmark databases.
8827382
Efficient Hierarchical Clustering Algorithms Using Partially Overlapping Partitions
Clustering is an important data exploration task. A prominent clustering algorithm is agglomerative hierarchical clustering. Roughly, in each iteration, it merges the closest pair of clusters. It was first proposed way back in 1951, and since then there have been numerous modifications. Some of its good features are: a natural, simple, and non-parametric grouping of similar objects which is capable of finding clusters of different shape such as spherical and arbitrary. But large CPU time and high memory requirement limit its use for large data. In this paper we show that geometric metric (centroid, median, and minimum variance) algorithms obey a 90-10 relationship where roughly the first 90iterations are spent on merging clusters with distance less than 10the maximum merging distance. This characteristic is exploited by partially overlapping partitioning. It is shown with experiments and analyses that different types of existing algorithms benefit excellently by drastically reducing CPU time and memory. Other contributions of this paper include comparison study of multi-dimensional vis-a-vis single-dimensional partitioning, and analytical and experimental discussions on setting of parameters such as number of partitions and dimensions for partitioning.