Routing for Enhancing Source-Location Privacy in Wireless Sensor Networks of Multiple Assets

Yeonghwan Tscha 한국통신학회 2009 Journal of communications and networks Vol.11 No.6

In wireless sensor networks, a node that reports information gathered from adjacent assets should relay packets appropriately so that its location context is kept private, and thereby helping ensure the security of the assets that are being monitored. Unfortunately, existing routing methods that counter the local eavesdropping-based tracing deal with a single asset, and most of them suffer from the packet-delivery latency as they prefer to take a separate path of many hops for each packet being sent. In this paper, we propose a routing method, greedy perimeter stateless routing-based source-location privacy with crew size w (GSLP-w), that enhances location privacy of the packet-originating node (i.e., active source) in the presence of multiple assets. GSLP-w is a hybrid method, in which the next-hop node is chosen in one of four modes, namely greedy, random, perimeter, and retreat modes. Random forwarding brings the path diversity, while greedy forwarding refrains from taking an excessively long path and leads to convergence to the destination. Perimeter routing makes detours that avoid the nodes near assets so that they cannot be located by an adversary tracing up the route path. We study the performance of GSLP-w with respect to crew size w (the number of packets being sent per path) and the number of sources. GSLP-w is compared with phantom routing-single path (PR-SP), which is a notable routing method for source-location privacy and our simulation results show that improvements from the point of the ratio of safety period and delivery latency become significant as the number of source nodes increases.

On Sensor Network Routing for Cloaking Source Location Against Packet-Tracing

Yeonghwan Tscha 한국통신학회 2009 韓國通信學會論文誌 Vol.34 No.3

Most of existing routing methods in wireless sensor networks to counter the local eavesdropping-based packet-tracing deal with a single asset and suffer from the packet-delivery latency as they prefer to take a separate path of many hops for each packet being sent. Recently, the author proposed a routing method, GSLP-w(GPSR-based Source-Location Privacy with crew size w), that enhances location privacy of the packet-originating node(i.e., active source) in the presence of multiple assets, yet taking a path of not too long. In this paper, we present a refined routing(i.e., next-hop selection) procedure of it and empirically study privacy strength and delivery latency with varying the crew size w(i.e., the number of packets being sent per path). It turns out that GSLP-w offers the best privacy strength when the number of packets being sent per path is randomly chosen from the range [1,hs-b/4] and that further improvements on the privacy are achieved by increasing the random walk length TTLrw or the probability prw that goes into random walk(where, hs-b is the number of hops of the shortest path between packet-originating node s and sink b).

광 베니언 - 형 교환 망에서의 누화를 회피하기 위한 교환소자를 달리하는 멀티캐스트 스케줄링 (제1부) : 누화 관계의 그래프 이론적 분석

차영환(Yeonghwan Tscha) 한국정보과학회 2001 정보과학회논문지 : 정보통신 Vol.28 No.3

본 논문에서는 방향성 커플러를 이용하여 구성한 광 베니언-형 교환 망에 있어 교환소자를 달리하는 멀티캐스팅의 스케줄링을 고려한다. 임의의 주어진 시각에 최대한 하나의 접속만이 각각의 교환소자를 점유하기 때문에 블럭킹은 물론 누화가 발생하지 않도록 보장된다. 이러한 멀티캐스팅에서는 대개 수차례에 걸친 라우팅이 수반되므로 라우팅 횟수(즉, 스케줄링 길이)를 최소한으로 하는 것이 바람직하다. 먼저 일-대-다 접속 능력을 제공하는 광 베니언-형 망에서 접속들이 동일한 교환소자를 경유(즉, 누화를 유발)하기 위한 필요충분 조건을 제시한다. 멀티캐스트 접속을 일정한 부분접속들로 분할하는 규칙을 정의하고, 부분접속들간의 누화 관계를 그래프로 표현한다. 최악의 경우의 누화를 분석하기 위해 그래프차수의 상한을 제시한다. 후속 논문(제2부)[14]에서는 스케줄링 알고리즘과 스케줄링 길이의 상한을 고찰하고, 관련 연구결과와의 상세한 비교를 다룬다. In this paper, we consider the scheduling of SE(switching element)-disjoint multicasting in photonic Banyan-type switching networks constructed with directional couplers. This ensures that at most, one connection holds each SE in a given time thus, neither crosstalk nor blocking will arise in the network. Such multicasting usually takes several routing rounds hence, it is desirable to keep the number of rounds(i.e., scheduling length) to a minimum. We first present the necessary and sufficient condition for connections to pass through a common SE(i.e., make crosstalk) in the photonic Banyan-type networks capable of supporting one-to-many connections. With definition of uniquely splitting a multicast connection into distinct subconnections, the crosstalk relationship of a set of connections is represented by a graph model. In order to analyze the worst case crosstalk we characterize the upper bound on the degree of the graph. The successor paper(Part II)[14] is devoted to the scheduling algorithm and the upper bound on the scheduling length. Comparison with related results is made in detail.

방향성 안테나에 기반을 둔 이동 애드 혹 네트워크에서의 대체 경로 설정

차영환(Yeonghwan Tscha) 한국멀티미디어학회 2007 멀티미디어학회논문지 Vol.10 No.9

방향성 안테나에 기반을 둔 애드 혹 네트워크를 위한 신뢰성 있는 브로드캐스팅 기법

차영환(Yeonghwan Tscha) 한국정보기술학회 2008 한국정보기술학회논문지 Vol.6 No.6

센서 네트워크에서 낮은 전달 지연으로 근원지 위치 기밀을 강화하는 라우팅

차영환(Yeonghwan Tscha) 한국통신학회 2008 韓國通信學會論文誌 Vol.33 No.8B

센서 네트워크에 있어서 정보 전송 노드인 근원지의 위치를 악의적 추적자로부터 보호하기 위해 길이가 긴 경로를 통해 단일 메시지를 전송하는 라우팅에서는 전달 지연이 길어지는 단점이 있다. 본 논문에서는 전송 메시지가 사전에 주어진 경우, 근원지 위치를 보호하면서 최소 비용의 단일 경로를 이용하여 이들을 목적지로 전달하는 문제는 NP-complete 임을 보인다. 이러한 양 극단의 절충 방안이라 할 수 있는 경로 당 ω개의 메시지들을 전송하도록 하여 근원지의 위치 보호 능력을 높이면서도 전달 지연을 저감시키는 라우팅 프로토콜 GSLP-ω (GPSR-based Source Location Privacy with crew size ω)를 제안한다. 평가 기준으로는 목적지와의 최단 경로의 홉 수를 기준으로 정규 안전 기간(NSP: Normalized Safety Period)과 정규 전달 지연(NDL: Normalized Delivery Latency)을 고려한다. 평균 차수(degree)가 8인 노드 50,000개로 구성되는 네트워크 토폴로지 100개를 생성하여 측정한 결과 제안된 GSLP-ω는 GSLP-ω의 초기 버전인 GSLP와 기존의 대표적인 근원지 위치 보호 라우팅 프로토콜인 PR-SP(Phantom Routing - Single Path)보다 더 높은 안전 기간을 보였다. 전달 지연에서는 GSLP-ω가 PR-SP보다 높으나 GSLP 보다는 낮은 것으로 나타났다. Most of routing schemes that protect the source's location from a malicious attacker usually make use of a path of a long length per message for the sake of lengthening the safety period. The biggest problem to such approaches is taking a very long latency in transferring messages to the destination. In this paper we show the problem to find the least-cost single path that is enough to keep the source-location always secure from the attacker, provided that it is used for the delivery of a set of messages given in priori, is NP-complete. Consequently we propose a routing protocol GSLP-w(GPSR-based Source-Location Privacy with crew size ω) that is a trade-off between two extreme approaches. The advantage of GSLP-ω lies in its enhanced safety period for the source and its lowered delivery latency in messaging. We consider NSP(Normalized Sefety Period) and NDL(Normalized Delivery Latency), measured in terms of the least number of hops to the destination, to achieve tangible interpretation of the results. We ran a simulation to confirm our claim by generating 100 topologies of 50,000 nodes with the average number of neighbors being 8. The results show that GSLP-ω provides more enhanced NSP compared to other protocols GSLP, an earlier version of GSLP-ω, and PR-SP(Phantom Routing - Single Path), the most notable existing protocol for the source-location privacy, and less NDL than that of GSLP but more than that of PR-SP.

근원지 위치 보호 라우팅 기법 GSLP의 확장에 관한 연구

차영환(Yeonghwan Tscha) 한국정보기술학회 2012 한국정보기술학회논문지 Vol.10 No.1

Multi - Log₂N 다중접속 망의 넌블럭킹 조건에 관한 새로운 결과

차영환(Yeonghwan Tscha),이균하(Kyoon Ha Lee) 한국정보과학회 1992 한국정보과학회 학술발표논문집 Vol.19 No.1

본 논문에서는 그 동안 미해결 문제(open problem)들[1-4]로 남아있던 Multi-Log₂N 다중접속 망의 Rearrangeable 넌블럭킹 조건과 Strictly 넌블럭킹 조건을 제시 하였다. 기존의 예측[1,2]과 달리 Multi-Log₂N 다중접속 망의 넌블럭킹 조건들은 Multi-Log₂N 일대일접속 망의 넌블럭킹 조건들과 일치한다는 흥미로운 결과를 얻었다. 본 논문에서 규명된 넌블럭킹 조건들은 물론 SIS(Subconnection-Intersection Set) 정규화된 SIS(Normalized SIS), SIG(Subconnection-Intersection Graph) 및 UMSR(Unified Multiconnection-Segmenting Rule)등은 다중접속 광대역 스위치의 개발은 물론 하나 또는 2개 이상의 스위치 망을 복수개 이용하는 다양한 구조의 다중접속 스위치 망에 있어 유용성있는 기본 자료로 활용될 수 있을 것으로 판단된다.

광 베니언 - 유형 교환 망에서의 누화를 회피하기 위한 교환소자를 달리하는 멀티캐스트 스케줄링(제2부) : 스케줄링 길이 및 넌블럭킹 특성

차영환(Yeonghwan Tscha) 한국정보과학회 2001 정보과학회논문지 : 정보통신 Vol.28 No.4

선행 논문(제1부)[13]에서는 광 베니언-형 교환 망에 있어 누화를 야기하는 멀티캐스트 접속들간의 관계를 그래프로 표현하고, 해당 그래프의 차수의 상한을 제시하였다. 본 논문(제2부)에서는 교환소자를 달리하는 멀티캐스팅의 스케줄링에서의 라우팅 횟수 즉, 스케줄링 길이에 대해 다룬다. 최적의 스케줄링 길이를 구하는 문제는 NP-complete이므로 최적 길이의 상한의 두 배이내의 길이를 제공하는 근사 알고리즘을 제시한다. 아울러, 링크를 달리하는(즉, 넌블럭킹) 멀티캐스팅에 관한 스케줄링 길이를 고찰한다. 얻어진 스케줄링 길이 하에서 다양한 넌블럭킹 베니언-형 멀티캐스팅 망들을 규명한다. In our predecessor paper(Part I)[13], we introduced a graph that represents the crosstalk relationship among multicast connections in the photonic Banyan-type switching network, and found the upper bound on the degree of it. In this paper(Part II), we consider the number of routing rounds(i.e., scheduling length) required for SE(switching element)-disjoint multicasting in photonic Banyan-type switching networks. Unfortunately, the problem to find an optimal scheduling length is NP-complete thus, we propose an approximation algorithm that gives its scheduling length is always within double of the upper bound on the optimal length. We also study the scheduling length on the link-disjoint(i.e., nonblocking) multicasting. Various nonblocking Banyan-type multicasting networks are found under the scheduling lengths.

이동 애드 - 혹 네트워크를 위한 신뢰성 있는 동적 소스 라우팅 프로토콜

임화정(HwaJung Lim),차영환(YeongHwan Tscha) 한국정보과학회 2003 한국정보과학회 학술발표논문집 Vol.30 No.2Ⅲ

본 논문에서는 이동 애드-혹 네트워크(mobile ad-hoc networks)의 대표적인 경로구축 방법인 DSR(dynamic source routing)을 확장된 R-DSR(robust DSR)을 제안한다. 제안된 R-DSR에서는 기존의 단일 경로 상의 2-홉 간격의 모든 노드들이 대체 노드를 경유하여 복수 개의 라우팅 경로를 유지하도록 구성되기 때문에, 경로 상의 일부 노드들이 이동하더라도 경로가 유지될 확률이 높아 메시지 전달률이 향상된다. 수학적 분석을 통하여 관련 연구 중 가장 우수한 것으로 알려진 Das의 다중경로 프로토콜보다 더 높은 라우팅 경로 유지 확률을 나타냄을 보였다. 아울러, 대체경로의 위상적 특성에 의한 빠른 대체경로로의 복구도 가능하다는 결론을 얻었다.