무선방송환경에서 효율적인 데이터 스케줄링을 위한 R-HBI

Ⅰ. 서 론

최근 인터넷 전송 속도가 증가함에 따라 사용자들은 대용량의 질의를 요청하고 있다. 이로 인해 서버는 대용량의 질의를 처리하는데 많은 비용이 증가하는 추세이다. 그 중에서 위치 요소는 대부분의 애플리케이션에서 요구하는 필수 조건이라고 볼 수 있다. 사용자의 위치를 활용한 서비스는 여러 가지 존재할 수 있다. 예를 들면, 자신의 위치를 중심으로 맛있는 식당을 찾아달라고 요청한다면 서버는 사용자의 위치를 확인 후 식당에 대한 데이터베이스를 매칭한 후 이를 추천해줄 수 있다. 그 외에 다양한 애플리케이션에서 위치를 기반으로 서비스를 제공하고 있다.

서버는 클라이언트에게 만족스러운 서비스를 제공하기 위해서 사용자의 정확한 정보를 알고 있어야 최적화된 서비스를 제공할 수 있다. 반면에 사용자 입장에서 자신의 개인정보를 무단으로 활용할 수 있다는 심리로 인해 정확한 정보를 제공하는 것을 선호하지 않는다. 두 가지 조건을 만족하기란 쉽지 않다. 이를 개선하기 위해서 클로킹 영역을 활용한 질의요청이나 k-익명화 기법 등이 제안됐다. 그러나 서버 입장에서 검색해야 하는 영역이 증가하면 영역 내에 객체 또한 증가하기 때문에 서버가 처리해야 하는 비용은 증가할 수밖에 없다. 물론 인터넷 전송 속도 및 서버의 하드웨어적인 성능이 크게 개선되고 있으나 다수의 사용자들이 대용량의 질의를 동시에 또는 반복적으로 요청할 경우 서버의 처리과정에서 과부하가 발생할 수 있다[1]. 따라서 본 논문에서는 앞선 문제점을 개선하기 위하여 무선방송환경에서 효율적으로 데이터 스케줄링을 구성할 수 있는 Reduced Hierarchical Bitmap Index (R-HBI) 기법을 제안하고자 한다.

무선방송환경이란 서버가 클라이언트들에게 정보를 전송할 때 다운 링크로서 1대 다 전송방식을 의미한다[2]. 무선방송환경의 특징은 서버가 관리하는 통신 반경 내에서 불특정 다수에게 필요로 할 것이라고 예측한 공통 이슈(e.g., 올림픽, 인기 검색 등)를 기반으로 질의 결과를 제공하는 확장성을 가진다는 것이다. 그래서 클라이언트의 질의 요청 수와 상관없이 일정한 시간 내에 질의 요청자에게 질의의 결과를 일괄적으로 제공할 수 있다.

앞서 설명했듯이 무선방송환경에서 서버는 자신이 관리하는 통신 반경 내에 존재하는 불특정 다수에게 예측한 정보를 전송했다[3]. 그러나 서버 입장에서 예측한 모든 정보를 전송하기 때문에 통신 비용이 발생할 것이고, 질의 요청자들은 필요하지 않은 정보를 수신해야 하기 때문에 효율성이 저하된다. 따라서 본 논문에서는 새로운 시스템 모델을 제안한다. 그림 1은 제안기법의 시스템 모델을 보여주고 있다. 사용자들(User1, User2, ⋯, UserN)이 원하는 정보를 서버에게 요청하면 서버는 t₁~t_n 시간까지 취합된 질의 내용을 확인하고 중복되는 결과 값을 정리한 후 질의 결과 값을 사용자들에게 브로드캐스트한다. 서버는 특정시간 내에 취합된 정보를 통해 질의를 요청한 사용자들에게 필요한 객체만을 포함해서 전송한다.

Fig. 1.

System model

서버의 입장에선 유효한 객체들을 전송하기 위해서 질의자들의 요청을 주기적으로 확인해야 하지만 앞서 설명했던 특정 조건에서 요구기반으로 공간 질의를 처리하는 것보다 제안된 시스템 모델 환경이 서버의 작업 부하를 줄일 수 있다.

본 논문에서 주요 기여는 다음과 같다.

• - 서버는 질의자가 요청한 결과들을 취합 후 전송하기 때문에 중복되는 전송을 줄일 수 있다.
• - 제안된 시스템 모델에서 질의 요청 수가 많아질수록 질의처리 시간의 효율성이 증가한다.
• - R-HBI는 색인의 크기를 줄임으로서 전체 방송 주기가 감소하여 빠른 질의처리가 가능하다.

본 논문의 구성은 다음과 같다. 2장에서 관련연구를 소개하고, 3장에서 제안기법에 대한 시스템 모델 적용 예와 R-HBI의 색인구조를 설명한다. 4장에서는 성능평가를 통해 제안기법과 기존기법을 비교하고 제안기법의 우수한 점을 부각했고, 마지막으로 5장에서 결론을 내린다.

Ⅱ. 무선방송환경 및 질의처리 관련연구

일반적으로 모바일 환경에서 서버는 사용자에게 무선 전송 기술을 통해 서비스를 제공한다. 무선 기술 중 요구기반 방식은 서버와 사용자가 1 대 1로 통신하는 방식이다[4]. 일반적으로 애플리케이션은 요구기반 방식을 선호한다고 볼 수 있다[5]. 그러나 사용자들의 질의 요청이 갑자기 증가할 경우 병목현상이 발생하게 되어 질의 결과를 늦게 전송 받는 경우가 발생할 수 있다[6].

사용자와 사용자간의 통신으로 peer-to-peer 기법이 존재한다[7]. 사용자가 가지고 있는 정보를 인근 사용자에게 제공하는 기법으로 서버에서 탈피하기 위하여 제안됐으나 인근 사용자에게 원하는 정보를 제공받지 못할 경우 원하는 정보를 얻을 때까지 반복해야 하는 문제점을 내포하고 있다[8].

무선방송환경에서 공간질의 처리를 위한 다양한 색인 구조가 개발됐다. Hilbert-Curve Index (HCI)는 힐버트 커브(이하 HC) 기반으로 공간질의를 처리하는 기법이다[9]. HC의 장점은 맵 분할 후 그리드의 순서를 정할 때 인접한 객체들끼리 유사한 순서를 가지고 있다. 즉, 범위 질의나 Nearest Neighbor (NN)질의에 적합한 맵 구성이라고 할 수 있다. Euclidean space를 고려한 Broadcast Grid Index (BGI)기법은 무선 방송 환경에서 연속적인 공간 질의처리를 지원하는 기법이다[10]. BGI 기법은 HC를 이용하여 셀 단위로 분할한 후 객체를 배치한다. 생성된 그리드를 정렬하고 비트맵 기반의 더티 그리드 정보를 전송한다. 그러나 HC order의 차수(N)가 증가하는 만큼 색인 크기가 정비례해서 증가하는 점과 색인을 처음부터 끝까지 모두 청취해야 하는 문제점을 가지고 있다. 이를 개선하기 위하여 선택적 청취가 가능한 distributed Spatial Index (DSI)가 제안됐다[11].

그림 2는 DSI 색인 구조에 대한 형태를 보여주고 있다. 하나의 색인에는 객체에 대한 모든 정보를 하나로 합친 색인 구조가 아닌 2ⁿ으로 부분적인 색인 구조를 가진다(그림 2에서는 2³ 적용 예). DSI 기법의 장점은 작은 색인 정보로 객체 정보를 선택적으로 청취할 수 있다는 점이다. 그러나 한 개의 객체마다 부분적인 색인이 존재해야 한다는 것과 2ⁿ이 증가할 경우 색인의 크기가 커질 수 있다. 그리고 객체 1~3번(obj₁~obj₃) 사이에 중복되는 색인이 존재한다는 단점을 가지고 있다.

Fig. 2.

Index structure of DSI

Hierarchical Bitmap Index (HBI)는 계층적 색인 구조를 통해서 색인을 선택적으로 청취할 수 있는 기법이다[12]. 그림 3은 HBI의 색인 구조를 보여주고 있다. HC order 1은 최상위 계층으로 ‘1011’ 4bit로 구성된다. HC 오더를 이용한 분할은 4^N으로 증가하며 상위계층 1bit는 하위계층 4bit로 연결된다. HC order 1에서 2번째 비트가 ‘0’이기 때문에 HC order 2에서 하위 계층은 생성되지 않는다. 이를 통해 색인의 크기를 줄일 수 있는 기법이다. 객체의 수가 적을 경우 비트 ‘0’이 증가하기 때문에 색인의 크기를 대폭 줄일 수 있는 장점을 가지고 있다. 반면에 분할된 영역의 객체의 수가 많고, 밀집되어 있을 경우 BGI의 색인보다 커질 수 있는 가능성이 존재한다.

Fig. 3.

Index structure of HBI

최근 무선 방송 환경에서 색인의 크기를 줄이기 위한 압축된 비트맵이 제안됐다[13]. 그러나 개념적인 설명만 있을 뿐 정확한 색인의 구조나 실험적 결과가 부족하다. 이처럼, 객체 수가 증가할 때도 이를 개선할 수 있는 연구가 필요한 실정이다.

Ⅲ. Reduced Hierarchical Bitmap Index

이 장에서는 HBI를 기반으로 제안된 R-HBI를 설명한다. 설명에 앞서 3-1절에서 제안한 시스템 모델의 설명을 위해 몇 가지를 정의하고 기존의 시스템 모델을 비교한다. 3-2절에서는 R-HBI의 색인구조를 소개한다.

3-1 시스템 모델 적용 예

정의 1. HBI 색인구조는 HC 오더 차수에 따라 4^N으로 분할되며 너비 우선 검색(Breath first search)으로 스택이 구성된다.

정의 2. ● : 질의를 요청 받은 후보 결과 객체 (범위 기준); 서버는 질의자가 요청한 객체들을 구분해서 유효한 객체를 의미한다.

정의 3. ○: 후보 결과에서 제외된 객체; 서버가 관리하는 전체 객체들 중에서 질의 요청을 받지 않은 객체를 의미한다.

그림 4는 기존의 브로드캐스트 환경에서 서버가 질의자에게 객체를 전송하는 과정을 보여주고 있다. 서버는 사용자가 질의할 내용을 예측하고, 자신이 관리하는 음영된 범위 내에 존재하는 객체들을 브로드캐스트한다.

Fig. 4.

Example of query processing in an previous broadcast environment

서버 입장에서는 전송되는 객체들이 유효한 객체인지 아닌지 구분할 수 없고(정의 2, 3 참조), 불필요한 객체가 방송 주기 내에 삽입될 경우 전체적인 방송주기가 증가하기 때문에 질의자는 평균적으로 질의처리시간이 증가할 가능성이 존재한다.

그림 5는 서버가 일정한 시간동안 사용자의 질의를 취합하여 필요한 객체만을 전송하는 예를 보여주고 있다(그림 1 참조).

Fig. 5.

Example of query processing in a broadcast environment with a proposed system model

서버 내에 존재하는 객체들 중에서 질의자에게 요청받은 유효한 객체(●)를 선별한다. 유효하지 않은 객체(○)는 색인 구성 시 제외한다. 서버는 유효한 객체들을 전송하기 위해서 질의자들의 요청을 주기적으로 확인한다. 반면에 기존의 서버처럼 해당 범위에 존재하는 객체들을 모두 전송하지 않아도 되기 때문에 방송 주기를 줄일 수 있고, 이로 인하여 통신비용을 줄일 수 있다. 또한 질의자 입장에서도 방송주기가 줄어들었기 때문에 평균적으로 질의처리 시간을 줄일 수 있다.

3-2 R-HBI 색인구조

본 절에서는 추가적으로 색인의 크기를 줄이기 위한 R-HBI 구조를 제안한다. 그림 6은 R-HBI의 색인 구조를 보여주고 있다.

Fig. 6.

Index structure of R-HBI

그림 6에서 ①은 HBI의 상위 계층 비트를 의미한다. 맵 내에 분포된 객체의 위치에 따라 상위 계층의 비트의 구성이 달라질 수 있다. ②와 ④에 “00000000”는 R-HBI의 시작과 끝을 나타낸다. 정의 1에서 설명했듯이 맵을 4^N 등분으로 분할할 경우 HBI 색인 구조 상 반복되는 비트 ‘0’이 8개를 넘을 수 없다. 즉, ②와 ④ 사이에 원하는 정보를 삽입할 수 있다. 마지막으로 ③은 연속적으로 연결된 비트의 개수는 2진수로 표현한다.

서버의 R-HBI 생성 과정은 다음과 같다.

• 1 : 서버는 질의자에게 요청받은 객체들을 확인한다.
• 2 : 요청받은 객체를 기준으로 HC order N을 설정한다.
• 3 : HBI의 색인을 구성한다.
• 4 : 비트 ‘0’이 있을 경우 연속적인 비트 ‘1’은 4n배까지 설정한다.(색인의 선택적 청취 가능)
• 5 : 연속적인 비트 ‘1’이 R-HBI인 (2*N)+17bit보다 크다면 R-HBI로 변경한다.
• 6 : HBI의 마지막 색인까지 이를 반복한다.

만약, HC 오더 N이 4이고 256개의 그리드에 모든 객체가 존재한다고 가정한다면 그림 3에서 보았듯이 4¹+4²+4³+4⁴으로 HBI의 색인 크기는 340bit가 필요하다. 반면에 R-HBI를 이용하여 색인을 구성할 경우 ②+③+④는 총 25bit까지 줄일 수 있다. 또한 ③의 크기는 HBI가 연속적으로 출력되는 값은 최대 340개이므로 9비트로 표현이 가능하다.

Ⅳ. 성능평가

4-1 실험환경

본 절에서는 HBI와 R-HBI를 비교한다. 실험환경은 Intel i5-7400 CPU 3.0GHz, memory 8GB이고, visual studio 2019를 이용하여 실험을 실행했으며 10,000번을 반복해서 실험한 후 평균값으로 실험 결과로 나타냈다.

표 1에서는 실험환경에 필요한 변수를 다음과 같이 보여주고 있다. 객체의 수는 제안한 시스템 모델을 통해 요청된 객체의 수와 동일하다고 가정한다. 색인의 구조는 정의 1에 따라 너비 우선 검색으로 구성됐다.

Table 1.

Parameter

4-2 실험결과

그림 7은 HC order N이 증가함에 따라 색인의 크기가 변화하는 것을 보여주고 있다. HC order N이 증가할수록 분할되는 맵의 칸이 증가하게 되고 증가된 칸 수를 기준으로 80%만큼 임의로 객체를 배치했고, x축의 변수는 HC order N이 7, 8, 9로 맵의 분할 영역 증가시켰다. 그림 3에서 소개했듯이 HC order N이 증가할수록 계층의 깊이가 증가하기 때문에 색인의 크기가 증가하는 것을 확인할 수 있었다. 또한 HC order 7로 분할된 칸보다 8로 분할된 칸의 개수가 4⁷에서 4⁹만큼 증가하기 때문에 그래프가 급격하게 증가하는 것을 확인할 수 있었다. HBI와 R-HBI의 색인 크기를 비교한 결과 평균 15.2%의 성능이 개선된 것을 확인할 수 있었다.

Fig. 7.

Index size according to HC order N

그림 8은 객체 수에 따라 색인의 크기가 변화하는 것을 보여주고 있다. HC ordrer N은 8로 고정했으며 x축의 변수는 객체의 수로 HC order 8 * 70, 80, 90%로 설정했다. 앞서 언급했듯이 객체는 분할된 칸의 수를 기준으로 생성되며 위치는 임의로 배치된다. 임의로 배치된 객체의 위치에 따라 색인의 크기가 바뀔 수 있기 때문에 10,000번을 반복하여 색인의 평균 크기를 나타냈다. 실험결과 HBI는 객체 수가 증가할수록 색인크기가 증가하는 반면 R-HBI는 객체 수가 증가할수록 색인크기가 감소하는 것을 확인할 수 있었다. 그 이유는 3장에서 설명했듯이 HBI는 상위 계층의 색인 중 비트 ‘0’이 줄어들게 되면 이로 인해 하위 계층의 색인들의 증가하기 때문이다. 반면에서 R-HBI는 연속적인 비트 ‘1’이 많아지기 때문에 제안된 색인 구조를 통해 색인의 크기를 줄일 수 있었다. 실험결과 R-HBI가 HBI에 비해 평균 16.8% 색인의 크기를 줄인 것을 확인할 수 있었다.

Fig. 8.

Index size according to the number of objects

Ⅴ. 결 론

본 논문에서는 무선방송환경에서 효율적인 데이터스케줄링을 위한 색인 구조인 R-HBI와 새로운 시스템 모델을 제안했다. 기존 HBI는 객체의 수가 증가할수록 상위 계층에서 하위 계층으로 내려가는 색인의 크기가 증가하는 문제점을 지적하고 이를 개선할 수 있는 R-HBI를 제안했다. R-HBI는 연속적으로 비트 ‘1’이 조건만큼 반복될 경우 색인의 크기를 줄일 수 있는 기법이다. 실험 결과를 통해 객체의 수가 증가할수록 HBI의 색인의 크기는 증가하는 반면 R-HBI의 색인크기가 감소하는 것을 확인할 수 있었다. 향후 연구에서는 R-HBI를 이용하여 객체를 검색할 수 있는 범위질의 및 k-NN질의를 적용한 질의처리를 진행하고자 한다. 색인의 크기뿐만 아니라 객체의 데이터를 포함한 접근시간 및 청취시간을 비교하여 다양한 환경에서 제안기법이 적용 가능한지에 대한 연구하고자 한다.

Acknowledgments

본 연구는 서울한영대학교의 지원에 의한 연구임.

References

• X. Wang, H. Yang, and J. Song, “A VLC-based Robust ID Broadcasting Indoor Location System for Mobile Devices,” in Proceedings of 2016 IEEE International Symposium on Broadband Multimedia Systems and Broadcasting (BMSB), Nara, Japan, pp. 1-5, June 2016. [https://doi.org/10.1109/BMSB.2016.7521922]
• T. Imielinski, S. Viswanathan, and B. R. Badrinath, “Data on Air: Organization and Access,” IEEE Transactions on Knowledge and Data Engineering, Vol. 9, No. 3, pp. 353-372, May-June 1997. [https://doi.org/10.1109/69.599926]
• D. Song and K. Park, “A Partial Index for Distributed Broadcasting in Wireless Mobile Networks,” Information Sciences, Vol. 348, No. 20, pp. 142-152, June 2016. [https://doi.org/10.1016/j.ins.2016.02.011]
• F. Sallabi, G. Ditsa, H. El-Khatib, and S. A. Kobaisi, “On-demand Dynamic Location-Based Services Using Web Services,” in Proceedings of 2010 Fifth International Conference on Internet and Web Applications and Services, Barcelona, Spain, pp. 129-134, May 2010. [https://doi.org/10.1109/ICIW.2010.27]
• K. E. Defrawy and G. Tsudik, “Privacy-Preserving Location-Based On-Demand Routing in MANETs,” IEEE Journal on Selected Areas in Communications, Vol. 29, No. 10, pp. 1926-1934, December 2011. [https://doi.org/10.1109/JSAC.2011.111203]
• S. Ishida, S. Tagashira, Y. Arakawa, and A. Fukuda, “On-demand Indoor Location-Based Service Using Ad-hoc Wireless Positioning Network,” in Proceedings of 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security, and 2015 IEEE 12th International Conference on Embedded Software and Systems, New York: NY, pp. 1005-1013, August 2015. [https://doi.org/10.1109/HPCC-CSS-ICESS.2015.111]
• Y. Che, Q. Yang, and X. Hong, “A Dual-Active Spatial Cloaking Algorithm for Location Privacy Preserving in Mobile Peer-to-Peer Networks,” in Proceedings of 2012 IEEE Wireless Communications and Networking Conference (WCNC), Paris, France, pp. 2098-2102, April 2012. [https://doi.org/10.1109/WCNC.2012.6214137]
• H. Zuo, N. Jing, Y. Deng, and L. Chen, “CAN-QTree: A Distributed Spatial Index for Peer-to-Peer Networks,” in Proceedings of 2008 10th IEEE International Conference on High Performance Computing and Communications, Dalian, China, pp. 250-257, September 2018. [https://doi.org/10.1109/HPCC.2008.20]
• B. Zheng, W.-C. Lee, and D. L. Lee, “Spatial Queries in Wireless Broadcast Systems,” Wireless Networks, Vol. 10, No. 6, pp. 723-736, November 2004. [https://doi.org/10.1023/B:WINE.0000044031.03597.97]
• K. Mouratidis, S. Bakiras, and D. Papadias, “Continuous Monitoring of Spatial Queries in Wireless Broadcast Environments,” IEEE Transactions on Mobile Computing, Vol. 8, No. 10, pp. 1297-1311, October 2009. [https://doi.org/10.1109/TMC.2009.14]
• W.-C. Lee and B. Zheng, “DSI: A Fully Distributed Spatial Index for Location-Based Wireless Broadcast Services,” in Proceedings of 25th IEEE International Conference on Distributed Computing Systems (ICDCS’05), Columbus: OH, pp. 349-358, June 2005. [https://doi.org/10.1109/ICDCS.2005.26]
• D. Song and K. Park “A Hierarchical Bitmap-based Spatial Index use k-Nearest Neighbor Query Processing on the Wireless Broadcast Environment,” Journal of the Korean Society of Computer and Information, Vol. 17, No. 1, pp. 203-209, January 2012. [https://doi.org/10.9708/jksci.2012.17.1.203]
• D. Song, “Efficient Compression Bitmap in a Wireless Broadcasting Environment,” in Proceedings of 2022 Korea Digital Contents Society Summer Academic Conference, Jeju, pp. 135-136, July 2022.