Expander graph based key distribution mechanisms in wireless sensor networks

Secure communications between large number of sensor nodes that are randomly scattered over a hostile territory, necessitate efficient key distribution schemes. However, due to limited resources at sensor nodes such schemes cannot be based on post deployment computations. Instead, pairwise (symmetric) keys are required to be pre-distributed by assigning a list of keys, (a.k.a. key-chain), to each sensor node. If a pair of nodes does not have a common key after deployment then they must find a key-path with secured links. The objective is to minimize the keychain size while (i) maximizing pairwise key sharing probability and resilience, and (ii) minimizing average key-path length. This paper presents a deterministic key distribution scheme based on Expander Graphs. It shows how to map the parameters (e.g., degree, expansion, and diameter) of a Ramanujan Expander Graph to the desired properties of a key distribution scheme for a physical network topology.

Design and analysis of key management schemes for distributed wireless sensor networks

Secure communications in distributed Wireless Sensor Networks (WSN) operating under adversarial conditions necessitate efficient key management schemes. In the absence of a priori knowledge of post-deployment network configuration and due to limited resources at sensor nodes, key management schemes cannot be based on post-deployment computations. Instead, a list of keys, called a key-chain, is distributed to each sensor node before the deployment. For secure communication, either two nodes should have a key in common in their key-chains, or they should establish a key through a secure-path on which every link is secured with a key. We first provide a comparative survey of well known key management solutions for WSN. Probabilistic, deterministic and hybrid key management solutions are presented, and they are compared based on their security properties and re-source usage. We provide a taxonomy of solutions, and identify trade-offs in them to conclude that there is no one size-fits-all solution. Second, we design and analyze deterministic and hybrid techniques to distribute pair-wise keys to sensor nodes before the deployment. We present novel deterministic and hybrid approaches based on combinatorial design theory and graph theory for deciding how many and which keys to assign to each key-chain before the sensor network deployment. Performance and security of the proposed schemes are studied both analytically and computationally. Third, we address the key establishment problem in WSN which requires key agreement algorithms without authentication are executed over a secure-path. The length of the secure-path impacts the power consumption and the initialization delay for a WSN before it becomes operational. We formulate the key establishment problem as a constrained bi-objective optimization problem, break it into two sub-problems, and show that they are both NP-Hard and MAX-SNP-Hard. Having established inapproximability results, we focus on addressing the authentication problem that prevents key agreement algorithms to be used directly over a wireless link. We present a fully distributed algorithm where each pair of nodes can establish a key with authentication by using their neighbors as the witnesses.

A multi-hypothesis topological SLAM approach for loop closing on edge-ordered graphs

We present a method for topological SLAM that specifically targets loop closing for edge-ordered graphs. Instead of using a heuristic approach to accept or reject loop closing, we propose a probabilistically grounded multi-hypothesis technique that relies on the incremental construction of a map/state hypothesis tree. Loop closing is introduced automatically within the tree expansion, and likely hypotheses are chosen based on their posterior probability after a sequence of sensor measurements. Careful pruning of the hypothesis tree keeps the growing number of hypotheses under control and a recursive formulation reduces storage and computational costs. Experiments are used to validate the approach.

Data transformations in custom digital workflows : property graphs as a data model for user-defined mappings

This paper describes the use of property graphs for mapping data between AEC software tools, which are not linked by common data formats and/or other interoperability measures. The intention of introducing this in practice, education and research is to facilitate the use of diverse, non-integrated design and analysis applications by a variety of users who need to create customised digital workflows, including those who are not expert programmers. Data model types are examined by way of supporting the choice of directed, attributed, multi-relational graphs for such data transformation tasks. A brief exemplar design scenario is also presented to illustrate the concepts and methods proposed, and conclusions are drawn regarding the feasibility of this approach and directions for further research.

A rule-based hybrid method for anomaly detection in online-social-network graphs

Detecting anomalies in the online social network is a significant task as it assists in revealing the useful and interesting information about the user behavior on the network. This paper proposes a rule-based hybrid method using graph theory, Fuzzy clustering and Fuzzy rules for modeling user relationships inherent in online-social-network and for identifying anomalies. Fuzzy C-Means clustering is used to cluster the data and Fuzzy inference engine is used to generate rules based on the cluster behavior. The proposed method is able to achieve improved accuracy for identifying anomalies in comparison to existing methods.

Edge-weighting of gene expression graphs

In recent years, considerable research efforts have been directed to micro-array technologies and their role in providing simultaneous information on expression profiles for thousands of genes. These data, when subjected to clustering and classification procedures, can assist in identifying patterns and providing insight on biological processes. To understand the properties of complex gene expression datasets, graphical representations can be used. Intuitively, the data can be represented in terms of a bipartite graph, with weighted edges corresponding to gene-sample node couples in the dataset. Biologically meaningful subgraphs can be sought, but performance can be influenced both by the search algorithm, and, by the graph-weighting scheme and both merit rigorous investigation. In this paper, we focus on edge-weighting schemes for bipartite graphical representation of gene expression. Two novel methods are presented: the first is based on empirical evidence; the second on a geometric distribution. The schemes are compared for several real datasets, assessing efficiency of performance based on four essential properties: robustness to noise and missing values, discrimination, parameter influence on scheme efficiency and reusability. Recommendations and limitations are briefly discussed. Keywords: Edge-weighting; weighted graphs; gene expression; bi-clustering

Scaffolding understanding of tables and graphs

The literacy demands of tables and graphs are different from those of prose texts such as narrative. This paper draws from part of a qualitative case study which sought to investigate strategies that scaffold and enhance the teaching and learning of varied representations in text. As indicated in the paper, the method focused on the teaching and learning of tables and graphs with use of Freebody and Luke's (1990) four resources model from literacy education.

The role of microcomputer-based laboratory display in supporting the construction of new understanding in kinematics

Teachers' failure to utilise MBL activities more widely may be due to not recognising their capacity to transform the nature of laboratory activities to be more consistent with contemporary constructivist theories of learning. This research aimed to increase understanding of how MBL activities specifically designed to be consistent with a constructivist theory of learning support or constrain student construction of understanding. The first author conducted the research with his Year 11 physics class of 29 students. Dyads completed nine tasks relating to kinematics using a Predict-Observe-Explain format. Data sources included video and audio recordings of students and teacher during four 70-minute sessions, students' display graphs and written notes, semi-structured student interviews, and the teacher's journal. The study identifies the actors and describes the patterns of interactions in the MBL. Analysis of students' discourse and actions identified many instances where students' initial understanding of kinematics were mediated in multiple ways. Students invented numerous techniques for manipulating data in the service of their emerging understanding. The findings are presented as eight assertions. Recommendations are made for developing pedagogical strategies incorporating MBL activities which will likely catalyse student construction of understanding.

An instrument for assessing primary students’ knowledge of information graphics in mathematics

Information graphics have become increasingly important in representing, organising and analysing information in a technological age. In classroom contexts, information graphics are typically associated with graphs, maps and number lines. However, all students need to become competent with the broad range of graphics that they will encounter in mathematical situations. This paper provides a rationale for creating a test to measure students’ knowledge of graphics. This instrument can be used in mass testing and individual (in-depth) situations. Our analysis of the utility of this instrument informs policy and practice. The results provide an appreciation of the relative difficulty of different information graphics; and provide the capacity to benchmark information about students’ knowledge of graphics. The implications for practice include the need to support the development of students’ knowledge of graphics, the existence of gender differences, the role of cross-curriculum applications in learning about graphics, and the need to explicate the links among graphics.

National numeracy tests : a graphic tells a thousand words

Mandatory numeracy tests have become commonplace in many countries, heralding a new era in school assessment. New forms of accountability and an increased emphasis on national and international standards (and benchmarks) have the potential to reshape mathematics curricula. It is noteworthy that the mathematics items used in these tests are rich in graphics. Many of the items, for example, require students to have an understanding of information graphics (e.g., maps, charts and graphs) in order to solve the tasks. This investigation classifies mathematics items in Australia’s inaugural national numeracy tests and considers the effect such standardised testing will have on practice. It is argued that the design of mathematics items are more likely to be a reliable indication of student performance if graphical, linguistic and contextual components are considered both in isolation and in integrated ways as essential elements of task design.

Gender effects in orientation on primary students’ performance on items rich in graphics

This study investigated the longitudinal performance of 378 students who completed mathematics items rich in graphics. Specifically, this study explored student performance across axis (e.g., numbers lines), opposed-position (e.g., line and column graphs) and circular (e.g., pie charts) items over a three-year period (ages 9-11 years). The results of the study revealed significant performance differences in the favour of boys on graphics items that were represented in horizontal and vertical displays. There were no gender differences on items that were represented in a circular manner.

Characterising creativity : a holistic methodology for the assessment of creative works

This paper reports on the early stages of a design experiment in educational assessment that challenges the dichotomous legacy evident in many assessment activities. Combining social networking technologies with the sociology of education the paper proposes that assessment activities are best understood as a negotiable field of exchange. In this design experiment students, peers and experts engage in explicit, "front-end" assessment (Wyatt-Smith, 2008) to translate holistic judgments into institutional, and potentiality economic capital without adhering to long lists of pre-set criteria. This approach invites participants to use social networking technologies to judge creative works using scatter graphs, keywords and tag clouds. In doing so assessors will refine their evaluative expertise and negotiate the characteristics of creative works from which criteria will emerge (Sadler, 2008). The real-time advantages of web-based technologies will aggregate, externalise and democratise this transparent method of assessment for most, if not all, creative works that can be represented in a digital format.

Solving graphics tasks : gender differences in middle-school students

The capacity to solve tasks that contain high concentrations of visual-spatial information, including graphs, maps and diagrams, is becoming increasingly important in educational contexts as well as everyday life. This research examined gender differences in the performance of students solving graphics tasks from the Graphical Languages in Mathematics (GLIM) instrument that included number lines, graphs, maps and diagrams. The participants were 317 Australian students (169 males and 148 females) aged 9 to 12 years. Boys outperformed girls on graphical languages that required the interpretation of information represented on an axis and graphical languages that required movement between two- and three-dimensional representations (generally Map language).