The FlexRay bus is a communication standard used in the automotive industry. It offers a deterministic message transmission in the static segment following a time-triggered schedule. Even if its bandwidth is ten times higher than the bandwidth of controller area network (CAN), its throughput limits are going to be reached in high-class car models soon. A solution that could postpone this problem is to use an efficient scheduling algorithm that exploits both channels of the FlexRay. The significant and often neglected feature that can theoretically double the bandwidth is the possibility to use two independent communication channels that can intercommunicate through the gateway. In this paper, we propose a heuristic algorithm that decomposes the scheduling problem to the electronic control unit (ECU)-to-channel assignment subproblem, which decides which channel the ECUs should be connected to and the channel scheduling subproblem that creates static segment communication schedules for both channels. The algorithm is able to create a schedule for cases where channels are configured in the independent mode, as well as in the fault-tolerant mode or in cases where just part of the signals are fault tolerant. Finally, the algorithm is evaluated on real data and synthesized data, and the relation between the portion of fault-tolerant signals and the number of allocated slots is presented.
It is necessary to decide, for each ECU, if the ECU should be connected to channel A, B or to both of them to divide the communication between the channels. A similar problem from computer science is clustering. Some widespread clustering methods are expectation-maximization (EM) and the K-Means algorithm @cite_13 . Graph clustering and spectral clustering methods @cite_15 are important for clustering problems that can be modeled by graphs. Another classical combinatorial optimization problem related to assigning items to subsets is number partitioning @cite_16 .
@cite_15 @cite_16 @cite_13
2104837959 2964083987 2065424480 2101866190
In this paper, we present "k-means+ID3", a method to cascade k-means clustering and the ID3 decision tree learning methods for classifying anomalous and normal activities in a computer network, an active electronic circuit, and a mechanical mass-beam system. The k-means clustering method first partitions the training instances into k clusters using Euclidean distance similarity. On each cluster, representing a density region of normal or anomaly instances, we build an ID3 decision tree. The decision tree on each cluster refines the decision boundaries by learning the subgroups within the cluster. To obtain a final decision on classification, the decisions of the k-means and ID3 methods are combined using two rules: 1) the nearest-neighbor rule and 2) the nearest-consensus rule. We perform experiments on three data sets: 1) network anomaly data (NAD), 2) Duffing equation data (DED), and 3) mechanical system data (MSD), which contain measurements from three distinct application domains of computer networks, an electronic circuit implementing a forced Duffing equation, and a mechanical system, respectively. Results show that the detection accuracy of the k-means+ID3 method is as high as 96.24 percent at a false-positive-rate of 0.03 percent on NAD; the total accuracy is as high as 80.01 percent on MSD and 79.9 percent on DED The classical center based clustering problems such as k-means median center assume that the optimal clusters satisfy the locality property that the points in the same cluster are close to each other. A number of clustering problems arise in machine learning where the optimal clusters do not follow such a locality property. For instance, consider the r -gather clustering problem where there is an additional constraint that each of the clusters should have at least r points or the capacitated clustering problem where there is an upper bound on the cluster sizes. Consider a variant of the k-means problem that may be regarded as a general version of such problems. Here, the optimal clusters O 1, ..., O k are an arbitrary partition of the dataset and the goal is to output k-centers c 1, ..., c k such that the objective function ( _ i = 1 ^ k _ x O_ i ||x - c_ i ||^ 2 ) is minimized. It is not difficult to argue that any algorithm (without knowing the optimal clusters) that outputs a single set of k centers, will not behave well as far as optimizing the above objective function is concerned. However, this does not rule out the existence of algorithms that output a list of such k centers such that at least one of these k centers behaves well. Given an error parameter e > 0, let l denote the size of the smallest list of k-centers such that at least one of the k-centers gives a (1 + e) approximation w.r.t. the objective function above. In this paper, we show an upper bound on l by giving a randomized algorithm that outputs a list of (2^ O (k ) ) k-centers. We also give a closely matching lower bound of (2^ (k ) ). Moreover, our algorithm runs in time (O (n d 2^ O (k ) ) ). This is a significant improvement over the previous result of Ding and Xu (2015) who gave an algorithm with running time O(n d ⋅ (log n) k ⋅ 2 p o l y(k e)) and output a list of size O((log n) k ⋅ 2 p o l y(k e)). Our techniques generalize for the k-median problem and for many other settings where non-Euclidean distance measures are involved. We propose novel cooperative spectrum sensing (CSS) algorithms for cognitive radio (CR) networks based on machine learning techniques which are used for pattern classification. In this regard, unsupervised (e.g., K-means clustering and Gaussian mixture model (GMM)) and supervised (e.g., support vector machine (SVM) and weighted K-nearest-neighbor (KNN)) learning-based classification techniques are implemented for CSS. For a radio channel, the vector of the energy levels estimated at CR devices is treated as a feature vector and fed into a classifier to decide whether the channel is available or not. The classifier categorizes each feature vector into either of the two classes, namely, the "channel available class" and the "channel unavailable class". Prior to the online classification, the classifier needs to go through a training phase. For classification, the K-means clustering algorithm partitions the training feature vectors into K clusters, where each cluster corresponds to a combined state of primary users (PUs) and then the classifier determines the class the test energy vector belongs to. The GMM obtains a mixture of Gaussian density functions that well describes the training feature vectors. In the case of the SVM, the support vectors (i.e., a subset of training vectors which fully specify the decision function) are obtained by maximizing the margin between the separating hyperplane and the training feature vectors. Furthermore, the weighted KNN classification technique is proposed for CSS for which the weight of each feature vector is calculated by evaluating the area under the receiver operating characteristic (ROC) curve of that feature vector. The performance of each classification technique is quantified in terms of the average training time, the sample classification delay, and the ROC curve. Our comparative results clearly reveal that the proposed algorithms outperform the existing state-of-the-art CSS techniques. Spectral clustering is a popular and successful approach for partitioning the nodes of a graph into clusters for which the ratio of outside connections compared to the volume (sum of degrees) is small. In order to partition into k clusters, one first computes an approximation of the bottom k eigenvectors of the (normalized) Laplacian of G, uses it to embed the vertices of G into k-dimensional Euclidean space R^k, and then partitions the resulting points via a k-means clustering algorithm. It is an important task for theory to explain the success of spectral clustering. (COLT, 2015) made an important step in this direction. They showed that spectral clustering provably works if the gap between the (k+1)-th and the k-th eigenvalue of the normalized Laplacian is sufficiently large. They proved a structural and an algorithmic result. The algorithmic result needs a considerably stronger gap assumption and does not analyze the standard spectral clustering paradigm; it replaces spectral embedding by heat kernel embedding and k-means clustering by locality sensitive hashing. We extend their work in two directions. Structurally, we improve the quality guarantee for spectral clustering by a factor of k and simultaneously weaken the gap assumption. Algorithmically, we show that the standard paradigm for spectral clustering works. Moreover, it even works with the same gap assumption as required for the structural result.