Engineering Papers⌕ Search

Engineering topics

Kasiviswanathan, Shiva

Publications and source records attributed to Kasiviswanathan, Shiva.

Efficient Placement of Directional Antennas

Directional antenna is an technology for the proliferation of wireless networks. In centralized wireless network, wireless devices communicate through base stations. Directed antennas are placed on base stations and form a backbone of communication. The communication between base stations and wireless devices can be interfered due to a large number of wireless device. Methodically positioning and orienting directed antennas can help to reduce the interference while saving energy. An integer linear programming is developed for siting and directing antennas on multiple base stations, and this formulation can be extended to model non-overlapping channels. Through the integer programming formulation, optimal antenna positions can be used to analyze the performance of directed antennas with different parameters like the number base stations and the number of non-overlapping channels.

99 GENERAL AND MISCELLANEOUS↗

Explicit spatial scattering for load balancing in conservatively synchronized parallel discrete-event simulations

We re-examine the problem of load balancing in conservatively synchronized parallel, discrete-event simulations executed on high-performance computing clusters, focusing on simulations where computational and messaging load tend to be spatially clustered. Such domains are frequently characterized by the presence of geographic 'hot-spots' - regions that generate significantly more simulation events than others. Examples of such domains include simulation of urban regions, transportation networks and networks where interaction between entities is often constrained by physical proximity. Noting that in conservatively synchronized parallel simulations, the speed of execution of the simulation is determined by the slowest (i.e most heavily loaded) simulation process, we study different partitioning strategies in achieving equitable processor-load distribution in domains with spatially clustered load. In particular, we study the effectiveness of partitioning via spatial scattering to achieve optimal load balance. In this partitioning technique, nearby entities are explicitly assigned to different processors, thereby scattering the load across the cluster. This is motivated by two observations, namely, (i) since load is spatially clustered, spatial scattering should, intuitively, spread the load across the compute cluster, and (ii) in parallel simulations, equitable distribution of CPU load is a greater determinant of execution speed than message passing overhead. Through large-scale simulation experiments - both of abstracted and real simulation models - we observe that scatter partitioning, even with its greatly increased messaging overhead, significantly outperforms more conventional spatial partitioning techniques that seek to reduce messaging overhead. Further, even if hot-spots change over the course of the simulation, if the underlying feature of spatial clustering is retained, load continues to be balanced with spatial scattering leading us to the observation that spatial scattering can often obviate the need for dynamic load balancing.

97 MATHEMATICS AND COMPUTING↗

Matrix interdiction problem

In the matrix interdiction problem, a real-valued matrix and an integer k is given. The objective is to remove k columns such that the sum over all rows of the maximum entry in each row is minimized. This combinatorial problem is closely related to bipartite network interdiction problem which can be applied to prioritize the border checkpoints in order to minimize the probability that an adversary can successfully cross the border. After introducing the matrix interdiction problem, we will prove the problem is NP-hard, and even NP-hard to approximate with an additive n{gamma} factor for a fixed constant {gamma}. We also present an algorithm for this problem that achieves a factor of (n-k) mUltiplicative approximation ratio.

45 MILITARY TECHNOLOGY, WEAPONRY, AND NATIONAL DEF↗