As you may remember, my goal for reading this paper is a better understanding of the theories behing QSR and thus be able to make a better decision regarding what theory to use to represent my problem. I know, I haven’t talked about what “the problem” is yet, but suffice it to say I want to reason about some objects in space.
So far, I’ve concluded that I needed spatial qualitative reasoning (instead of qualitative reasoning); I have decided on my spatial entities (regions) and topology (to describe the relationships among my entities) and I have defined my basic relationships between my entities (binary relations). So let’s go on, what other factors do I need to consider? Read more »
Things are starting to get hot and heavy now. We will be seeing some mathematical definitions soon. To recap, so far we’ve decided which kinds of spatial objects (points, lines, regions) as well as what primitive non logical symbols to allow in our theory. We’ve settled on regions and (binary) relations.
The question is now, out of the possible set of relations out which one should you choose? Different sets have different advantages and disadvantages. Understanding these will help in choosing a proper theory for your problem. I might even find that my present course of action is not the best, maybe RCC-8 will not allow me to represent my problem properly.
Varzi showed that mereology is not sufficient by itself, but that integrating mereology and topology will. Hence we arrive at mereotopology. Given that topology already deals with spatial entities and as such is a necessary component, how should we work in these topology theories? Three general strategies are available:
- Generalize mereology by adding topological primitives.
- Topology is the primary theory and mereology is secondary.
- Mereology is primary theory and topology is secondary.
To paraphrase: “An important familiy of theories steam from the intuition that parthood and connection cannot be defined in terms of each other.”
For now, I’m going to take a detour and explore mereotopology in more detail to ensure that I fully understand these implications. Please subscribe to my feed to hear about my next adventure.
Are you considering using QSR to solve your research problem? Looking at “Qualitative Spatial Representation and Reasoning” (A. G. Cohn and J. Renz) and need help deciding if you want to spend the time reading the paper?
Deciding whether or not to use QSR to solve a particular problem is an important first step. Do you need to do spatio-temporal reasoning about objects in space? Are you looking for qualitative information, such as “Object A is close to Object B and partially covers Object C” or are you looking for detailed quantitative information, such as “Object A is 5 mm from Object B”? QSR deals with qualitative information.
Let’s assume that qualitative spatial reasoning will suffice for your research problem, how do you decide what theory to use. This paper gives you an overview of the current (2007) state of affairs in QSR and will help you figure out where to start your reading.
Read more »
Now that I have a better understanding of QSR and the theory behind it, I thought it would be a good idea to reread some articles. I often find, that I can gain greater understanding about research by re-reading articles. This particular article by Cohn and Renz part of a book on Knowledge Representation (KR) (A. G. Cohn and J. Renz, Qualitative Spatial Representation and Reasoning, in: F. van Hermelen, V. Lifschitz, B. Porter, eds., Handbook of Knowledge Representation, Elsevier, 551-596, 2008. ). I had already reread sections 1.1 and 1.2 when I thought of writing about it, so my thoughts on those sections will come at a later point.
Communication in wireless sensor networks uses the majority of a sensor’s limited energy. Using aggregation in wireless sensor network reduces the overall communication cost. Security in wireless sensor networks entails many different challenges. Traditional end-to-end security is not suitable for use with in-network aggregation. A corrupted sensor has access to the data and can falsify results. Additively homomorphic encryption allows for aggregation of encrypted values, with the result being the same as the result when unencrypted data was aggregated. Using public key cryptography, digital signatures can be used to achieve integrity. We propose a new algorithm using homomorphic encryption and additive digital signatures to achieve confidentiality, integrity and availability for in-network aggregation in wireless sensor networks.We prove that our digital signature algorithm which is based on the Elliptic Curve Digital Signature Algorithm (ECDSA) is as secure as ECDSA.
This paper has been accepted at IEEE WCNC 2009. Feel free to read it here and leave me your feedback.
Energy Constrained Clustering in Sensor Networks
Using partitioning in sensor networks to create clusters used for routing, data management and other protocols has been proven as a way to ensure scalability and to deal with shortcomings of sensor networks such as limited communication ranges and energy. Cluster heads use additional energy for their responsibilities and that burden needs to be carefully passed around. Many existing clustering protocols choose cluster heads either randomly or use nodes with the highest remaining energy. We introduce the energy constrained minimum dominating set (ECDS) problem to model the problem of optimally choosing cluster heads with energy constrains. We show its applicability to sensor networks and give an approximation algorithm of O(log n) for solving the ECDS problem. We propose a distributed algorithm for the constrained dominating set and experimentally show that it outperforms the greedy algorithm. We show experimentally that our heuristics are good approximations in random networks.
A paper has been submitted to IEEE MASS 2009. The current version of this paper is here. If you read it and have any corrections/suggestions for improvment, I would appreciate the feedback.
QSR, Research, bioinformatics | julia | 
March 23, 2009 10:58 | 
Comments (0) 
Subscribe