Efficient algorithms for beacon routing in polygons

In a paper by Biro et al. [7], a novel twist on guarding in art galleries is introduced. A beacon is a fixed point with an attraction pull that can move points within the polygon. Points move greedily to monotonically decrease their Euclidean distance to the beacon by moving straight towards the beacon or sliding on the edges of the polygon. The beacon attracts a point if the point eventually reaches the beacon. Unlike most variations of the art gallery problem, the beacon attraction has the intriguing property of being asymmetric, leading to separate definitions of attraction region and inverse attraction region. The attraction region of a beacon is the set of points that it attracts. For a given point in the polygon, the inverse attraction region is the set of beacon locations that can attract the point. We first study the characteristics of beacon attraction. We consider the quality of a "successful" beacon attraction and provide an upper bound of $\sqrt{2}$ on the ratio between the length of the beacon trajectory and the length of the geodesic distance in a simple polygon. In addition, we provide an example of a polygon with holes in which this ratio is unbounded. Next we consider the problem of computing the shortest beacon watchtower in a polygonal terrain and present an $O(n \log n)$ time algorithm to solve this problem. In doing this, we introduce $O(n \log n)$ time algorithms to compute the beacon kernel and the inverse beacon kernel in a monotone polygon. We also prove that $\Omega(n \log n)$ time is a lower bound for computing the beacon kernel of a monotone polygon. Finally, we study the inverse attraction region of a point in a simple polygon. We present algorithms to efficiently compute the inverse attraction region of a point for simple, monotone, and terrain polygons with respective time complexities $O(n^2)$, $O(n \log n)$ and $O(n)$. We show that the inverse attraction region of a point in a simple polygon has linear complexity and the problem of computing the inverse attraction region has a lower bound of $\Omega(n \log n)$ in monotone polygons and consequently in simple polygons.

Kernel machines for epilepsy diagnosis via EEG signal classification: A comparative study

Objective: We carry out a systematic assessment on a suite of kernel-based learning machines while coping with the task of epilepsy diagnosis through automatic electroencephalogram (EEG) signal classification. Methods and materials: The kernel machines investigated include the standard support vector machine (SVM), the least squares SVM, the Lagrangian SVM, the smooth SVM, the proximal SVM, and the relevance vector machine. An extensive series of experiments was conducted on publicly available data, whose clinical EEG recordings were obtained from five normal subjects and five epileptic patients. The performance levels delivered by the different kernel machines are contrasted in terms of the criteria of predictive accuracy, sensitivity to the kernel function/parameter value, and sensitivity to the type of features extracted from the signal. For this purpose, 26 values for the kernel parameter (radius) of two well-known kernel functions (namely. Gaussian and exponential radial basis functions) were considered as well as 21 types of features extracted from the EEG signal, including statistical values derived from the discrete wavelet transform, Lyapunov exponents, and combinations thereof. Results: We first quantitatively assess the impact of the choice of the wavelet basis on the quality of the features extracted. Four wavelet basis functions were considered in this study. Then, we provide the average accuracy (i.e., cross-validation error) values delivered by 252 kernel machine configurations; in particular, 40%/35% of the best-calibrated models of the standard and least squares SVMs reached 100% accuracy rate for the two kernel functions considered. Moreover, we show the sensitivity profiles exhibited by a large sample of the configurations whereby one can visually inspect their levels of sensitiveness to the type of feature and to the kernel function/parameter value. Conclusions: Overall, the results evidence that all kernel machines are competitive in terms of accuracy, with the standard and least squares SVMs prevailing more consistently. Moreover, the choice of the kernel function and parameter value as well as the choice of the feature extractor are critical decisions to be taken, albeit the choice of the wavelet family seems not to be so relevant. Also, the statistical values calculated over the Lyapunov exponents were good sources of signal representation, but not as informative as their wavelet counterparts. Finally, a typical sensitivity profile has emerged among all types of machines, involving some regions of stability separated by zones of sharp variation, with some kernel parameter values clearly associated with better accuracy rates (zones of optimality). (C) 2011 Elsevier B.V. All rights reserved.

Extensions of discrete triangular distributions and boundary bias in kernel estimation for discrete functions

Asymmetric discrete triangular distributions are introduced in order to extend the symmetric ones serving for discrete associated kernels in the nonparametric estimation for discrete functions. The extension from one to two orders around the mode provides a large family of discrete distributions having a finite support. Establishing a bridge between Dirac and discrete uniform distributions, some different shapes are also obtained and their properties are investigated. In particular, the mean and variance are pointed out. Applications to discrete kernel estimators are given with a solution to a boundary bias problem. (C) 2010 Elsevier B.V. All rights reserved.

Meat Quality of Lambs Fed on Palm Kernel Meal, a By-product of Biodiesel Production

This study aimed to establish the optimum level of palm kernel meal in the diet of Santa Ines lambs based on the sensorial characteristics and fatty acid profile of the meat. We used 32 lambs with a starting age of 4 to 6 months and mean weight of 22 2.75 kg, kept in individual stalls. The animals were fed with Tifton-85 hay and a concentrate mixed with 0.0, 6.5, 13.0 or 19.5% of palm kernel meal based on the dry mass of the complete diet. These levels formed the treatments. Confinement lasted 80 days and on the last day the animals were fasted and slaughtered. After slaughter, carcasses were weighed and sectioned longitudinally, along the median line, into two antimeres. Half-carcasses were then sliced between the 12th and 13th ribs to collect the loin (longissimus dorsi), which was used to determine the sensorial characteristics and fatty acid profile of the meat. For sensorial evaluation, samples of meat were given to 54 judges who evaluated the tenderness, juiciness, appearance, aroma and flavor of the meat using a hedonic scale. Fatty acids were determined by gas chromatography. The addition of palm kernel meal to the diet had no effect on the sensorial characteristics of meat juiciness, appearance, aroma or flavor. However, tenderness showed a quadratic relationship with the addition of the meal to the diet. The concentration of fatty acids C12:0, C14:0 and C16:0 increased with the addition of palm kernel meal, as did the sum of medium-chain fatty acids and the atherogenicity index. Up to of 19.5% of the diet of Santa Ines lambs can be made up of palm kernel meal without causing significant changes in sensorial characteristics. However, the fatty acid profile of the meat was altered.

Population balance modelling of granulation with a physically based coalescence kernel

It was previously published by the authors that granules can either coalesce through Type I (when granules coalesce by viscous dissipation in the surface liquid layer before their surfaces touch) or Type II (when granules are slowed to a halt during rebound, after their surfaces have made contact) (AIChE J. 46 (3) (2000) 529). Based on this coalescence mechanism, a new coalescence kernel for population balance modelling of granule growth is presented. The kernel is constant such that only collisions satisfying the conditions for one of the two coalescence types are successful. One constant rate is assigned to each type of coalescence and zero is for the case of rebound. As the conditions for Types I and II coalescence are dependent on granule and binder properties, the coalescence kernel is thus physically based. Simulation results of a variety of binder and granule materials show good agreement with experimental data. (C) 2002 Elsevier Science Ltd. All rights reserved.

The effect of water, brine and ethanol flotation on the quality and shelf life of macadamia kernels 2. Kernel pieces

Raw macadamia kernel pieces were immersed in water (specific gravity 1.00 g/cm(3)), brine (SG 1.02 g/cm(3)) or ethanol solution (SG 0.97 g/cm(3)) for 30 or 60 s, then re-dried to below 1.5% moisture (wet basis) and stored under vacuum for 0, 4 and 12 months. Flotation in water had no effect on the quality or shelf life of the kernel pieces over 12 months storage, as measured by sensory evaluation of the kernels and chemical analysis of the kernel oil. Immersion in a salt solution caused unacceptable changes in quality during storage, increasing as storage time increased. Flotation in dilute ethanol also caused unacceptable quality changes during storage. Therefore, only flotation of macadamia kernel pieces in water can be recommended for commercial operations. Microbiological concerns with such a process still need to be addressed.

Error bounds for low-rank approximations of the first exponential integral kernel

A hierarchical matrix is an efficient data-sparse representation of a matrix, especially useful for large dimensional problems. It consists of low-rank subblocks leading to low memory requirements as well as inexpensive computational costs. In this work, we discuss the use of the hierarchical matrix technique in the numerical solution of a large scale eigenvalue problem arising from a finite rank discretization of an integral operator. The operator is of convolution type, it is defined through the first exponential-integral function and, hence, it is weakly singular. We develop analytical expressions for the approximate degenerate kernels and deduce error upper bounds for these approximations. Some computational results illustrating the efficiency and robustness of the approach are presented.

Exploração da implementação actual de IPv6 no Kernel do Linux

A presente dissertação visa retratar a exploração do suporte do protocolo Internet versão seis (IPv6) no kernel do Linux, conjuntamente com a análise detalhada do estado da implementação dos diferentes aspectos em que se baseia o protocolo. O estudo incide na experimentação do funcionamento em geral do stack, a identificação de inconsistências deste em relação aos RFC’s respectivos, bem como a simulação laboratorial de cenários que reproduzam casos de utilização de cada uma das facilidades analisadas. O objectivo desta dissertação não é explicar o funcionamento do novo protocolo IPv6, mas antes, centrar-se essencialmente na exploração do IPv6 no kernel do Linux. Não é um documento para leigos em IPv6, no entanto, optou-se por desenvolver uma parte inicial onde é abordado o essencial do protocolo: a sua evolução até à aprovação e a sua especificação. Com base no estudo realizado, explora-se o suporte do IPv6 no Kernel do Linux, fazendo uma análise detalhada do estado de implementação dos diferentes aspectos em que se baseia o protocolo. Bem como a realização de testes de conformidade IPv6 em relação aos RFC’s.

Real-time scheduling of parallel tasks in the Linux Kernel

This paper proposes a global multiprocessor scheduling algorithm for the Linux kernel that combines the global EDF scheduler with a priority-aware work-stealing load balancing scheme, enabling parallel real-time tasks to be executed on more than one processor at a given time instant. We state that some priority inversion may actually be acceptable, provided it helps reduce contention, communication, synchronisation and coordination between parallel threads, while still guaranteeing the expected system’s predictability. Experimental results demonstrate the low scheduling overhead of the proposed approach comparatively to an existing real-time deadline-oriented scheduling class for the Linux kernel.

Enhancing the real-time capabilities of the Linux Kernel

The mainline Linux Kernel is not designed forhard real-time systems; it only fits the requirements of soft realtimesystems. In recent years, a kernel developer communityhas been working on the PREEMPT-RT patch. This patch(that aims to get a fully preemptible kernel) adds some realtimecapabilities to the Linux kernel. However, in terms ofscheduling policies, the real-time scheduling class of Linux islimited to the First-In-First-Out (SCHED_FIFO) and Round-Robin (SCHED_RR) scheduling policies. These scheduling policiesare however quite limited in terms of realtime performance.Therefore, in this paper, we report one importantcontribution for adding more advanced real-time capabilitiesto the Linux Kernel. Specifically, we describe modificationsto the (PREEMPT-RT patched) Linux kernel to supportreal-time slot-based task-splitting scheduling algorithms. Ourpreliminary evaluation shows that our implementation exhibitsa real-time performance that is superior to the schedulingpolicies provided by the current version of PREMPT-RT. Thisis a significant add-on to a widely adopted operating system.

TDBS: a time division beacon scheduling mechanism for ZigBee cluster-tree wireless sensor networks

Synchronization is a challenging and important issue for time-sensitive Wireless Sensor Networks (WSN) since it requires a mutual spatiotemporal coordination between the nodes. In that concern, the IEEE 802.15.4/ZigBee protocols embody promising technologies for WSNs, but are still ambiguous on how to efficiently build synchronized multiple-cluster networks, specifically for the case of cluster-tree topologies. In fact, the current IEEE 802.15.4/ZigBee specifications restrict the synchronization to beacon-enabled (by the generation of periodic beacon frames) star networks, while they support multi-hop networking in mesh topologies, but with no synchronization. Even though both specifications mention the possible use of cluster-tree topologies, which combine multi-hop and synchronization features, the description on how to effectively construct such a network topology is missing. This paper tackles this issue by unveiling the ambiguities regarding the use of the cluster-tree topology and proposing a synchronization mechanism based on Time Division Beacon Scheduling (TDBS) to build cluster-tree WSNs. In addition, we propose a methodology for efficiently managing duty-cycles in every cluster, ensuring the fairest use of bandwidth resources. The feasibility of the TDBS mechanism is clearly demonstrated through an experimental test-bed based on our open-source implementation of the IEEE 802.15.4/ZigBee protocols.

A time division beacon scheduling mechanism for IEEE 802.15.4/Zigbee cluster-tree wireless sensor networks

While the IEEE 802.15.4/Zigbee protocol stack is being considered as a promising technology for low-cost low-power Wireless Sensor Networks (WSNs), several issues in the standard specifications are still open. One of those ambiguous issues is how to build a synchronized multi-hop cluster-tree network, which is quite suitable for ensuring QoS support in WSNs. In fact, the current IEEE 802.15.4/Zigbee specifications restrict the synchronization in the beacon-enabled mode (by the generation of periodic beacon frames) to star-based networks, while it supports multi-hop networking using the peer-to-peer mesh topology, but with no synchronization. Even though both specifications mention the possible use of cluster-tree topologies, which combine multihop and synchronization features, the description on how to effectively construct such a network topology is missing. This paper tackles this problem, unveils the ambiguities regarding the use of the cluster-tree topology and proposes a synchronization mechanism based on Time Division Beacon Scheduling to construct cluster-tree WSNs. We also propose a methodology for an efficient duty cycle management in each router (cluster-head) of a cluster-tree WSN that ensures the fairest use of bandwidth resources. The feasibility of the proposal is clearly demonstrated through an experimental test bed based on our own implementation of the IEEE 802.15.4/Zigbee protocol.