Bayesian Prediction for Game-structured Slotted ALOHA

최천원,Choi, Cheon-Won The Institute of Electronics and Information Engin 2012 電子工學會論文誌-TC (Telecommunications) Vol.41 No.2

With a game-theoretic view, p-persistence slotted ALOHA is structured as a non-cooperative game, in which a Nash equilibrium is sought to provide a value for the probability of attempting to deliver a packet. An expression of Nash equilibrium necessarily includes the number of active outer stations, which is hardly available in many practical applications. In this paper, we thus propose a Bayesian scheme of predicting the number of active outer stations prior to deciding whether to attempt to deliver a packet or not. Despite only requiring the minimal information that an outer station is genetically able to acquire by itself, the Bayesian scheme demonstrates the competitive predicting performance against a method which depends on heavy information. 게임 이론적 시각으로 p-persistence 슬롯화된 ALOHA를 비협력 게임으로 구성하고, 이 게임에서 Nash equilibrium을 구해 찾아 패킷 전달을 시도할 확률 값을 마련한다. Nash equilibrium의 수학적 표현에는 반드시 활성 변방국의 수가 포함되지만, 많은 실제 응용에서 이러한 수를 거의 알 수가 없다. 따라서 본 논문에서는 패킷의 전달을 시도할 지 결정하기에 앞서 활성 변방국의 수를 예측하는 Bayes 풍의 방식을 제안한다. 제안하는 Bayes 풍의 방식은 변방국이 스스로 자연스럽게 구할 수 있는 최소 정보만을 필요로 하지만 상당량의 정보에 의존하는 방식에 비해 경쟁력 있는 예측 성능을 보여 준다.

순차 번호의 다 패킷 할당 방식

최천원(Cheon Won Choi),신우철(Woo Cheol Shin),주재환(Jea Hwan Ju) 대한전자공학회 2001 대한전자공학회 학술대회 Vol.2001 No.11

무선 수동형 센서 망을 위한 경합형 MAC 방식의 최적 설계

최천원(Cheon Won Choi),서희원(Heewon Seo) 대한전자공학회 2016 전자공학회논문지 Vol.53 No.6

별도의 RF 소스가 센서 노드에게 에너지를 공급하는 무선 수동형 센서 망은 배터리 없이 영원히 동작할 수 있는 망이다. 그러나 영원한 수명에 대한 기대와 달리 무선 수동형 센서 망은 아직 에너지의 희소성, 에너지 수신과 데이타 전송의 동시불가성, 자원 활용의 비효율성 등 많은 문제를 안고 있다. 본 논문에서는 패킷 상실에는 관대하지만 패킷의 적시 전달을 요구하는 서비스를 제공하는 무선 수동형 센서 망을 다룬다. 이러한 망에서 여러 센서 노드들이 하나의 싱크 노드에게 패킷들을 전달하도록 현실적 제약을 인식하여 framed and slotted ALOHA에 기초한 경합형 MAC 방식을 고려한다. 이어서 지리적으로 흩어져있는 센서 노드들이 전송한 패킷들이 경로 손실을 겪어 결국 capture 현상이 빚어질 때 MAC 방식이 얻을 수 있는 망전체 throughput을 조사한다. 특히 두 센서 노드만이 망에 있을 때 망 전체 throughput의 정확한 공식을 closed form으로 도출한다. 마지막으로 설계 parameter들을 조절하여 최대의 망 전체 throughput을 취하도록 경합형 MAC 방식을 최적화한다. A wireless passive sensor network is a network which, by letting separate RF sources supply energy to sensor nodes, is able to live an eternal life without batteries. Against expectations about an eternal life, however, a wireless passive sensor network still has many problems; scarcity of energy, non-simultaneity of energy reception and data transmission and inefficiency in resource allocation. In this paper, we focus on a wireless passive sensor network providing a packet service which is tolerable to packet losses but requires timely delivery of packets. Perceiving the practical constraints, we then consider a contending-type MAC scheme, rooted in framed and slotted ALOHA, for supporting many sensor nodes to deliver packets to a sink node. Next, we investigate the network-wide throughput achieved by the MAC scheme when the packets transmitted by geographically scattered sensor nodes experience path losses hence capture phenomena. Especially, we derive an exact formula of network-wide throughput in a closed form when 2 sensor nodes reside in the network. By controlling design parameters, we finally optimize the contending-type MAC scheme as to attain the maximum network -wide throughput.

무선 수동형 센서 망을 위한 Slotted ALOHA 기반의 기본적인 MAC 방식

최천원(Cheon Won Choi),서희원(Heewon Seo) 대한전자공학회 2016 전자공학회논문지 Vol.53 No.4

무선 수동형 센서 망은 RF 소스가 센서 노드에게 에너지를 공급하여 적어도 이론적으로 배터리 없이 영원히 동작할 수 있는 망이다. 그러나 기술이 성숙하지 못하여 무선 수동형 센서 망은 아직 센서 노드에서 에너지의 희소성, 에너지 수신과 data 전송의 동시불가성, data 전송의 비효율성 등 많은 어려움을 안고 있다. 본 논문에서는 이러한 현실적 제약을 고려하여 여러 센서 노드가 하나의 싱크 노드에게 packet을 전달하기 위한 기본적인 MAC 방식을 제안한다. 수신한 에너지로 캐패시터를 충전하는 충전 구간과 싱크 노드와 통신하는 활동 구간이 번갈아 반복되는 시간 구조에 기초하여 제안하는 MAC방식은 활동 구간 동안 slotted ALOHA를 따라 싱크 노드에게 패킽을 전달한다. 일반적으로 경합형 방식은 throughput이 상대적으로 낮은 경향을 보인다. 따라서 모의 실험 방법을 이용하여 제안하는 MAC 방식의 throughput 성능을 다각도로 평가한다. 모의 실험 결과로부터 활동 구간의 길이를 적절히 설정하여 망 전체 throughput 성능을 높일 수 있음을 확인할 수 있다. A wireless passive sensor network is a network which, by letting RF sources supply energy to sensor nodes, is - at least theoretically - able to live an eternal life without batteries. Due to the technological immaturity, however, a wireless passive sensor network still has many difficulties; energy scarcity, non-simultaneity of energy reception and data transmission and inefficiency in data transmission occurring at sensor nodes. Considering such practical constraints, in this paper, we propose an elementary MAC scheme supporting many sensor nodes to deliver packets to a sink node. Based on a time structure in which a charging interval for charging capacitors by using received and an acting interval for communicating with a sink node are alternately repeated, the proposed MAC scheme delivers packets to a sink node according to slotted ALOHA. In general, a contention-type scheme tends to exhibit relatively low throughput. Thus, we multilaterally evaluate the throughput performance achieved by the proposed MAC scheme using a simulation method. Simulation results show that the network-wide throughput performance can be enhanced by properly setting the length of acting interval.

Optimal Time Structure for Tag Cognizance Scheme based on Framed and Slotted ALOHA in RFID Networks

최천원(Cheon Won Choi) 大韓電子工學會 2010 電子工學會論文誌-TC (Telecommunications) Vol.47 No.9

하나의 reader가 tag의 군집에 둘러싸여 있는 별 형태의 RFID 망을 고려한다. 이러한 RFID 망에서 reader는 tag에 저장된 정보를 얻기 전에 tag의 응답 간 충돌을 중재하면서 tag를 인식하여야 한다. 이러한 목적으로 tag가 응답하도록 프레임마다 정적으로 일정 수의 슬롯을 마련해 주는 프레임화 및 슬롯화된 ALOHA에 기반한 tag 인식 방식을 제안한다. 제안 방식의 인식성능을 평가하기 위해 주요 성능 척도로 인식 완료 확률과 기대 인식 완료 시간을 선정한다. 이어서 이러한 성능 척도를 계량적으로 계산할 수 있는 방법을 제안한다. 특히 tag가 많지 않은 경우 성능 척도를 closed form으로 도출한다. 다음 인식 시간에 대한 제약 하에서 인식 완료 확률을 최대화하거나 기대 인식 완료 시간을 최소화하는 최적의 시간 구조를 찾는 문제를 구성한다. 마지막으로 이러한 문제를 풀어서 프레임 당 tag가 응답하기 위한 슬롯의 최적 수를 구한다. 계량적 결과로부터 tag가 응답하기 위한 슬롯의 유한한 최적 수가 존재함을 확인한다. 또한 인식 완료 확률을 최대화하는 최적 슬롯 수는 인식 시간에 대한 제약이 약해지면서 기대 인식 완료 시간을 최소화하는 최적의 슬롯 수로 접근하는 경향을 보임을 관찰한다. Consider an RFID network configured as a star such that a single reader is surrounded by a crowd of tags. In the RFID network, prior to attaining the information stored at a tag, the reader must cognize the tags while arbitrating a collision among tags' responses. For this purpose, we present a tag cognizance scheme based on framed and slotted ALOHA, which statically provides a number of slots in each frame for the tags to respond. For the evaluation of the cognizance performance, we choose the cognizance completion probability and the expected cognizance completion time as key performance measures. Then, we present a method to numerically calculate the performance measures. Especially, for small numbers of tags, we derive them in a closed form. Next, we formulate a problem to find an optimal time structure which either maximizes the cognizance completion probability under a constraint on the cognizance time or minimizes the expected cognizance completion time. By solving the problem, we finally obtain an optimal number of slots per frame for the tags to respond. From numerical results, we confirm that there exist a finite optimal number of slots for the tags to respond. Also, we observe that the optimal number of slots maximizing the cognizance completion probability tends to approach to the optimal number of slots minimizing the expected cognizance completion time as the constraint on the cognizance time becomes loose.

Bayesian Prediction for Game-structured Slotted ALOHA

최천원(Cheon Won Choi) 대한전자공학회 2012 電子工學會論文誌-TC (Telecommunications) Vol.49 No.1

게임 이론적 시각으로 p-persistence 슬롯화된 ALOHA를 비협력 게임으로 구성하고, 이 게임에서 Nash equilibrium을 구해찾아 패킷 전달을 시도할 확률 값을 마련한다. Nash equilibrium의 수학적 표현에는 반드시 활성 변방국의 수가 포함되지만, 많은 실제 응용에서 이러한 수를 거의 알 수가 없다. 따라서 본 논문에서는 패킷의 전달을 시도할 지 결정하기에 앞서 활성 변방국의 수를 예측하는 Bayes 풍의 방식을 제안한다. 제안하는 Bayes 풍의 방식은 변방국이 스스로 자연스럽게 구할 수 있는 최소 정보만을 필요로 하지만 상당량의 정보에 의존하는 방식에 비해 경쟁력 있는 예측 성능을 보여 준다. With a game-theoretic view, p-persistence slotted ALOHA is structured as a non-cooperative game, in which a Nash equilibrium is sought to provide a value for the probability of attempting to deliver a packet. An expression of Nash equilibrium necessarily includes the number of active outer stations, which is hardly available in many practical applications. In this paper, we thus propose a Bayesian scheme of predicting the number of active outer stations prior to deciding whether to attempt to deliver a packet or not. Despite only requiring the minimal information that an outer station is genetically able to acquire by itself, the Bayesian scheme demonstrates the competitive predicting performance against a method which depends on heavy information.

중복도 기반 순차 번호 부여 방식의 지연 성능 분석

최천원(Cheon Won Choi),주재환(Jea Hwan Ju),신우철(Woo Cheol Shin),김동준(Dong Joon Kim) 한국통신학회 2002 한국통신학회 학술대회 및 강연회 Vol.2002 No.4

Snowball Scheme: An Alternative Admission Control Scheme for 3GPP ARQ

신우철,박진경,하준,최천원,Shin, Woo-Cheol,Park, Jin-Kyung,Ha, Jun,Choi, Cheon-Won The Institute of Electronics and Information Engin 2007 電子工學會論文誌-TC (Telecommunications) Vol.44 No.8

신뢰할 수 있는 데이타 전송을 위해 3GPP RLC 명세서는 window 기반의 수락 제어 방식이 곁들어진 selective-repeat ARQ 방식을 채택하였다. 이러한 3GPP ARQ는 selective-repeat ARQ 부류에 속하고 따라서 재정렬 문제가 내재한다. 길고 불규칙한 재정렬 시간은 throughput 및 지연 성능의 열화를 불러오고 재정렬 버퍼의 범람을 초래할 수 있다. 또한 지연과 상실에 모두 민감한 서비스를 위해 재정렬 시간은 반드시 조절되어야 한다. 이러한 재정렬의 위해를 인지하고 3GPP ARQ의 원래 수락 제어 방식을 대체하여 재정렬 버퍼의 점유량을 억제하기 위한 snowball 방식을 제안한다. Snowball 방식은 재정렬 버퍼에 남아있는 기존의 DATA PDU에 인접하지 않은 새 DATA PDU를 거부하는 특징을 갖는다. 이러한 고의적 거부는 재정렬 버퍼의 점유량을 낮추는 반면 throughput 및 지연 성능을 악화시킬 수 있다. 따라서 해석적 근사 방법을 개발하여 snowball 방식이 포화 점유량 및 throughput 비치는 영향을 조사한다. 또한 모의 실험 방법으로 실제 환경에서 최고 점유량, 정규화된 throughput 그리고 평균 지연을 평가한다. 모의 실험 결과로부터 3GPP ARQ의 원래 수락 제어 방식에 비해 snowball 방식은 점유 및 throughput 성능을 모두 고양할 수 있음을 확인한다. For provisioning reliable data transmission, the 3GPP RLC specification adopted a selective-repeat ARQ scheme assisted by a window-based admission control scheme. In the 3GPP ARQ, which is a member of the selective-repeat ARQ clan, inheres the reordering problem A long and irregular reordering time results in the degradation of throughput and delay performance, and may incur the overflow of the reordering buffer. Furthermore, the reordering time must be regulated to meet the requirements of some services which are loss-sensitive and delay-sensitive as well. Perceiving the reordering hazard, we propose an alternative, identified as snowball scheme, to the original admission control scheme of the 3GPP ARQ with aiming at deflating the occupancy of the reordering buffer. A unique feature of the snowball scheme is to reject a new DATA PDU if it is non-adjacent to any DATA PDU sojourning at the reordering buffer. Such an intentional rejection apparently reduces the occupancy of the reordering buffer while it may deteriorate the throughput and delay performance. Developing an analytical approximation method, we investigate the effect of snowball scheme on the saturated occupancy and throughput. Also, we, using a simulation method, evaluate the peak occupancy, normalized throughput and average delay in the practical environment. From the simulation results, we reveal that the snowball scheme is able to enhance occupancy performance as well as throughput performance compared with the original admission control scheme of the 3GPP ARQ.

무선 센서 망에서 MAC 방식을 위한 Bayes 중지 규칙

박진경(Jin Kyung Park),최천원(Cheon Won Choi) 대한전자공학회 2008 電子工學會論文誌-TC (Telecommunications) Vol.45 No.7

본 논문에서 줄기 노드는 mesh 토폴로지의 중추 망을 이루고 각 줄기 노드는 주변의 잎 노드와 함께 별 토폴로지의 부속망을 형성하는 무선 센서 망을 고려한다. 이러한 무선 센서 망에서 잎 노드로부터 줄기 노드로의 패킷 전달을 지원하는 MAC 방식을 설계할 때 반드시 다음 사항을 유념해야 한다. 첫째, 잎 노드는 일반적으로 배터리로부터 전력을 공급받는데 이러한 배터리를 교체하거나 충전하기가 어렵다. 둘째, 무선 센서 망은 흔히 주기적으로 데이타를 수집하여 갱신하기 위해 파송된다. 데이타 조각의 전달이 지연되면 싱크 노드의 데이타 처리가 지연되고 결과적으로 데이타 조각 자체를 폐기해야 할 수도 있다. 셋째, 무선 센서 망에서는 시그널링이 극도로 제약되고 복잡한 계산이 곤란하다. 이러한 점을 고려할 때 MAC 방식은 에너지를 절약하고 패킷 전달에서 적시성을 지원할 수 있어야 하며 동시에 단순하고 로버스트해야 한다. 본 논문에서는 무선 센서망의 MAC 방식으로 ALOHA의 수정판을 제안한다. ALOHA 제안 판은 ALOHA 원판의 단순함과 로버스트함을 보전하면서 매번 패킷의 전달을 시도하기에 앞서 잎 노드가 중지 혹은 계속을 결정하는 특징을 갖는다. 이러한 결정을 위해 본 논문에서는 Bayes 중지 규칙을 제안한다. Bayes 중지 규칙은 에너지, 적시성 그리고 throughput 손실이 반영된 Bayes 위험을 최소화하는 중지 규칙으로 잎 노드가 오직 전달 시도에 관한 선험적 지식과 자신의 전달 시도 경험에만 의존하여 중지 혹은 계속을 결정하므로 실용적이다. 계량적 결과로부터 Bayes 중지 규칙이 도입된 ALOHA 제안 판은 무선 센서 망의 열악한 환경에서 유용함을 확인한다. Consider a typical wireless sensor network in which stem nodes form the backbone network of mesh topology while each stem node together with leaf nodes in its vicinity forms a subnetwork of star topology. In such a wireless sensor network, we must heed the following when we design a MAC scheme supporting the packet delivery from a leaf node to a stem node. First, leaf nodes are usually battery-powered and it is difficult to change or recharge their batteries. Secondly, a wireless sensor network is often deployed to collect and update data periodically. Late delivery of a data segment by a sensor node causes the sink node to defer data processing and the data segment itself to be obsolete. Thirdly, extensive signaling is extremely limited and complex computation is hardly supported. Taking account of these facts, a MAC scheme must be able to save energy and support timeliness in packet delivery while being simple and robust as well. In this paper, we propose a version of ALOHA as a MAC scheme for a wireless sensor network. While conserving the simplicity and robustness of the original version of ALOHA, the proposed version of ALOHA possesses a distinctive feature that a sensor node decides between stop and continuation prior to each delivery attempt for a packet. Such a decision needs a stopping rule and we suggest a Bayes stopping rule. Note that a Bayes stopping rule minimizes the Bayes risk which reflects the energy, timeliness and throughput losses. Also, a Bayes stopping rule is practical since a sensor node makes a decision only using its own history of delivery attempt results and the prior information about the failure in delivery attempt. Numerical examples confirm that the proposed version of ALOHA employing a Bayes stopping rule is a useful MAC scheme in the severe environment of wireless sensor network.

Retrospective Maximum Likelihood Decision Rule for Tag Cognizance in RFID Networks

김준모,박진경,하준,서희원,최천원,Kim, Joon-Mo,Park, Jin-Kyung,Ha, Jun,Seo, Hee-Won,Choi, Cheon-Won The Institute of Electronics and Information Engin 2011 電子工學會論文誌-TC (Telecommunications) Vol.40 No.7

Tag가 reader 주변을 정상적으로 오가는 별 형태의 RFID 망을 고려한다. 이 RFID 망에서 주위의 tag를 인식하기 위해 동적으로 프레임에 속한 슬롯의 수를 결정하는 동적 프레임화 및 슬롯화된 ALOHA 기반의 방식을 제안한다. 이 tag 인식 방식은 특징적으로 주위의 tag의 기대 수를 추정하기 위해 R-회고풍 최대 우도 규칙이라 불리는 규칙을 채택하여 이전 R 개의 프레임에서 얻은 관찰 값을 tag의 기대 수의 우도를 최대화하는 과정에 사용한다. 모의 실험 결과는 회고의 깊이를 조금 늘려도 인식 성능이 유의할 만큼 향상됨을 보여준다. We consider an RFID network configured as a star in which tags stationarily move into and out of the vicinity of the reader. To cognize the neighboring tags in the RFID network, we propose a scheme based on dynamic framed and slotted ALOHA which determines the number of slots belonging to a frame in a dynamic fashion. The tag cognizance scheme distinctively employs a rule for estimating the expected number of neighboring tags, identified as R-retrospective maximum likelihood rule, where the observations attained in the R previous frames are used in maximizing the likelihood of expected number of tags. Simulation result shows that a slight increase in depth of retrospect is able to significantly improve the cognizance performance.