OpenRaiser/Intern-Atlas huggingface dataset:
Unilateral Altruism in Network Routing Games with Atomic Players
Venue: arXiv cs.GT 2011
Year: 2011

We study a routing game in which one of the players unilaterally acts altruistically by taking into consideration the latency cost of other players as well as his own. By not playing selfishly, a player can not only improve the other players' equilibrium utility but also improve his own equilibrium utility. To quantify the effect, we define a metric called the Value of Unilateral Altruism (VoU) to be the ratio of the equilibrium utility of the altruistic user to the equilibrium utility he would have received in Nash equilibrium if he were selfish. We show by example that the VoU, in a game with nonlinear latency functions and atomic players, can be arbitrarily large. Since the Nash equilibrium social welfare of this example is arbitrarily far from social optimum, this example also has a Price of Anarchy (PoA) that is unbounded. The example is driven by there being a small number of players since the same example with non-atomic players yields a Nash equilibrium that is fully efficient.
A Key Establishment Scheme for Mobile Wireless Sensor Networks Using Post-Deployment Knowledge
Venue: arXiv cs.CR 2011
Year: 2011

Establishment of pairwise keys between sensor nodes in a sensor network is a difficult problem due to resource limitations of sensor nodes as well as vulnerability to physical captures of sensor nodes by the enemy. Public-key cryptosystems are not much suited for most resource-constrained sensor networks. Recently, elliptic curve cryptographic techniques show that public key cryptosystem is also feasible for resource-constrained sensor networks. However, most researchers accept that the symmetric key cryptosystems are viable options for resource-constrained sensor networks. In this paper, we first develop a basic principle to address the key pre-distribution problem in mobile sensor networks. Then, using this developed basic principle, we propose a scheme which takes the advantage of the post-deployment knowledge. Our scheme is a modified version of the key prioritization technique proposed by Liu and Ning. Our improved scheme provides reasonable network connectivity and security. Moreover, the proposed scheme works for any deployment topology.
Three-term Method and Dual Estimate on Static Problems of Continuum Bodies
Venue: arXiv cs.CE 2011
Year: 2011

This work aims to provide standard formulations for direct minimization approaches on various types of static problems of continuum mechanics. Particularly, form-finding problems of tension structures are discussed in the first half and the large deformation problems of continuum bodies are discussed in the last half. In the first half, as the standards of iterative direct minimization strategies, two types of simple recursive methods are presented, namely the two-term method and the three-term method. The dual estimate is also introduced as a powerful means of involving equally constraint conditions into minimization problems. As examples of direct minimization approaches on usual engineering issues, some form finding problems of tension structures which can be solved by the presented strategies are illustrated. Additionally, it is pointed out that while the two-term method sometimes becomes useless, the three-term method always provides remarkable rate of global convergence efficiency. Then, to show the potential ability of the three-term method, in the last part of this work, some principle of virtual works which usually appear in the continuum mechanics are approximated and discretized in a common manner, which are suitable to be solved by the three-term method. Finally, some large deformation analyses of continuum bodies which can be solved by the three-term method are presented.
Two-stage coordination multi-radio multi-channel mac protocol for wireless mesh networks
Venue: arXiv cs.NI 2011
Year: 2011

Within the wireless mesh network, a bottleneck problem arises as the number of concurrent traffic flows (NCTF) increases over a single common control channel, as it is for most conventional networks. To alleviate this problem, this paper proposes a two-stage coordination multi-radio multi-channel MAC (TSC-M2MAC) protocol that designates all available channels as both control channels and data channels in a time division manner through a two-stage coordination. At the first stage, a load balancing breadth-first-search-based vertex coloring algorithm for multi-radio conflict graph is proposed to intelligently allocate multiple control channels. At the second stage, a REQ/ACK/RES mechanism is proposed to realize dynamical channel allocation for data transmission. At this stage, the Channel-and-Radio Utilization Structure (CRUS) maintained by each node is able to alleviate the hidden nodes problem; also, the proposed adaptive adjustment algorithm for the Channel Negotiation and Allocation (CNA) sub-interval is able to cope with the variation of NCTF. In addition, we design a power saving mechanism for the TSC-M2MAC to decrease its energy consumption. Simulation results show that the proposed protocol is able to achieve higher throughput and lower end-to-end packet delay than conventional schemes. They also show that the TSC-M2MAC can achieve load balancing, save energy, and remain stable when the network becomes saturated.
Green: Towards a Pollution-Free Peer-to-Peer Content Sharing Service
Venue: arXiv cs.NI 2011
Year: 2011

Peer-to-Peer (P2P) content sharing systems are susceptible to the content pollution attack, in which attackers aggressively inject polluted contents into the systems to reduce the availability of authentic contents, thus decreasing the confidence of participating users. In this paper, we design a pollution-free P2P content sharing system, Green, by exploiting the inherent content-based information and the social-based reputation. In Green, a content provider (i.e., creator or sharer) publishes the information of his shared contents to a group of content maintainers self-organized in a security overlay for providing the mechanisms of redundancy and reliability, so that a content requestor can obtain and filter the information of his requested content from the associated maintainers. We employ a reputation model to help the requestor better identify the polluted contents, and then utilize the social (friend-related) information to enhance the effectiveness and efficiency of our reputation model. Now, the requestor could easily select an authentic content version for downloading. While downloading, each requestor performs a realtime integrity verification and takes prompt protection to handle the content pollution. To further improve the system performance, we devise a scalable probabilistic verification scheme. Green is broadly applicable for both structured and unstructured overlay applications, and moreover, it is able to defeat various kinds of content pollution attacks without incurring significant overhead on the participating users. The evaluation in massive-scale networks validates the success of Green against the content pollution.
Program slicing techniques and its applications
Venue: arXiv cs.SE 2011
Year: 2011

Program understanding is an important aspect in Software Maintenance and Reengineering. Understanding the program is related to execution behaviour and relationship of variable involved in the program. The task of finding all statements in a program that directly or indirectly influence the value for an occurrence of a variable gives the set of statements that can affect the value of a variable at some point in a program is called a program slice. Program slicing is a technique for extracting parts of computer programs by tracing the programs' control and data flow related to some data item. This technique is applicable in various areas such as debugging, program comprehension and understanding, program integration, cohesion measurement, re-engineering, maintenance, testing where it is useful to be able to focus on relevant parts of large programs. This paper focuses on the various slicing techniques (not limited to) like static slicing, quasi static slicing, dynamic slicing and conditional slicing. This paper also includes various methods in performing the slicing like forward slicing, backward slicing, syntactic slicing and semantic slicing. The slicing of a program is carried out using Java which is a object oriented programming language.
An Efficient Architecture for Information Retrieval in P2P Context Using Hypergraph
Venue: arXiv cs.DB 2011
Year: 2011

Peer-to-peer (P2P) Data-sharing systems now generate a significant portion of Internet traffic. P2P systems have emerged as an accepted way to share enormous volumes of data. Needs for widely distributed information systems supporting virtual organizations have given rise to a new category of P2P systems called schema-based. In such systems each peer is a database management system in itself, ex-posing its own schema. In such a setting, the main objective is the efficient search across peer databases by processing each incoming query without overly consuming bandwidth. The usability of these systems depends on successful techniques to find and retrieve data; however, efficient and effective routing of content-based queries is an emerging problem in P2P networks. This work was attended as an attempt to motivate the use of mining algorithms in the P2P context may improve the significantly the efficiency of such methods. Our proposed method based respectively on combination of clustering with hypergraphs. We use ECCLAT to build approximate clustering and discovering meaningful clusters with slight overlapping. We use an algorithm MTMINER to extract all minimal transversals of a hypergraph (clusters) for query routing. The set of clusters improves the robustness in queries routing mechanism and scalability in P2P Network. We compare the performance of our method with the baseline one considering the queries routing problem. Our experimental results prove that our proposed methods generate impressive levels of performance and scalability with with respect to important criteria such as response time, precision and recall.
Distributed Detection over Noisy Networks: Large Deviations Analysis
Venue: arXiv cs.IT 2011
Year: 2011

We study the large deviations performance of consensus+innovations distributed detection over noisy networks, where sensors at a time step k cooperate with immediate neighbors (consensus) and assimilate their new observations (innovation.) We show that, even under noisy communication, \emph{all sensors} can achieve exponential decay e^{-k C_{\mathrm{dis}}} of the detection error probability, even when certain (or most) sensors cannot detect the event of interest in isolation. We achieve this by designing a single time scale stochastic approximation type distributed detector with the optimal weight sequence {α_k}, by which sensors weigh their neighbors' messages. The optimal design of {α_k} balances the opposing effects of communication noise and information flow from neighbors: larger, slowly decaying α_k improves information flow but injects more communication noise. Further, we quantify the best achievable C_{\mathrm{dis}} as a function of the sensing signal and noise, communication noise, and network connectivity. Finally, we find a threshold on the communication noise power below which a sensor that can detect the event in isolation still improves its detection by cooperation through noisy links.
A Novel Header Matching Algorithm for Intrusion Detection Systems
Venue: arXiv cs.CR 2011
Year: 2011

The evolving necessity of the Internet increases the demand on the bandwidth. Therefore, this demand opens the doors for the hackers' community to develop new methods and techniques to gain control over networking systems. Hence, the intrusion detection systems (IDS) are insufficient to prevent/detect unauthorized access the network. Network Intrusion Detection System (NIDS) is one example that still suffers from performance degradation due the increase of the link speed in today's networks. In This paper we proposed a novel algorithm to detect the intruders, who's trying to gain access to the network using the packets header parameters such as; source/destination address, source/destination port, and protocol without the need to inspect each packet content looking for signatures/patterns. However, the "Packet Header Matching" algorithm enhances the overall speed of the matching process between the incoming packet headers against the rule set. We ran the proposed algorithm to proof the proposed concept in coping with the traffic arrival speeds and the various bandwidth demands. The achieved results were of significant enhancement of the overall performance in terms of detection speed.
Weak Dominance Drawings and Linear Extension Diameter
Venue: arXiv cs.DS 2011
Year: 2011

We introduce the problem of Weak Dominance Drawing for general directed acyclic graphs and we show the connection with the linear extension diameter of a partial order P. We present complexity results and bounds.
Gender Recognition Based on Sift Features
Venue: arXiv cs.AI 2011
Year: 2011

This paper proposes a robust approach for face detection and gender classification in color images. Previous researches about gender recognition suppose an expensive computational and time-consuming pre-processing step in order to alignment in which face images are aligned so that facial landmarks like eyes, nose, lips, chin are placed in uniform locations in image. In this paper, a novel technique based on mathematical analysis is represented in three stages that eliminates alignment step. First, a new color based face detection method is represented with a better result and more robustness in complex backgrounds. Next, the features which are invariant to affine transformations are extracted from each face using scale invariant feature transform (SIFT) method. To evaluate the performance of the proposed algorithm, experiments have been conducted by employing a SVM classifier on a database of face images which contains 500 images from distinct people with equal ratio of male and female.
Efficient Sum-Based Hierarchical Smoothing Under \ell_1-Norm
Venue: arXiv cs.DS 2011
Year: 2011

We introduce a new regression problem which we call the Sum-Based Hierarchical Smoothing problem. Given a directed acyclic graph and a non-negative value, called target value, for each vertex in the graph, we wish to find non-negative values for the vertices satisfying a certain constraint while minimizing the distance of these assigned values and the target values in the lp-norm. The constraint is that the value assigned to each vertex should be no less than the sum of the values assigned to its children. We motivate this problem with applications in information retrieval and web mining. While our problem can be solved in polynomial time using linear programming, given the input size in these applications such a solution might be too slow. We mainly study the \ell_1-norm case restricting the underlying graphs to rooted trees. For this case we provide an efficient algorithm, running in O(n^2) time. While the algorithm is purely combinatorial, its proof of correctness is an elegant use of linear programming duality. We believe that our approach may be applicable to similar problems, where comparable hierarchical constraints are involved, e.g. considering the average of the values assigned to the children of each vertex. While similar in flavor to other smoothing problems like Isotonic Regression (see for example [Angelov et al. SODA'06]), our problem is arguably richer and theoretically more challenging.
A Process Algebra for Supervisory Coordination
Venue: arXiv cs.LO 2011
Year: 2011

A supervisory controller controls and coordinates the behavior of different components of a complex machine by observing their discrete behaviour. Supervisory control theory studies automated synthesis of controller models, known as supervisors, based on formal models of the machine components and a formalization of the requirements. Subsequently, code generation can be used to implement this supervisor in software, on a PLC, or embedded microprocessor. In this article, we take a closer look at the control loop that couples the supervisory controller and the machine. We model both event-based and state-based observations using process algebra and bisimulation-based semantics. The main application area of supervisory control that we consider is coordination, referred to as supervisory coordination, and we give an academic and an industrial example, discussing the process-theoretic concepts employed.
Computing a Maximal Independent Set Using Beeps
Venue: arXiv cs.DC 2011
Year: 2011

We consider the problem of finding a maximal independent set (MIS) in the discrete beeping model. At each time, a node in the network can either beep (i.e., emit a signal) or be silent. Silent nodes can only differentiate between no neighbor beeping, or at least one neighbor beeping. This basic communication model relies only on carrier-sensing. Furthermore, we assume nothing about the underlying communication graph and allow nodes to wake up (and crash) arbitrarily. We show that if a polynomial upper bound on the size of the network n is known, then with high probability every node becomes stable in O(\log^3 n) time after it is woken up. To contrast this, we establish a polynomial lower bound when no a priori upper bound on the network size is known. This holds even in the much stronger model of local message broadcast with collision detection. Finally, if we assume nodes have access to synchronized clocks or we consider a somewhat restricted wake up, we can solve the MIS problem in O(\log^2 n) time without requiring an upper bound on the size of the network, thereby achieving the same bit complexity as Luby's MIS algorithm.
An Optimization-Based Model for Full-body Reaching Movements
Venue: arXiv cs.SY 2011
Year: 2011

Background The development of a simulation model of full body reaching tasks that can predict endeffector trajectories and joint excursions consistent with experimental data is a non-trivial task. Because of the kinematic redundancy inherent in these multi-joint tasks there are an infinite number of postures that could be adopted to complete them. By developing models to simulate full-body reaching movements in 3D space we can begin to explore cost functions that may be used by the central nervous system to plan and execute these movements. Methods A robust simulation model was developed using 1) graphic-based modeling tools to generate an inverse dynamics controller (SimMechanics), 2) controller parameterization methods, and 3) cost function criteria. An adaptive weight coefficient based on the final motor task error (i.e. distance between end-effector and target at the end of movement) was proposed to balance motor task error and physiological cost terms (e.g. joint power). The output of the simulation models using different cost controller functions based on motor task error or motor task error and various physiological cost terms (e.g. joint power, center of mass displacement) were compared to experimental data from 15 healthy participants performing full body reaching movements. Results In sum, the best fit to the experimental data was obtained by minimizing motor task error, joint power, and center of mass displacement. Simulation and experimental results demonstrated that the proposed method is effective for the simulation of large-scale human skeletal systems. Conclusions This method can reasonably predict the whole body reaching movements including final postures, joint power and movement of COM using simple algebraic calculations of inverse dynamics and forward kinematics.
Dynamic Index Coding for Wireless Broadcast Networks
Venue: arXiv cs.IT 2011
Year: 2011

We consider a wireless broadcast station that transmits packets to multiple users. The packet requests for each user may overlap, and some users may already have certain packets. This presents a problem of broadcasting in the presence of side information, and is a generalization of the well known (and unsolved) index coding problem of information theory. Rather than achieving the full capacity region, we develop a code-constrained capacity region, which restricts attention to a pre-specified set of coding actions. We develop a dynamic max-weight algorithm that allows for random packet arrivals and supports any traffic inside the code-constrained capacity region. Further, we provide a simple set of codes based on cycles in the underlying demand graph. We show these codes are optimal for a class of broadcast relay problems.
Mobile Agent as an Approach to Improve QoS in Vehicular Ad Hoc Network
Venue: arXiv cs.NI 2011
Year: 2011

Vehicular traffic is a foremost problem in modern cities. Huge amount of time and resources are wasted while traveling due to traffic congestion. With the introduction of sophisticated traffic management systems, such as those incorporating dynamic traffic assignments, more stringent demands are being placed upon the available real time traffic data. In this paper we have proposed mobile agent as a mechanism to handle the traffic problem on road. Mobile software agents can be used to provide the better QoS (Quality of Service) in vehicular ad hoc network to improve the safety application and driver comfort.
Embedded Model Control approach to robust control
Venue: arXiv cs.SY 2011
Year: 2011

Robust control design is mainly devoted to guarantee closed-loop stability of a model-based control law in presence of parametric and structural uncertainties. The control law is usually a complex feedback law which is derived from a (nonlinear) model, possibly complemented with some mathematical envelope of the model uncertainty. Stability may be guarantee with the help of some ignorance coefficients and restricting the feedback control effort with respect to the model-based design. Embedded Model Control shows that under certain conditions, the model-based control law must and can be kept intact under uncertainty, if the controllable dynamics is complemented by a suitable disturbance dynamics capable of real-time encoding the different uncertainties affecting the 'embedded model', i.e. the model which is both the design source and the core of the control unit. To be real-time updated the disturbance state is driven by an unpredictable input vector, called noise, which can be only estimated from the model error. The uncertainty (or plant)-based design concerns the noise estimator, as the model error may convey into the embedded model uncertainty components (parametric, cross-coupling, neglected dynamics) which are command-dependent and thus prone to destabilize the controlled plant. Separation of the components into the low and high frequency domain by the noise estimator allows to recover and guarantee stability, and to cancel the low frequency ones from the plant. Among the advantages, control algorithms are neatly and univocally related to the embedded model, the embedded model provides a real-time image of the plant, all control gains are tuned by fixing closed-loop eigenvalues. Last but not least, the resulting control unit has modular structure and algorithms, thus facilitating coding. A simulated case study helps to understand the key assets of the methodology.
An Abstract Semantics for Inference of Types and Effects in a Multi-Tier Web Language
Venue: arXiv cs.LO 2011
Year: 2011

Types-and-effects are type systems, which allow one to express general semantic properties and to statically reason about program's execution. They have been widely exploited to specify static analyses, for example to track computational side effects, exceptions and communications in concurrent programs. In this paper we adopt abstract interpretation techniques to reconstruct (following the Cousot's methodology) a types-and-effects system developed to handle security problems of a multi-tier web language. Our reconstruction allows us to show that this types-and-effects system is not sound with respect to the semantics of the language. In addition, we correct the soundness issues in the analysis and systematically construct a correct analyser.