Sándor Plósz

István Moldován

László Kántor

Tuan Anh Trinh
email: trinh@tmit.bme.hulkantor@aitia.ai

Characterization of Power-Aware Reconfiguration in FPGA-Based Networking Hardware

Keywords: Networking, hardware, reconfiguration, power optimization, FPGA

Dynamic reconfiguration of FPGA in the networking hardware device is a feature which can be exploited in numerous networking applications. By reconfiguration we can change either the functionality, performance or even energy consumption of an area on the FPGA. This property can be exploited in a number of ways, in different application areas. However, the question of performance and power consumption trade-off in these situations is still an open issue. In this paper we address this issue by investigating different use cases and introducing a general approach of algorithmic optimization of power consumption based on dynamic reconfiguration. Our findings are supported by extensive SystemC/TLM hardware level simulations.

Introduction

Handling high speed traffic requires high performance, which is a term quite often competing with low power consumption. The challenge of high-performance, yet low-power systems is to find an optimal balance of shutting down resources that are not in use. To shut down and wake them up when needed may not result in lower cost (power) comparing to not even shutting them down in the first place. Optimization for low power with high performance is a key requirement during the definition and design of state-of-the-art communication systems. With the ever-increasing demand of faster data transmission currently the 10 Gigabit per second Ethernet (10 GbE) service is becoming a requirement on the provider side network. When data arrives to a system at 10 Gigabit per second rate, the time is very limited for analysing or handling it. To optimize data processing at many different levels, tasks should be distributed and made parallel.

The Scalopes C-Board was created to overcome these issues featuring high processing power but also efficient resource usage. For high-speed packet processing FPGAs are used and the board was extended with a general-purpose processor for management functions. The four Virtex-5 FPGAs used in the Scalopes C-board support dynamic partial reconfiguration. This feature allows multiple design modules to time-share physical resources. Partially reconfigurable modules can be swapped on-the-fly, even while the base design continues to operate. The FPGA technology helps building a multi-purpose hardware, a simple firmware switch enables switching between applications much faster than if we needed to switch the whole device.

In this paper we investigate the applicability of networking system reconfiguration. We use a simulation tool to investigate the performance trade-off and the usefulness of reconfigurability according to different metrics.

In Section 2 we introduce what dynamic, partial reconfiguration is really about, how it works and how this feature can be exploited in communication systems. In Section 3 we present different algorithms for this use-case and describe the parameters which affect their operation. In Section 4.1 the realization of the simulation scenarios are presented along with the simulation environment. Results of the simulations are presented in Section 4.2. Finally Section 5 concludes the paper.

Dynamic, partial reconfiguration

Reconfiguration is a mechanism that makes it possible to change the configuration of a reconfigurable hardware, such as an FPGA. The reconfiguration can be full or partial: during partial reconfiguration only a part of the FPGA is reconfigured while the other part remains unchanged. This method supposes well defined interface points to the unchanged part. Dynamic reconfiguration means that partial reconfigurations are done on-the-fly, triggered by events related to the operation of the whole system. This method requires sophisticated management of interface points in the system to preserve process states. Dynamic reconfiguration implies that reconfiguration should be fast and should have limited impact on the performance of the whole system.

Hardware level reconfiguration mechanism

Partial reconfiguration requires that reconfiguration bitstream files that store the hardware reconfiguration option are available in advance. Usually they are stored in the DDRAM memory. Each FPGA has a DDRAM memory connected, and besides the communication related functions they can also contain reconfigurable IP (Intellectual Property) cores.

Bitstream-based partial configuration can be done using the ICAP (Internal Configuration Access Port) that is already loaded in the initial configuration stream. A Partial Reconfiguration (PR) controller is required to initiate the reconfiguration. The job of a PR controller is to retrieve the partial bitstream from memory, then to deliver it to a configuration port. An internal PR controller loads partial configuration bitstreams through the ICAP interface. As with any other logic in the static design, the internal partial reconfiguration control circuitry operates without interruption throughout the partial reconfiguration process.

The speed of reconfiguration depends on many factors. The most trivial is the speed of the source interface (PCI-express), the ICAP component which writes, and loads the frames to the FPGA configuration RAM, and the size of the cores. The C-Board design has a 125Mhz/64bit user data bus on the PCI-express interface. This results an approx. 8 Gb/sec throughput in theory. Practically, data throughput is around 7.2-7.6 Gb/sec depending on header/payload size and PC system configuration.

The necessary amount of transferred data also determines the overall performance. Differential core sizes vary depending on application complexity from 40-100 Kbytes to 1-2 Megabytes (almost full sized cores). Unfortunately, except some marginal cases binary file compression does not increase performance, due to the time consuming decompression process.

Above all, the real bottleneck is the operation speed of the ICAP controller. The component can operate in x8, x16, and x32 input/output bus width-modes. Input clock rates theoretically vary from 200 KHz to 200 MHz by Virtex5 devices. During our further investigation we have considered a XPS_HWICAP structure amended with a DMA controller in a Virtex FPGA introduced in [START_REF] Liu | Run-Time Partial Reconfiguration Speed Investigation and Architectural Design Space Exploration[END_REF] where the authors state an average reconfiguration speed of 82.1 MB/s achieved by simulation using this structure.

Applications of hardware reconfiguration in networking

In the networking area there are numerous applications for the reconfigurable hardware. Dynamic reconfiguration of hardware, however, is a new topic of interest. Dynamic reconfiguration has been used for several networking applications in the literature such as in firewalls [START_REF] Lockwood | An Extensible, System-On-Programmable-Chip,Content-Aware Internet Firewall[END_REF], intrusion detection systems [START_REF] Yu | PKI based dynamic reconfiguration home network media centre[END_REF], on-demand configured cryptographic and multimedia accelerators [START_REF] Lockwood | Internet Worm and Virus Protection in Dynamically Reconfigurable Hardware[END_REF], enhanced packet processors [START_REF] Kachris | A Reconfigurable Platform for Multi-Service Edge Routers[END_REF] and for reducing the power consumption. Based on the reconfiguration time requirements, the following application fields are present:

• User-requested reconfiguration. In this scenario the user initiates a reconfiguration of the hardware, loading an IP core with different characteristics. The reconfiguration itself can be automatic, for example a result of a setting change on the graphical user interface. An example application is the change of the protocol-optimized monitoring IP core to another protocol. The reconfiguration time has limited importance here.

• Per-flow on-demand reconfiguration. The reconfiguration takes place in order to meet the requirements of the new flow. Example applications are changing the cryptographic core or video codec to meet the requirements imposed. Reconfiguration time is now important, but it should only affect the new flow.

• Run-time reconfiguration of the packet processing logic. Reconfiguration is triggered by a signal or by reaching a load threshold. In this case the reconfiguration time is critical; all packets handled by the module are affected.

In this paper we target on the last application area, where the delays introduced by reconfiguration can be compensated by buffering. However, the buffer sizes have constraints on both networking and hardware side: some networking applications have low delay and jitter requirements, while in hardware the memory required to buffer the packets is limited.

Networking address lookup algorithms

Address lookup can be realized by numerous algorithms. The goal of these algorithms is to find an entry in the so-called lookup table witch satisfies a given input criteria. The lookup table can change dynamically by adding, deleting or modifying entries; it is the duty of the lookup algorithms to realize these functions to maintain the table. The lookup table is usually stored in memory to allow fast access. The table itself realizes an overlay structure above the memory and the mapping of the table to the physical part of the memory is not the task of the lookup algorithms.

The simplest search method is the linear search, where the lookup is performed starting from the beginning of the table and progressing continuously comparing the entry in the pointed part of the table with the input entry. Other more complex algorithms use techniques like hashing and heuristics to increase lookup speed resulting in faster but more power consuming or increased storage complexity algorithms compared to the simple linear search.

In this work we have selected three different algorithms which can realize packet lookup: a Binary search, the HiCuts (Hierarchical intelligent Cuttings) [START_REF] Gupta | Hierarchical Intelligent Cuttings: A Dynamic Multi-dimensional Packet Classification Algorithm[END_REF] and the TCAM (Ternary Content Addressable Memory) based lookup. The Binary search algorithm maintains an ordered structure, where the search can be performed in binary decisions from the middle of the table.

The HiCuts algorithm works by cutting the state space along the number of classifiers (dimensions) until each leaf has no more entries than a predefined number. Based on this method entries can be stored in multiple leaves, therefore it has exponential space requirement (static consumption) depending on the number of classifiers in the entries.

The TCAM is a fully hardware accelerated algorithm which can be implemented in FPGA platform. It can find an entry in the table in one clock cycle independent of the size of the table [START_REF] Le | Scalable High Throughput and Power Efficient IP-Lookup on FPGA[END_REF]. In that time it consumes massive power which is proportional of the number of entries stored in the table. In fact the consumption is a linear function of the number of cells occupied by the implementation and of the frequency [START_REF] Chen | Power efficient packet classification using cascaded bloom filter and off-the-shelf ternary CAM for WDM networks[END_REF].

The average power consumption of these algorithms can be calculated as follows:

mgmt dynamic static sum E E E E   
, where the static consumption ( static E ) expresses the consumption of the algorithm for storing its table in the memory. The dynamic consumption ( dynamic E ) relates to the operational consumption of the algorithm in case of lookup request. The management consumption ( mgmt E

) is connected with maintaining the lookup table after entry deletion or addition. Since the modification of the lookup table by adding or deleting entries is a rare event in the provider core network the management consumption is negligible compared to the other two consumptions. Because of this we have omitted the management consumption from our simulations.

d k*N r + d C 2 * d TCAM N N k*N + N 1
In Table 1 we have collected the consumption complexity and response time of the examined algorithms [START_REF] Gupta | Algorithms for Packet Classification[END_REF]. All consumption values are proportional to memory operations needed in average and response time values are proportional to the number of sequential operations required for one request. Parameter N expresses the number of entries stored in the lookup table . Parameter k is the ratio between the static and dynamic consumption, while C x are constants related to the operation of the algorithms in the memory. The exponential static consumption of the HiCuts algorithm represents the worst case scenario where all entries are present in all of the leaves. In practice the exponent is much less than d which is expressed by choosing parameter r properly.

All consumption values represent orders of magnitude in average and response time values represent orders of magnitude of clock cycles (proportional to memory accesses required).

If we consider a power unit the energy required to make one memory operation, we can express the power consumption of different algorithms in power units. In spite of showing concrete power numbers for a concrete hardware we will come up with percentages of power savings using reconfiguration in general by simulation.

The basis of the optimisation is to use an algorithm which is fast enough to serve the demand and has the minimal consumption among them. When there is less demand we can reconfigure the device to a slower and also less power consuming algorithm.

Simulations

The simulations were implemented in SystemC/TLM using the ReSP (Reflective Simulation Platform) [START_REF]ReSP simulator[END_REF] designed by the Technical University of Milano. This platform combines the flexibility of the Python language with the robustness of the C language. The simulation handling is dynamic due to the reflective properties of Python. Reconfigurability was an amendment to this platform.

Simulation Scenarios

In the simulations we have modeled a 4 port router with 10G interfaces in an aggregation (core) network. We use an adaptive algorithm to perform reconfiguration based on the incoming traffic intensity. The reconfiguration algorithm targets to exploit the daily variation of the traffic level which can be observed in the core network where data is aggregated from dozens of users. The daily traffic variation is a slow process, but the traffic in off-peak hours is only a percent of the peak traffic. This slow variation can be tracked by a few reconfigurations with insignificant impact on the Quality-of-Service (jitter) but still providing significant power gain.

In the simulations we have reconfigured the lookup algorithm on an FPGA, which is responsible for packet lookup. The three selected lookup algorithms (described in Section 3) are assigned to traffic speed intervals based on their lookup speed. We supposed that the cores are available in advance and reconfiguration is done by a hardware assisted mechanism.

The parameters have been chosen as follows for the simulations. The number of entries (N) to 1000, the number of classifiers (HiCuts dimension) to 2, the constants (C 1 , C 2 ) to 3 for reading the memory, comparing content, and reading address of next entry. Parameter r has been chosen for 0.6 which is less than 1 but still makes the table size close to the values achieved in simulations in [START_REF] Gupta | Hierarchical Intelligent Cuttings: A Dynamic Multi-dimensional Packet Classification Algorithm[END_REF] which is a good compromise.

As introduced in Section 3 we measure consumption in power units by choosing the k parameter for 1/50 meaning that the operational consumption of the algorithms is 50 times higher than in idle state. ratio can be observed by many used memory types and it is also true for FPGA block RAMs.

The bitstream required to insert the entries into the memory is calculated by multiplying the number of entries with the size of one entry. The dimension was chosen to be 2, which by having two 4 Byte IPv4 addresses gives 8 Byte for an entry. Multiplying this with the number of entries results in 8 KB as the size of the table. According to the speed of the ICAP controller (80 MB/s) explained in Section 2.1 the reconfiguration time is about 100 ns. In case of the HiCuts algorithm the table size calculated is approximately 253 KB and the reconfiguration time is about 3.2 ms. In Table 2 the parameters of the algorithms calculated for the simulations are summarized. For example, the consumption of the binary search is calculated as follows: 30 96 , 9 20 1000 log 50 1000 log * 50 A sinusoid traffic generator has been implemented to simulate the changing traffic in a daily period. The values on this curve represent the expected values of a Pareto probability distribution, while packet sizes are chosen according to simple IMIX model widely used to simulate network traffic. The incoming traffic speed is calculated and given to an IIR filter to smooth out bursts.

1 2 2        N N E bin

Results

In the first simulation we have considered the daily traffic fluctuation approximated by a sinusoidal traffic varying between 3-8Gbps. In reality this should have a daily periodicity however we have reduced the period to 1 second only for simulation scalability reasons. Algorithms are configured according to their average throughput, with a hysteresis of 5% around the configuration threshold of each algorithm. Results are presented on Figure 1. The upper graph shows the traffic load. The middle graphs show the queue utilization and consumed power. The reconfiguration cost considered in our simulations is 2000 power units. When the traffic load level crosses an algorithm configuration threshold, reconfiguration occurs. During reconfiguration the arriving packets are buffered. The queue utilization is around zero most of the time, with short spikes around the configuration changes. After reconfiguration the queue is emptied with a faster algorithm. When a new threshold is crossed (either upper or lower) the most appropriate algorithm is configured again. The lower graph shows the selected algorithm in a particular moment.

Figure 1 Throughput based reconfiguration

Beside actual power average power is also shown on the 3 rd graph. If we do not use reconfiguration, the fastest (and most power hungry) algorithm must be used all the time. This is the TCAM which has a power consumption of 1020 power units. With reconfiguration the average power consumption is less than half (below 500 in longterm) indicated by the red line on the graph.

In the second simulation we show that higher power gain can be achieved if we use buffer level based reconfiguration instead of traffic intensity based. In this case reconfiguration occurs whenever the buffer utilization crosses a threshold (selected to 50kbytes, 200kbytes and 500kbytes respectively). The new algorithm with its higher throughput will empty the buffer, and when the buffer utilization gets below the lower threshold of 50kbytes, the slower algorithm is configured again. Before reconfiguration the possible energy gain is also evaluated and a reconfiguration is carried out only if the gain is higher than the cost of reconfiguration. Figure 2 shows the results in case of buffer based reconfiguration. The offered traffic has a 7Gbps load with Pareto distribution. This configuration uses 2 algorithms only, a faster TCAM based and the slower HiCuts. The HiCuts algorithm is unable to handle this much traffic, which results in increasing buffer utilization. When the TCAM based algorithm is then configured the buffer starts to decrease quickly as the TCAM lookup speed is faster than the load. During the reconfiguration the buffer is increasing fast (almost vertical increase between 3Mbytes and 4Mbytes).

Figure 2 Buffer threshold based reconfiguration

The introduced delays are proportional to the queue utilization, the jitter in this case is determined by minimal and maximal buffer utilization, and it is in range of 0-4.5ms. This jitter is considerable, and may not be tolerable by some applications.

To reduce the jitter introduced by buffering we can limit the lower threshold on the buffer utilization for each algorithm for the desired jitter limit. This of course results in lower gain in energy, but also in lower jitter.

In the simulations we have used a jitter limit of 2ms. Power consumption for different loads and different reconfiguration schemes is shown on Figure 3. As we can see, without reconfiguration (blue line) the power consumption is a bit more than 1000 power units. In case of jitter-limited (green line) scheme the gain is determined by the algorithm properties only, and only a few reconfigurations are allowed. Maximal gain (red line) can be achieved if algorithms are changed dynamically, and in this case further gain can be achieved at the cost of an accepted jitter (which can be limited, as an input to the scheme).

Figure 3 Power consumption for different reconfiguration schemes 5 Conclusions

Partial reconfiguration is a very interesting technique which has many benefits. It can be used to gain space on FPGA, to reduce power consumption and it also can be used in specific network-related applications like lookup tables or filtering rule sets. We have presented the partial reconfiguration possibilities on the C-board, and also we have identified the most important components of the reconfiguration. The possible use cases for partial reconfiguration have been discussed and we have investigated by simulation the applicability of dynamic reconfiguration in a high speed networking environment. Results show that dynamic reconfiguration can be used to reduce power consumption by adapting to the load levels, with an increased jitter penalty. The daily traffic fluctuation can be exploited by minimal impact, but considerable higher gain can be achieved by allowing buffering and rapid reconfigurations at a higher but controlled jitter penalty. The reconfiguration process inevitably introduces delays, and further delays are introduced while maximizing the energy gain. The impact of the delays on network traffic can be simulated in network simulators, which take into consideration both the transport protocol and application specific behaviour.

Table 1 .

 1 Consumption complexity and response time of different lookup algorithms (proportional to memory accesses and sequential operations, respectively)

	Algorithm	Consumption Static Dynamic	Sum	Response time
	Binary HiCuts(d)	N N rd (r ≤ 1 )	log 2 N	k*N + log 2 N	C 1 * log 2 N

Table 2 .

 2 Calculated simulation parameters for the selected algorithms (from Table1with selected parameters)

	Algorithm	Consumption (in Power Units)	Max. speed	Reconfiguration time [ns]
	Binary search	30	4,7 Gb/s	100
	HiCuts(d)	82	6,9 Gb/s	3200
	TCAM	1020	9,6 Gb/s	100

Acknowledgement

The research leading to these results has received funding from the ARTEMIS Joint Undertaking under grant agreement n° 100029 and from the Hungarian National Office for Research and Technology (NKTH).

This work is also connected to the scientific program of the "Development of quality-oriented and cooperative R+D+I strategy and functional model at BME" project. This project is supported by the New Hungary Development Plan (Project ID: TÁMOP-4.2.1/B-09/1/KMR-2010-0002).


Xiaomeng Shi
email: xshi@mit.edu

Muriel Médard
email: medard@mit.edu

Daniel E Lucani
email: dlucani@fe.up.pt

When Both Transmitting and Receiving Energies Matter: An Application of Network Coding in Wireless Body Area Networks

Keywords: wireless body area networks, network coding, medium access control, energy efficiency

A network coding scheme for practical implementations of wireless body area networks is presented, with the objective of providing reliability under low-energy constraints. We propose a simple network layer protocol for star networks, adapting redundancy based on both transmission and reception energies for data and control packets, as well as channel conditions. Our numerical results show that even for small networks, the amount of energy reduction achievable can range from 29% to 87%, as the receiving energy per control packet increases from equal to much larger than the transmitting energy per data packet. The achievable gains increase as a) more nodes are added to the network, and/or b) the channels seen by different sensor nodes become more asymmetric.

Introduction

Body Area Networks (BAN) present numerous application opportunities in areas where measured personal information is to be stored and shared with another individual or a central database. One example is wearable medical monitors which can relay patients' vital information to physicians or paramedics in real time. A wireless body area network (WBAN) is composed of sensors attached to the human body. The sensors also function as transceivers to relay measurements to a personal server (base station); this central receiver then communicates with remote servers or databases. In this paper we consider such WBANs where the central communication problem is to ensure reliable and secure transmission of the measured data to the base station (BS) in a timely and robust fashion.

Here the amount of data uploaded from the sensors to the BS much outweighs the amount of control signals downloaded from the BS, but energy used to receive control signals can still be high depending on the specific physical layer implementation and the network layer control protocol used. We develop a protocol to incorporate network coding into the system architecture, and show for a star network with multiple sensor nodes, using network coding can reduce the number of times sensors wake up to receive control signals, thus reducing the overall energy consumption and lengthen the system depletion time. In the remaining part of the introduction, we show through a simple example the potential energy gains of applying network coding to transmissions in a WBAN. We also discuss briefly past works related to energy efficient WBAN design. The rest of this paper is organized as follows. Section 2 describes the network and energy model, and the network coded algorithm. Section 3 provides a Markov chain model to analyze the optimal number of packets to transmit by each sensor node. Numerical results are presented in Section 4, comparing the network coded scheme with uncoded scheme in terms of completion energy. Section 5 concludes the paper.

Example: Network Coding Benefits in WBAN

Before discussing other past work related to energy efficient WBAN design, we first show through a simple example why network coding can be beneficial. One category of energy use often overlooked in wireless networks is the reception energy spent on listening to control signals from the base station. In a WBAN, however, such reception energies can have more significant effects on node depletion time since data rate is much lower, but control signals need to be transmitted frequently for medium access purposes. Let us consider a two-sensor star network with nodes N 1 and N 2 , each trying to directly upload 4 packets to a BS through the same frequency band. In the link layer, assume the packet erasure probabilities are time invariant, at 0.2 and 0.4 respectively. Figure 1 shows instances of four different possible communication schemes, all based on time division multiple access (TDMA) with automatic repeat requests (ARQ). Shaded blocks represent data packets in transmission and ack packets in reception; white blocks represent time during which nodes are idle. Some packets are lost during transmission according to the different erasure probabilities. Define a transmission round to be the transmission of data packets by one or more sensor nodes, followed by a broadcasted ack packet. Both nodes wake up at the end of a transmission round to listen to the ack, which contains retransmission requests and schedules for the next round.

(a) Fixed Timing Allocation (FTA): each node is allocated 4 slots per round, and both wake up at the end of each round to receive the broadcasted ack. (b) Node-specific ARQ (NARQ): each node transmits until all of its packets are received successfully. The ack packet contains retransmission requests for the actively transmitting node and scheduling information for both nodes. (c) Combined ARQ (CARQ): both nodes are allocated specific transmission periods each round, with a combined ack packet broadcasted at the end. To evaluate energy use, assume every data packet transmission and every ack packet reception consumes an equal amount of E units of energy. Table 1 compares the total energy required for the schemes shown in Figure 1. Also shown is the throughput of each scheme, defined as the total number of accepted data packets divided by the total transmission time in units of packet slots. Excluding ack periods and time during which nodes are sleeping, all schemes require 12E in data transmission. On the other hand, the energy used for ack reception varies significantly across the different schemes. CARQ-NC (hereafter referred to as 'NC') is the most energy efficient. FTA requires less or the same amount of total energy than NARQ and CARQ, but is throughput inefficient. As the number of nodes in the network increases, this inefficiency will become increasingly severe. CARQ outperforms NARQ, and NC introduces further gains. It is not necessarily true that NC always transmits the same total number of data packets as CARQ. In fact, NC sends more packets than the required number of dofs. Nonetheless, the added transmission energy is offset by reduced reception energy to give a smaller overall completion energy. This specific example is extremely simple, but very similar results can be expected as more sensor nodes are added. In the remaining parts of this paper, we will consider only the CARQ and the NC scheme. Our goal is to determine analytically the optimal network coding and transmission scheme such that the expected completion energy for the overall transmission is minimized.

Related Work

To make WBANs practical, one approach is to modify existing wireless sensor networks (WSN) to suite the need of WBAN systems. References [START_REF] Cao | Enabling technologies for wireless body area networks: A survey and outlook[END_REF][START_REF] Chen | Body area networks: A survey[END_REF] compare WBAN with traditional WSNs and give comprehensive overviews of recent research efforts in the design of WBAN systems, particularly in terms of sensor devices, physical layer schemes and data link layer protocols. In WSNs, energy is often wasted in medium access collisions, idle listening, and protocol overheads when the desired data rate is low. Low power MAC protocols such as T-MAC, S-MAC and Wise-MAC have therefore been proposed to introduce various degrees of synchronization into the transmission schedule, but these schemes are not throughput efficient. Recently a WBAN specific MAC protocol has been proposed to adjust parameters of the IEEE 802.15.4 parameter in an adaptive fashion to achieve energy efficiency [START_REF] Li | An ultra-low-power medium access control protocol for body sensor network[END_REF], but direct modification of this existing standard also introduces redundant communication modes. Unlike WSNs, a WBAN contains only a limited number of nodes, all positioned close to the BS. A single-hop master-slave architecture with TDMA suffices to remove much of the energy wastage seen in a WSN. Reference [START_REF] Omeni | Energy efficient medium access protocol for wireless medical body area sensor networks[END_REF] implements such an architecture, with adjustable wakeup fallback times to mitigate possible slot overlaps. We use a similar TDMA setup in the current paper. What we aim to achieve is to introduce network coding into the system architecture, such that overall data transmission completion energy can be reduced by reducing the number of times sensor nodes wake up to listen to control signals. Recent works by Lucani et al. consider the use of network coding in time division duplex systems to minimize packet completion time, energy use, and queue length in unicast and broadcast settings [START_REF] Lucani | Broadcasting in time-division duplexing: A random linear network coding approach[END_REF][START_REF] Lucani | Random Linear Network Coding For Time Division Duplexing: Energy Analysis[END_REF][START_REF] Lucani | Random linear network coding for time division duplexing: When to stop talking and start listening[END_REF]. The current study extends the unicast TDD case to that of a simple star network, with single-hop links between the BS and the sensors.

r 1 ack Node N 1 Node N 2 r 2 r K N 2 N 3 M 1 (p 1 , r 1 ) ack M 2 (p 2 , r 2 ) M K (p K , r K ) (b) Combined ARQ (CARQ), r k = #packets transmitted to the BS in the current round BS N 1 N k M 1 (p 1 , r 1 ) ack Node N 1 Node N 2 M 2 (p 2 , r 2 ) M K (p K , r K ) (c) CAQR with network coding (NC). M k (p k , r k ) = #coded packets transmitted to the BS in the current round, 1≤ k ≤ K. N k-1 (
2 Linear Network Coding for Energy Efficiency

System Model

We model a WBAN with a star topology as shown in Figure 2(a): each of K sensor nodes communicates with the BS directly to upload M data packets. Nodes and the BS are assumed to operate in half-duplex mode, either transmitting or receiving, but not at the same time. A WBAN occupies a single frequency band, with the BS centrally coordinating a TDMA scheme. Exact synchronization among the nodes and the BS is assumed, and nodes return to sleep when not transceiving. Computation of the transmission schedule is relegated to the BS, with start and stop times allocated through the ack signal. We assume ack packets are transmitted reliably, and propagation delays from BS to nodes are negligible. The channel between an individual sensor N k , 1 ≤ k ≤ K, and the BS are assumed to be memoryless, with packet erasure probability p k , which is invariant during the time when the M packets are uploaded.

The above system model may seem over-simplified, but is sufficiently accurate for the current study. As already discussed in Section 1.2, the small physical size of a WBAN enables the use of a star topology with TDMA scheduling controlled centrally by a BS. Compared to sensor nodes, the BS is relatively unconstrained in power. Ack packets can therefore be piggybacked on a periodic synchronization signal transmitted at high power, or protected through error correction codes to ensure reliability. In an actual implementation, additional headers or beacon periods will be needed for synchronization, but such details can be safely omitted here in analyzing the data transmission energy efficiency and system throughput. An additional difficulty in WBAN design is channel modeling for physical layer designs. Unlike cellular networks or WSNs, a WBAN is in close proximity to the human body. Absorption of emitted power and body movement can easily and frequently alter the channel response. Reference [START_REF] Yazdandoost | Channel model for body area network (BAN)[END_REF] provides a summary of channel modeling studies conducted and submitted to the IEEE 802.15.6 body area network task group. In the current paper, we only consider an erasure channel abstraction for the network layer model. The time-invariance assumption is a reasonable first step, since data in WBAN come in very small bursts periodically and the channel can be assumed to fade slowly over each such small periods.

In the CARQ scheme, nodes take turns to transmit data packets before waiting for a combined ack, which contains repeat requests and scheduling information. Figure 2(b) illustrates one round of transmission, where r k represents the number of packets requested by the BS for retransmission. In the NC scheme, each node linearly combines its M packets before taking turns to transmit the ensuing mixtures. The coefficients can be generated on the fly and attached to the data payload, or tabulated a priori. Assume the field size is large enough such that accepted coded packets are independent from each other with very high probability. Since coded packets represent degrees of freedom (dof) rather than distinct data packets, each node can transmit more than the required number of dof to compensate for packet losses. Figure 2(b) illustrates one round of transmission. M k represents the number of coded packets for (re)transmission. M k is a function of p k , the erasure probability, and r k , the remaining number of dof needed at the BS to decode successfully. Note M k ≥ r k . Since all nodes within the network need to wakeup from sleep modes to listen to the ack, reducing the number of ack packets effectively reduces the total energy consumption. M k should also be kept small to minimize redundant transmissions. We want to show that an optimal number, M k , 1 ≤ k ≤ K, of coded packets exists to minimize the mean completion energy.

Energy Consumption

We assume sensor nodes operate in two modes: transceive and sleep. Denote the processing and transmission energy per data packet by E p,CARQ and E p,N C for the uncoded and coded cases respectively; also denote the reception and processing energy per ack packet by E a,CARQ and E a,N C . When in sleep mode, most circuit components are assumed to be turned off such that energy consumption is negligible. Let E a,CARQ = αE p,CARQ , E a,N C = αE p,N C , where the parameter α can take on different positive values depending on the circuit and protocol designs. For example, in narrow-band systems where transmission power is approximately the same as receiving power, α is the ratio between lengths of ack and data packets. For short range ultra-wide band systems where transmission energy per bit is much smaller than the reception energy per bit, α can take on large values in the range of tens to the hundreds [START_REF] Daly | A pulsed UWB receiver SoC for insect motion control[END_REF][START_REF] Mercier | An Energy-Efficient All-Digital UWB Transmitter Employing Dual Capacitively-Coupled Pulse-Shaping Drivers[END_REF][START_REF] Ryckaert | Ultra-wide-band transmitter for low-power wireless body area networks: Design and evaluation[END_REF]. Moreover, assume E p,N C = (1 + β)E p,CARQ , where the non-negative factor β represents the additional energy needed to perform network coding. In later sections, we will study the effect α and β have on overall completion energy.

,1 ,2 M M C C p p ( ) ,2 ,1 ,2 1 2 2 1 M M M c l c c l l M p p p - = - ∑ ,1 M C p M,M M,M-1 M,1 M,0 M-1,M M-1,M-1 ,1 ,2 1 2 M M p p ,1 1 M p M-1,M M-1,M-1 1,M 1,0 0,M 0,M-1 0,1 0,0 1
Fig. 3. Markov chain representation of the network coded scheme, number of nodes is K = 2.

Expected Energy for Completing Transmission

To study the expected completion energy of uploading data from sensor nodes to the BS in a WBAN, we model the communication process using a Markov chain. Let state I = (i 1 , . . . , i K ) represent the dof requested by the BS from nodes (N 1 , . . . , N K ) for the next round of transmission, where

0 ≤ i k ≤ M , 1 ≤ k ≤ K.
The overall communication process initializes in state M = (M, . . . , M ) and terminates in state 0 = (0, . . . , 0). Assume packet losses occur independently across nodes, the transition probability from state I = (i 1 , . . . , i K ) to state J = (j 1 , . . . , j K ) is P IJ = P (i1,...,iK )(j1,...,jK ) = ∏ K l=1 P (i k ,j k ) , where P (i k ,j k ) = P i k j k and

P ij =          ( c i,k i -j ) (1 -p k ) i-j p c i,k -i+j k 0 < j ≤ i ∑ c i,k l=i ( c i,k l ) (1 -p k ) l p c i,k -l k j = 0 . ( 1
)
c i,k = M k (p k , i
) denotes the number of coded packets node N k transmits when it sees a packet erasure probability of p k and the BS requires i additional dof for decoding; c 0,k = 0. The value of c i,k is computed by the BS. This Markov chain has (M +1) K -1 transient states and one recurrent state, 0, which signals completion of the transmission. Figure 3 illustrates the case where there are K = 2 sensor nodes within the WBAN. Let E I denote the expected system completion energy when nodes (N 1 , . . . , N K ) have (i 1 , . . . , i K ) dof to upload to the BS respectively, then E I is the expected absorption time of this Markov chain. Let Q = {0, . . . , i 1 }×. . .×{0, . . . , i K }. The following recursion holds

E I = 1 1- ∏ K k=1 p c i k ,k k { E p ∑ K k=1 c i k ,k + E a K + ∑ J∈Q\I P IJ E J } .
Unlike the erasure probabilities P IJ , this expected completion energy can not be separated into node-specific energy terms. To minimize the expected completion energy

E M , let C = {c i,k |1 ≤ i ≤ M, 1 ≤ k ≤ K}, c 0,k = 0, 1 ≤ k ≤ K, we then have C * = argmin C E M , E * M = min C E M ,
and the following recursion, where

Z M +1 = {0, . . . , M }. E * M = min cM,1 ...,cM,K 1 1 - ∏ K k=1 p c M,k k    E p K ∑ k=1 c M,k + E a K + ∑ J∈(ZM+1) K \M P MJ E * J    .
(

) 2
One approach to this optimization is to ignore the integer constraints, and solve for c i,k iteratively by finding values that set the partial derivatives of the objective function to zero. However, it can be shown that no closed-form solution exists. Also since there are (M + 1) K states in the Markov chain. As M and K increase, the computational complexity becomes prohibitive for a practical system. An alternative is to perform exhaustive numerical searches for the optimal values C * on an integer grid. For given values of {p k |1 ≤ k ≤ K}, E p , and E a , we can recursively search on an M dimensional space of non-negative integers to find C * . We will show numerical examples in the next section for such an optimal scheme. In a practical implementation, the computation task is imposed on the BS, not individual sensor nodes. Neither do the results need to be computed in real time. Instead, pre-computed values can be stored in a look-up table according to different packet erasure probabilities. The exact quantization required to balance the accuracy and required memory is a topic for future studies.

Numerical Examples

In this section, we provide numerical examples for the CARQ and NC schemes to study the amount of energy reduction offered by network coding as system parameters vary.

Table 2 lists explicitly the solution to the optimization problem stated in Section 3 when there are K = 2 nodes within the network, each having M = 4 data packets to upload, p 1 = 0.2, p 2 = 0.4. Assume α = 1 and β = 0. The first column(row) states the remaining number of dof required by the BS from node N 1 (N 2 ). Transmission initiates at (i 1 , i 2 ) = (4, 4), and terminates at (0, 0). Since N 2 sees a more challenging channel, it sends more coded packets than N 1 , when the same number of dof is requested. Observe that the number of coded packets sent by N 2 actually increases from 6 to 7 when i 2 = 4, and i 1 is decremented from 4 to 0. This is because N 1 is expected to complete its data transmission in a small number of rounds, thus N 2 would want to send more data packets such that it also completes its data transmission in a small number of rounds, to reduce the total number of times both wake up to listen to ack signals. The optimal solution minimizes the sum of all energy terms, taking into account of future rounds of retransmissions, and tries to reduce possible energy wastes. The optimal expected total completion energy is found to be 16.46E, larger than 14E shown in Table 1, which illustrates only one possible channel realization. Figure 4 extends the example in Table 2 to summarize the percentage reduction in expected completion energy per accepted data packet achieved by the NC scheme when packet erasure probabilities vary. A packet is said to be accepted by the BS if it is received successfully, and the percentage reduction is computed with respect to the CARQ scheme. Again, we assume α = 1, i.e., E p,N C = E a,N C , E p,CARQ = E a,CARQ , and β = 0, i.e., E p,N C = E p,CARQ . The horizontal axis represents variations in the packet Table 2. Optimal numbers of coded packets to transmit by each node when dof requested by the base station is i1 from node N1 and i2 from node N2; M = 4, K = 2, p1 = 0.2, p2 = 0.4, α = 1, β = 0. erasure probability of node N 1 . When the erasure probability of N 2 increases from 0.2 to 0.8, the amount of reduction in expected completion energy per accepted data packet increases from 3.5% to about 29%. Although not shown explicitly in this graph, the energy gain is derived from reduced number of transmission rounds. As p 2 degrades, the actual amount of energy spent for each accepted data packet increases, because more retransmissions are expected. Since depletion occurs more quickly when the channel condition worsens, the increased amount of saving is beneficial in extending the lifetime of sensor nodes. Another observation from Figure 4 is that the curves take a dip at different values of p 1 . The locations of these minima correspond approximately to the values of p 2 in each case. This is because the NC scheme achieves higher energy reduction when nodes experience more asymmetric channel conditions. When packet losses occur asymmetrically, nodes with more reliable channels complete data transmission quickly; yet they are forced to wake up for the ack signal repeatedly until other nodes with less reliable channels complete their transmissions. When nodes see similar channel conditions, with high probability, all nodes have non-zero number of packets to send each round, hence not as much energy is wasted in listening to the ack signals.

Figure 5 considers the more general case when the number of sensors within the network is increased, and M is set to 2 for simplicity. More gains can be achieved when more nodes are included, especially under asymmetric channel conditions. Although not shown explicitly here, we also compared numerical results under different network coding parameters. When the generation size M is varied, the amount of energy gain over CARQ is higher if M is smaller, with a decrease of approximately 10% as M increases from 2 to 10. This is because reception energy is amortized over more data packets. The NC scheme can also be shown to improve the throughput of the system.

So far we have examined reduction in completion energy achievable through NC when the reception energy E a per ack packet is the same as the transmission energy E p per data packet, i.e., α = 1. The actual value of α is dependent on the circuit architectures of the transmitter and receiver, and the data and ack packet payload design. For example, α can be on the order of 1 for a narrow band system, but can be one or two orders of magnitude larger for an ultra-wide band system [START_REF] Daly | A pulsed UWB receiver SoC for insect motion control[END_REF][START_REF] Mercier | An Energy-Efficient All-Digital UWB Transmitter Employing Dual Capacitively-Coupled Pulse-Shaping Drivers[END_REF][START_REF] Ryckaert | Ultra-wide-band transmitter for low-power wireless body area networks: Design and evaluation[END_REF]. Figure 6 shows the reduction in completion energy in using NC over CARQ when α is varied, where E a = αE p , E p = E p,N C = E p,CARQ and E a = E a,N C = E a,CARQ . Again, the computation is conducted over a 2-node network for simplicity. The observed gain is not as significant as 29% when α decreases from 1, for data transmission energy much outweighs ack reception energy. However, as α increases to values higher than 15, we can achieve up to 87% in energy reduction, i.e., 5 times less energy. This is equivalent to extending the lifetime of a sensor node by a factor of 5.

Another assumption we have made explicitly in previous examples is that the average transmission energy E p is the same for both NC and CARQ. In an actual implementation, the NC scheme may require non-negligible energy overheads for coding. Figure 7 compares the completion energy of the two schemes when E p,N C = (1 + β)E p,CARQ = (1 + β)αE a,CARQ , α = 1, and E a,N C = E a,CARQ . Here the energy advantage is lessened because of the added cost of coding. Nonetheless, even with a 20% overhead in coding, we can still achieve an energy reduction of about 17%.

Conclusion

We proposed a network coded scheme to help improve energy efficiency of wireless body area networks. Assuming that the different channel conditions experienced by individual nodes are known at the base station, the base station can request each sensor node to send an optimal number of coded packets, taking into account anticipated packet losses during transmission, and energy needed for receiving control signals. We show with numerical examples that in a two-node star, when transmitting a data packet and receiving an ack packet cost approximately the same amount of energy, the network coded scheme can achieve up to 29% percent reduction in expected completion energy per accepted data packet compared to the CARQ scheme. When receiving costs a lot more than transmitting, network coding can reduce energy use by up to 87%. We also shown with numerical examples that the amount of energy gain achievable through coding increases as more nodes are added to the network, and when nodes see more asymmetric channel conditions.

  TDMA with fixed timing allocation (FTA). (b) Node-specific ARQ (NARQ). Combined ARQ (CARQ). (d) CARQ and network coding (CARQ, NC).

Fig. 1 .

 1 Fig. 1. Example comparing overall completion energy for 2 nodes, each with 4 packets to upload; the erasure probabilities are p1 = 0.2, p2 = 0.4.

Fig. 2 .

 2 Fig. 2. Uplink transmissions using combined ARQ and network coding.

Fig. 4 .

 4 Fig. 4. Percentage reduction in expected completion energy per accepted data packet as p2 varies; M = 4, K = 2, α = 1, β = 0.

8 K 8 KFig. 5 .

 885 Fig. 5. Percentage reduction in expected completion energy as K is varied, M = 2, α = 1, β = 0.

Fig. 6 .

 6 Fig. 6. Percentage reduction in expected completion energy when α is varied, M = 4, K = 2, β = 0, p2 = 0.8.

Fig. 7 .

 7 Fig. 7. Percentage reduction in expected completion energy when β is varied, M = 4, K = 2, α = 1, p2 = 0.8.

6 Acknowledgment

 6 This material is based upon work supported under subcontract # RA306-S1 issued by the Georgia Institute of Technology, by the Claude E. Shannon Research Assistantship awarded by the Research Laboratory of Electronics, MIT, and by the NSERC Postgraduate Scholarship (PGS) issued by the Natural Sciences and Engineering Research Council of Canada. This work is also partially funded by the European Commission under grant FP7-INFSO-ICT-215252 (N-Crave Project).

Table 1 .

 1 Comparison of completion energy per accepted data packet; there are 2 nodes in the star each with 4 packets to upload. ET X = total transmission energy; EA = energy spent on listening to acknowledgement packets; Etot = total completion energy per accepted data packet,

	η = throughput.
		ET X EA Etot	η
	(a) FTA	12E 6E 9E/4 8/27
	(b) NARQ	12E 10E 11E/4 8/17
	(c) CARQ	12E 6E 9E/4 8/15
	(d) CARQ-NC 12E 2E 7E/4 8/13
	(d) Combined ARQ and network coding (CARQ-NC): each node linearly combines its
	4 data packets before transmission. Since each coded packet represents an addi-
	tional degree of freedom (dof) rather than a distinct data packet, more than 4 coded
	packets can be sent to compensate for anticipated losses.


Marjan Eggermont
email: meggermo@ucalgary.ca

Charles Perin
email: charles.perin@ucalgary.ca

Bon Adriel Aseniero
email: baasenie@ucalgary.ca

Roxane Fallah
email: roxane.fallah2@ucalgary.ca

Sheelagh Carpendale
email: sheelagh@ucalgary.ca

Leveraging Biological Inspiration in an Information Visualization Class

We reflect on an infovis course with a focus on biomimicry that we taught in Winter 2016. This graduate course looked beyond visualization basics and fundamentals and focused on the idea of making use of a biomimetic approach in visualization. As global interest in visualization expands, exciting new research is emerging in many facets of visualization. One of these new directions draws from the incredible successes in engineering, where improvements in many directions including form and functionality are resulting from leveraging the examples from biology, or biomimicry. The course was set in examples of advanced visualization topics so students with heterogeneous backgrounds could draw from multiple disciplines and implement visualization projects using bio-inspired design.

INTRODUCTION

In this paper we reflect on our experience in a recent graduate class when we used biomimicry as the primary source of inspiration for the design of visual representations of data. Biomimicry is "an approach to innovation that seeks sustainable solutions to human challenges by emulating nature's timetested patterns and strategies."[https://biomimicry.org/ what-is-biomimicry/]. Our motivations for this exploration are widespread varying from specific questions about whether biomimicry is an effective classroom innovation approach to broader research questions about whether bio-inspired design can be leveraged to expand possibilites for InfoVis.

An important distinction to make is between visualization of biology (biovis) and biomimicry or using biology as a source of inspiration for representation of data -not necessarily biological data. Visualization of biology is a well established research area with at least two dedicated conferences: BioVis [http://biovis. net/], which is largely organized by visualization researchers, and VizBi [https://vizbi.org/], which is largely organized by biologists. In contrast, biomimicry has received much less attention in the visualization research field. This concept has rarely been applied to information visualization and the few existing examples seem unaware of the larger biomimicry movement. The possible benefits for information visualization still remain under explored.

BACKGROUND AND MOTIVATION

Biomimicry comes from the Greek words bios, meaning "life", and mimesis, meaning "to imitate". Biomimicry is an increasingly popular approach to finding sustainable solutions to human problems by taking inspiration from natures patterns [START_REF] Benyus | Biomimicry: Innovation Inspired By Nature[END_REF] to inform form, function or process. This is typically achieved by using biological pat-terns or principles as the source for design ideas [START_REF] Valtere | First steps to develop biomimicry ideas[END_REF], based on the idea that nature and natural selection offer winnowed solutions to human problems. Applications of biomimicry to engineering range from designing the nose of Japanese high-speed trains inspired by the beak of kingfishers [START_REF] Mckeag | Auspicious forms[END_REF] to finding optimal trucking routes based on the foraging behavior of individual ants [START_REF]AntOptima[END_REF] to syringe needles made less painful by copying mosquito proboscis [START_REF] Izumi | Realistic imitation of mosquito's proboscis: Electrochemically etched sharp and jagged needles and their cooperative inserting motion[END_REF].

Because biomimicry is increasingly popular for solving engineering and technology design challenges, we thought that infovis could also benefit from this design approach for creating new visualizations. A few researchers in infovis have already successfully explored this approach. For example, with Visual Sedimentation [START_REF] Huron | Visual sedimentation[END_REF], Huron et al. mimicked the sedimentation in nature to create visualizations using motion and physics. In-Formation Flocking [START_REF] Vande Moere | In-Formation Flocking: An Approach to Data Visualization Using Multi-agent Formation Behavior[END_REF] is a visualization in which individuals interact with simple behavioral rules, resulting in a bio-inspired swarm behavior. The emergence and success of the VISAP program [4] at VIS demostrates where bio-inspired visualizations are intensively used at the intersection of art and visualization. For example, Ji and Wakefield [START_REF] Ji | Endogenous Biologically-Inspired Visualization Immersed within an Art of Complex Systems[END_REF] document biologically-inspired installations.

COURSE ORGANIZATION

Eggermont has been teaching bio-inspired design in engineering for over 10 years and co-founded the Zygote Quarterly bio-inspired design journal (http://zqjournal.org/). Perin and Carpendale have experience teaching infovis. This was a unique opportunity to leverage our combined expertise in both biomimicry and infovis to create this course.

This was a 13 weeks long, three hours a week, graduate course offered if enough students signed up. At the university of Calgary, Computer Science courses are part of the Computer Media Design program which allows for more flexible course offerings due to the multidisciplinary nature of the program. Given the focus of the course, we made the following assumptions:

1. We assumed students were familiar with infovis. We provided an introductory lecture but self-study was expected for those new to the field. This made it possible to focus on leveraging biomimicry instead of on learning basic infovis concepts.

2. We provided an overview of the broad field of bio-inspired design -from product design to bio-inspired computing. We expected students to self-study once they had chosen an area of bio-inspiration for their projects.

Outline and Assignments

The graded components of the course were as follows:

• 20% in class activities: data sketching activities (weeks 1 and 2) and engagement with discussions during guest lectures. • 20% in class participation: project proposal (week 3), project update presentations (weeks 6 and 9), final project presentation (week 13), and critiques of other students' projects. • 60% course project: content of the final presentation (6%), video showcasing the project (10%) and written report (44%). We integrated infovis and biomimicry through graphic design process methodology. In the first 3 hours class we gave a brief overview of information visualization basics (primarily based on J. Bertin [START_REF] Bertin | Semiology of Graphics[END_REF]), and in the second 3 hours class an overview of biomimicry. Then, to give a broad perspective of the variety of approaches currently being applied to visualization, each class featured lectures from established researchers who publish visualization in their own fields including: kinesiology, neurology, reservoir geoscience, and biology. Classes were then split into two parts: the first half was dedicated to projects and student presentations; the second half was dedicated to guest lectures.

The graphic design approach included dedicating three hours of class time to design process for every six hours of lecture and seminar time. In the design process sessions, we used a mixture of student presentation, critique, discussions, and brainstorming techniques including basic design charrettes (https://en. wikipedia.org/wiki/Charrette). Through this process students chose a dataset near the beginning of the class and worked through several possible sources of bio-inspiration during the class.

STUDENT PROJECTS

Students had to think about their projects from the first class. Week 1, they were asked to think about what data they would use, how they would collect the data, and why this data is important to them.

Week 2, they were asked to look more deeply into their data and characterize data dimensions, types and scales, and to explain what they found interesting in this data. Then they were then asked to create ten independent sketches during a data sketching in class activity to map the variables spatially. They were further asked to pick the best sketch and to create ten variations on a theme.

Weeks 1 and 2, students were asked to explore where bio-inspiration can be introduced in their design process. They were asked to find interesting functions on www.asknature.org and to present their bio-inspirations to the class.

From week 3 and until the end of the course, they were asked to code their visualization or to create their physical visualization.

At the end of the class, students were asked to include in their project report: i) changes that they made to their initial proposal and how they used biomimicry; ii) inspirations from related work; iii) data description; iv) representation components of the project (how to read the visualization); v) interaction components of the project (how to interact with the visualization and explore the data); and vi) lessons learned, including what worked and what did not work.

Next we present two student bio-inspired projects that illustrate how bio-inspired design encourages original visualization projects.

Fireflies: Bon Adriel Aseniero

The Fireflies project is an exploration that uses swarming behaviours and plant phyllotaxis to create a bio-inspired visualization of a Canadian attitudinal survey on HIV/AIDS (see poster [START_REF] Aseniero | Fireflies: Biomimicry-Inspired InfoVis for Exploring Public Opinion about an Infectious Disease[END_REF] at the VIS 2016 conference). The data [START_REF]hiv/aids attitudinal tracking survey[END_REF] contains participants' answers to a series of health-related questions, which concentrate on public opinion and knowledge about HIV/AIDS. Along with demographic information such as age range and location in Canada, it includes self-reported knowledge of HIV/AIDS, and other factors such as their ideas about how the virus spreads, their opinions about the disease, and their degree of comfort/discomfort with HIV/AIDS.

The chief sources of bio-inspiration for this project are firefly swarming behavior and plant phyllotaxis. In nature, fireflies swarm towards food. In this visualization, particles representing participants swarm towards ideas they agree with. The phyllotatic patterns are used to layout dense swarms. The motion of the fireflies is used to depict comfort levels concerning HIV/AIDS, with particles representing participants less comfortable with HIV/AIDS appearing agitated and nervous. The visual properties of fireflies led to an expressive representation of a sensitive dataset (see Figure 1).

Chameleon skin, music and mood: Roxane Fallah

Fallah says: "In this project biomimicry not only is used to improve aesthetic aspects of data visualization, but is used as a conceptual inspiration in order to bridge between science, nature, and art." The data are the moods based on tags in social media of mu-sic gathered from Harvard Dataverse [3]. This dataset studies the relationships between music content and mood. For more than 600 popular music tracks, several moods are included and given a value.

Bio-inspirations are the skin color variation and skin cell geometry of chameleons. The aesthetics of the project are inspired by chameleon skin. Each of the active cells exhibit one of the moods of the dataset. Every cell has a color chosen based on the chameleon mood skin color variation. The dynamics make use of servo motors that rotate according to the value of their related mood. This performative piece is still a work in progress (see Figure 2). Generally students were positive about the course, though they were also quick to point out this was challenging. Students gave us feedback such as "I learned a lot about the process and execution of information visualization using the biomimicry methodology" and also talked to us about "the difficulty of abstracting and not simply cloning a biology-inspired thing". While some students were simply enthusiastic "Biomimicry is a great way for finding solutions to problems and the Infovis community can benefit by taking guidelines from it and applying them to the design of new visualization techniques", it was clear that this was a challenging approach.

All students entered enthusiastically into the process and attendance was close to 100%, with people -both other professors and other graduate students -partaking at times with permission. This was clearly both an exciting and innovative process as well as a challenging one. All students shifted the sources of bio-inspiration several times during the process. Students with even a small amount of art or creative background (artists, architects, etc.) performed very well and designed incredible bio-inspired visualizations (as seen in the examples above). Other students struggled with this and many had not arrived at a good fit between biology inspiration and the data they were working with. While they did manage to complete their projects they were clearly still searching, and as a result their project were less satisfying.

The complexity of the process, particularly for some students, would probably not make this a suitable approach for undergraduate students (although a more thorough intro to infovis and biomimcry replacing the guest lectures could be more appropriate to an undergraduate class). However, it is promising as an innovation process and definitely led to original and unique visualizations. It is also a way of integrating interdisciplinary work and of leveraging design, art, and computer science.

Finally, while our goal was to explore biomimicry, in reality our class more closely reflected bio-inspiration. In the larger technological world, including engineering and architecture, the advantages and potential of biomimicry are increasingly evident. Biomimicry was a term coined in 1997 in Benyus's book of the same name [START_REF] Benyus | Biomimicry: Innovation Inspired By Nature[END_REF]. Benyus, a biologist, tied the term directly to sustainability. Other terms, such as bioinspiration, biomimetics, and bionics, are closely related, but do not necessarily lead to a sustainable outcome. For example, engineers have looked at nature for inspiration for many centuries. Planes, engines, and the built environment are all inspired by nature, but not necessarily sustainable. Using benign manufacturing and sustainable life cycles is where biomimicry tries to separate itself from other areas of bio-inspired design. Within our class hours we did not have the time to explore the sustainability questions posed by the idea of biomimicry. Exactly what sustainability means in terms of visualization and whether biomimicry can help us achieve this remains an open challenge.

Figure 1 :

 1 Figure 1: Attitude towards HIV explored with Fireflies [6] by Bon Adriel Aseniero. On the left hand-drawn sketches explaining the swarm behaviour of graphical marks. On the right snapshots of the web-based application for exploring attitude towards HIV.

Figure 2 :

 2 Figure 2: Chameleon skin, music and mood by Roxane Fallah. The images on the left show bio-inspirations, with the skin of a chameleon changing colour according to its mood. The image on the right is the physical, ambient, dynamic installation that represents the mood conveyed by a song when played.

ACKNOWLEDGEMENTS

Thanks to support from NSERC, AITF, and SMART Technologies.


Fateme Rajabiyazdi

Charles Perin
email: charles.perin@ucalgary.ca

Sheelagh Carpendale
email: sheelagh@ucalgary.ca

WESt: Visualizing non-Emergency Surgery Waiting Times

Figure 1: WESt overview, 1) BC map representation and hospital waiting times as arcs, 2) scatter plot of physician/hospital attributes, 3) physicians and number of waiting cases

INTRODUCTION

Many visualizations on the web visualize health data, such as Mapsdata [START_REF]Mapping health data: GP waiting times[END_REF] showing the percentage of people who had to wait for a consultation in Greater London. Existing visualizations for exploring health-related waiting times usually focus on one dimension, time. However, these datasets have multiple facets, including geographical information and hospitals' and physicians' ratings.

Our visualization, WESt (available at http: //rajabiyazdi.com/BC-Surgery/) is unique in that it includes a variety of available datasets and represents these datasets in detail, in contrast to techniques which involve a one dimensional view that may hide important information. In order to represent this variety of datasets, our visualization includes multiple visualization techniques such as a choropleth map and a node-link diagram [START_REF] Ghoniem | A comparison of the readability of graphs using node-link and matrix-based representations[END_REF] providing a more complete view of the information. Finally, we employ various techniques to improve the accessibility and readability of our visualization such as zooming, overview and detail-on-demand [START_REF] Shneiderman | The eyes have it: A task by data type taxonomy for information visualizations[END_REF].

For this project, we focused on designing and developing a visualization for surgery waiting times, hospitals' and physicians' ratings, regions' populations, and the number of households in the province of BC. The purpose of the visualization is to represent surgery waiting times in order to: help people identify hospitals and physicians with least waiting time; and to facilitate the procedure of finding bottlenecks in surgical departments of the hospitals for hospital managers and the government.

BC SURGICAL AND STATISTIC DATA

In order to capture the complexity and the different factors when choosing where to get a surgery, we used four datasets in this visualization: BC surgery waiting times, BC statistic data, physicians' rating, and hospitals' rating. The surgery waiting times dataset 1shows information about wait times for non-emergency surgeries done throughout the province of BC in six regions: Fraser, Interior, Northern, Vancouver Island, Vancouver Coastal, and Provincial. The three main dimensions are: 1) number of cases waiting, 2) 50th percentile wait time in weeks, and 3) 90th percentile wait time in weeks. The second dataset contains the population estimate and number of households in BC regions 2 . The third dataset is the physicians' rating from the RateMD3 which is a public website where patients can rate physicians from one star to five stars. The last dataset, from the CBC website4 contains hospitals' rating.

When analyzing surgery waiting times, a patient might need to perform a number of tasks. Patient tasks might vary depending on their goal. From our previous experience, we created a list of tasks that we think are important for analyzing our dataset. Our proposed visualization assists patients in performing these tasks. Also, our visualization could help hospitals and the government analyze the hospital needs for equipment and allocate enough funding to balance surgery waiting lists. Below we list the tasks that we think are important for patients, hospitals, and government. For patients: P1 Find the nearby hospitals. P2 Find hospitals with fewer cases waiting for a surgery. P3 Compare hospitals' waiting times and ratings for a surgery. P4 Compare physicians' waiting times and ratings for a surgery. P5 Find physicians with fewer cases waiting for a surgery. For hospitals and government: H1 Compare a regions' population to its number of waiting cases. H2 Compare a regions' number of households to its number of waiting cases.

WESt VISUALIZATION

Our goal is to go beyond existing multi-dimensional and multityped tables from which it is difficult to get insights. To do this we sketched ideas, used visualization design guidelines [START_REF] Shneiderman | The eyes have it: A task by data type taxonomy for information visualizations[END_REF], and investigated visualizations for similar datasets. Then, we developed WESt by means of iterative design. The resulting visualization consists of an overview and a comparison view.

Overview

The overview (Figure 1) shows the hospital waiting times for a requested surgery. This view consists of three representations, driven by the extracted tasks: a map of BC, a scatter plot matrix, and a bar chart. The black dots on the map represent hospitals' locations to help patients find hospitals in their region (P1). To ease comparison between hospitals waiting time, the hospitals are represented by arcs on the circle periphery (P2). The length of each arc is computed by dividing each hospital waiting time by the total waiting time for the requested surgery among all and proportioned to 360°. The scatter plot matrix is used to represent all the hospitals attributes: number of cases waiting for the requested surgery since 31 March 2015, 50%, 90% completed cases waiting time (weeks), and hospitals' rating. This will ease the process of comparing hospitals (P3). On the left side of the view, one can change the scatter plot view from hospital to physician. This changes the scatter plot points' values to physicians' waiting time and rating (P4). Furthermore, by hovering over hospital's arc, highlighted hospital circles will become larger and more easily distinguishable.

The bar chart at the bottom shows all the physicians' name who perform the requested surgery and the number of cases waiting for them (P5). To fulfill H1 and H2, we added an option to choose regions' population and households in addition to color map. The choropleth technique is used for this view and the values are mapped based on the regions population or household numbers.

All three visualizations are linked, by hovering over any of the components in the overview page, the corresponding items, physicians' name, and hospital representations will be highlighted. Also, more detailed information such as number of cases waiting, 50%, and 90% completed cases waiting time will appear in a tooltip [START_REF] Shneiderman | The eyes have it: A task by data type taxonomy for information visualizations[END_REF].

Comparison view

One can click on hospitals in the overview to select these for comparison. This view gives an extra opportunity to compare hospitals and physicians in more detail. It consists of three main components: a map of BC with the selected hospitals to compare, a radar 2). The radar chart on the right represents the number of weeks in which 50% and 90% cases received their surgery, and the number of cases waiting. Hovering over any arc on the map highlights the corresponding triangular area in the radar chart.

In addition, one can look at the information about physicians operating in the selected hospitals. Each bar chart at the bottom of the comparison view shows the number of cases waiting for all the physicians in a hospital. We added hospitals' name to the bar chart legend to discriminate between hospitals with the same color. Also, the scale of the y-axis is set to the maximum scale among multiple bars, making it possible to compare in between charts.

DISCUSSION AND FUTURE WORK

We designed WESt with focus on patients' needs and we think patients usually look for one surgery at a time and are less likely to be interested in comparing different surgeries. That is why WESt is currently limited to showing only one surgery. However, this may be useful for hospitals or the government to compare waiting times of several surgeries and balance their facilities and human resources. In addition, our system loads data from the BC government website, however, some patients may not agree with the method hospitals use to report surgery waiting times. For example, hospitals do not take into account the waiting time to see a specialist and/or to run necessary diagnostic procedures before the surgery. As a result, future work could include allowing people to actively collaborate in this visualization by entering their own data on the website and contribute to the database [START_REF] Heer | Design considerations for collaborative visual analytics[END_REF].

Figure 2 :

 2 Figure 2: Comparison view: comparing selected hospitals in detail. 1) BC map representation with selected hospitals 2) radar chart of hospital attributes, 3) physicians' name and number of waiting cases

https://swt.hlth.gov.bc.ca/

http://www.bcstats.gov.bc.ca/StatisticsBySubject/ Demography.aspx

https://www.ratemds.com/bc/vancouver/

http://www.cbc.ca/news2/health/features/ ratemyhospital/hospitalratings.html

ACKNOWLEDGEMENTS

This research was supported in part by AITF, NSERC, GRAND, Surfnet, and SMART Technologies.


B Johnson

B C Correa

C Correa

C E Scheidegger

We detail the data collection and the visualization design, we give examples of insights one can get by looking at the visualization, and we discuss potential implications.

ABSTRACT

Members understanding the organization of a community is useful for any community. Correspondingly this applies to researchers involved in the Infovis community. We present Who Rules Infovis?, an infographic showing the temporal evolution of the internal organization of the Infovis conference. It shows all persons who have been a chair or in a related committee over the past 20 years and provides an understanding of the internal organization of the community.

INTRODUCTION

Any researcher willing to be involved in the community wants to understand how this community works, how persons access positions with responsibilities such as being a chair or in a particular committee, and how academic contributions such as publications play a role in this process. The community itself needs to grasp how it behaves over the years in order to question the organizational process and maybe make adjustments. Although the data is publicly available, understanding the internal politics is challenging and no guidelines exist for helping researchers achieve their goals. Our intent is to provide the dataset and an initial view on this dataset, hoping that other researchers will use this groundwork to contribute to a better understanding and transparency within the community, as this is the case with CiteVis [START_REF] Stasko | CiteVis: Exploring conference paper citation data visually[END_REF] for example.

To achieve this goal, we created a web-based visualization designed to understand the Infovis chair and committee evolution over the years (Figure 1), available at http://innovis.cpsc.ucalgary.

DATA COLLECTION AND FILTERING

The first step was to gather and filter the data. The main dimension of interest is the persons being part of a committee or being a chair at the conference, that we call roles. This information being only partly available online, we had to manually process some of the paper proceedings to complete the dataset. Some roles in the VIS conference are not exclusive to Infovis. We chose to remove the roles that are global to the conference, such as Student Volunteer and Finance Chairs, as well as exceptional roles such as Bertin Exhibit Chair at VIS 2014. The Program Committee (PC) being the core of the conference, we filtered out the persons who may have had a role in the conference but have never been in the PC, except before 2006. Therefore, some persons (e.g., Ben Fry, Alex Endert, and the first author of this poster) are not represented.

Since an important factor of involvement is the number of publications in the conference, we integrated the publications dataset [START_REF] Isenberg | Visualization publication dataset[END_REF]. In total, the dataset consists of 25 roles over 20 years for 223 persons.

VISUALIZATION DESIGN

We use position to map the two core dimensions: the roles at the conference and the year they were held. Role boxes are distributed on the vertical axis and time is mapped to the horizontal axis. The vertical center of role boxes is fixed to ensure layout stability over the years, and their ordering is determined according to the number of links (i.e. number of times one person connects two roles) between each pair of roles. It also makes it possible to add the legend for each role on the right side of the visualization. Only by looking at the size of each role colored box, one can already understand how the number of persons a role contains evolves over the years. The remaining graphical elements consist of persons. The name of each person is repeated every year and connected using bezier links. The font size and weight of the name encodes the number of roles this person had up to the current year, and the width of each link the number of publications at Infovis for the person up to the current year. Finally, the link color conveys the evolution of the person from year to the other: blue link means that the person got a role while he or she did not have any the previous year; a red link that the person got no role while he or she had one the previous year; and a gray link that the person had at least one role the previous year, and at least one role in the current year. A person appears the year before his or her first role, and disappears the year after his or her last role. If a person does not have a role a given year, he or she is assigned one of the vertical positions with no role (typically, the space between two role boxes). Because one person can have multiple roles for a given year, links split and merge accordingly. As a result, the name of one person can appear several times for one year. Finally, the algorithm minimizes the vertical variation locally for each person. The overall result is similar to the ones from Tanahashi et al. [START_REF] Tanahashi | An efficient framework for generating storyline visualizations from streaming data[END_REF][START_REF] Tanahashi | Design considerations for optimizing storyline visualizations[END_REF], inspired from XKCD storylines.

READING THE VISUALIZATION

By looking at the static infographic, one can make discoveries and get a better understanding of the internal organization of the conference. Here we discuss some observations at the overall information, intermediate, and elementary levels described by Bertin [START_REF] Bertin | Graphics and Graphic Information Processing[END_REF].

At the overall level, can observe that there was no PC in 1998 and 1999. Also, some roles disappear and others appear. For example, Late-Breaking Hot Topics Chair existed only in 2000-01, Interactive Demo Chair only in 2007-08, and Industry outreach Chair appeared in 2012. It also appears that the number of persons in the organization of the conference increased over the years.

At the intermediate level, one can the trends within roles over the years, by visually scanning the links' size and color, the links' direction, and the persons' font weight and size. For example, Figure 2 shows the PC members in 2014 and 2015. One can observe that people entering the PC (blue links) globally have a larger link width in 2014 than in 2015. Moreover, only few persons in the 2015 PC have a large link width. Finally, the names with the bolder and larger font in 2014 are not present in 2015. on these facts, it seems that the PC in 2015 is less experienced than the one in 2014, regarding both the number of publications and the number of roles PC members have had in the past. By simply estimating the sum of all links width and name sizes for a given year and a given role, one can evaluate the experience of the role members. Analyzing the rotation for each role is another interesting inquiry, as these rotations are supposed to follow rules (e.g., no more than three consecutive years as a PC member) which may be violated.

Finally, at the elementary level, one can inspect persons and analyze their path over the years in order to understand the mechanisms inside the conference organization. One may observe that three types of persons are involved in the Infovis conference organization. The balanced are those that equally publish and get involved. Visually, balanced persons are those whose name font width and size are proportional to the stroke width of the links connecting the name. Such people are Munzner, T., van Wijk, J.J., Isenberg, P. and Stasko, J. The organizers are those that do not publish a lot in Infovis but are recognized as being good organizers. They have a large name with thin links. For example, Keim, D.A. is the biggest and boldest name, but does not have the larger links: he is more involved in the community as an organizer than as an author. The same observation can be made for example for Ward, M.O. and Bartram, L. The publishers are those that publish a lot but are less involved in the organization. They have a small name with large links.

DISCUSSION

Although this visualization is designed to be analyzed in its static form, the online version features basic interactions (hovering over a person and selecting multiple persons to highlight them) and in the future we plan to increase the available features. For example, being able to formulate queries to filter out persons would provide a way of specifying meaningful requests and unclutter the visualization.

In the future, we plan to include VAST and Scivis data. It creates new challenges in terms of quantity of data to represent, but would provide interesting views about across-conferences relationships.

We are sure that this poster will trigger interesting conversations during the conference and may create some polemics. This is often the case when visualizing a dataset, although the data is publicly available. We hope that this initial work will encourage other researchers to pursue in this direction, towards more transparency and a deeper understanding of the internal processes of the conference.

Finally, this visualization focuses on the organizational structure of the Infovis conference along with its members. However, these persons are not the ones that ultimately rule Infovis. Accessing the data about influential and decision-taking groups would strengthen the visualization towards a better understanding of the community.

Figure 1 :

 1 Figure 1: Researcher roles from 1995 to 2015 in the Infovis conference. Persons are grouped by role (chair or member of a committee) each year. The font size and weight encode the number of roles a person had up to the current year. A red link represents a person leaving a role and a blue link a person entering a role. The stroke of links encodes the number of publications of a person at Infovis up to the current year.

Figure 2 :

 2 Figure 2: Program Committees for Infovis 2014 (left) and 2015 (right).

Senay, H. Senay, H. Senay, H. Senay, H. Senay, H. Senay, H. Senay, H. van de Wetering, H. van de Wetering, H. van de Wetering, H. van de Wetering, H. van de Wetering, H. van de Wetering, H. van de Wetering, H. van de Wetering, H. van de Wetering, H. van de Wetering, H.

ACKNOWLEDGMENTS

This research was supported in part by AITF, NSERC, GRAND, Surfnet, and SMART Technologies.


Bon Adriel Aseniero
email: baasenie@ucalgary.ca

Charles Perin
email: charles.perin@ucalgary.ca

Marjan Eggermont
email: meggermo@ucalgary.ca

Sheelagh Carpendale
email: sheelagh@ucalgary.ca

Fireflies: Biomimicry-Inspired InfoVis for Exploring Public Opinion about an Infectious Disease

We present Fireflies, an exploration of bio-inspired visualization using animal swarming behaviours and plant phyllotaxis. We applied Fireflies to a Canadian attitudinal survey on HIV/AIDS. Information about the survey participants is encoded within different visual elements of fireflies; most importantly, the motion of the fireflies depicts comfort levels concerning HIV/AIDS. The bio-inspired visual properties of Fireflies meld into an expressive representation of a sensitive dataset.

Each participant from the study is encoded as a firefly (coloured dot) whose motion depicts their comfort levels regarding HIV/AIDS. Fireflies are arranged randomly in 2D space, enticing individuals to interact with the visualization to make their own meaningful groupings.

INTRODUCTION

Biomimicry-derived from the Greek word bios, meaning "life", and mimesis, meaning "to imitate"-is an increasingly popular paradigm where one imitates solutions found in nature in order to solve day-to-day problems efficiently [START_REF] Benyus | Biomimicry : Innovation Inspired by Nature[END_REF]. This comes from the premise that nature (animals, plants, and microbes) offers solutions to problems that humans are still trying to solve-solutions that have undergone multiple iterations of testing and improvement, with failures already winnowed by natural selection.

Biomimicry has been applied to many engineering design challenges in the last decade: from minuscule syringe needles made less painful by copying mosquito proboscis [2], to enormous bullet trains made quiet by copying kingfisher beaks [START_REF] Kobayashi | JFS Bio-Mimicry Interview Series: No. 6 Technologies Learned from Living Things: 'Shinkansen Technology Learned from an Owl?'-The Story of Eiji Nakatsu[END_REF]. However, biomimicry's application to information processing is still under-explored. Hence, Fireflies (see Figure 1) is a preliminary exploration as to how biomimicry can be applied in information processing. In particular, we look into how inspirations from nature can be leveraged in order to encode data into a visual representation that enables people to explore complex data. We describe our process of applying biomimicry to the design of a visualization.

DATA

The data visualized in Fireflies comes from a 2012 Canadian HIV/AIDS attitudinal survey, which we retrieved from the Government of Canada's online data repository [START_REF]HIV/AIDS Attitudinal Tracking Survey[END_REF]. The dataset contains demographic information such as participants' age range and location, as well as whether they identify as members of Canada's aboriginal population who are disproportionately affected by HIV/AIDS [START_REF] Of | HIV/AIDS Epi Updates -July 2010[END_REF]. Furthermore, it includes information about participants' ideas or knowledge on how the virus spreads, and their opinions about the disease obtained through a series of questions regarding HIV/AIDS.

Given the nature of our dataset, we focused on participants' attitude towards HIV/AIDS. We measured this based on their answers to questions eliciting their opinions about HIV/AIDS. Some opinion questions required them to answer whether they agree or disagree with certain statements such as "I feel afraid of people living with HIV/AIDS." Other opinion questions required them to rate their comfort level (very uncomfortable to very comfortable) regarding hypothetical scenarios such as "How comfortable of uncomfortable would you be with a close friend or family member dating someone with HIV/AIDS?" After examining the dataset, we defined goals for designing an engaging visualization which is both visually expressive and useful for exploring this sensitive dataset. These goals include providing expressiveness through visual variables such as motion; enabling the creation of meaningful groups or clusters of data-points; and supporting conventional means of exploration such as sorting and querying. Our approach in achieving these goals was to use inspirations from nature.

One inspiration is animal flocking and swarming behaviour. The metaphor we used to allow people to make their own groupings of data-points is based off a naïve swarming behaviour of insects, where members of the swarm fly towards a food source (see Figure 2). People can place queries (as food sources) in the visualization space and the fireflies that meet the requirements get drawn to query's position. This interaction is similar to that in Dust & Magnets by Yi et al. [START_REF] Yi | Dust & Magnet: Multivariate Information Visualization Using a Magnet Metaphor[END_REF]. In their visualization, magnets-representing a query-are placed in the visual space and attract the dust-representing the data-points-that meet the requirements of the query. Those that do not meet the requirements are repelled. By applying bio-inspired algorithms, we introduce collision detection (loosely modelled after boids [START_REF] Reynolds | Flocks, Herds and Schools: A Distributed Behavioral Model[END_REF]).

We also made use of animal motion that depict their character to encode other aspects of the data. Motion can depict behavioural characteristics such as "aggressive" and "nonaggressive", "comfortable" and "uncomfortable." While these characteristics are seen in real-life animals, they may be less apparent in abstract representations (e.g., a circle representing an animal). Hence, we look at how we perceive apparent behaviour from animation [START_REF] Heider | An Experimental Study of Apparent Behavior[END_REF]. Aggressive behaviours are typically accompanied by fast and jittering actions, while nonaggressive behaviours are accompanied by slow and calm actions.

To create firefly clusters, we used a phyllotactic pattern based off the algorithm by Vogel [START_REF] Vogel | A Better Way to Construct the Sunflower Head[END_REF]. We used a 137.5° angle which mimics how sunflower seeds grow, giving us an efficient way of clustering undetermined numbers of fireflies.

FIREFLIES

The resulting visualization, Fireflies (Figure 1), visualizes a random sample of data-points as fireflies floating in space. During initialization, the fireflies are sprinkled randomly in the 2D space where the horizontal and vertical axes have no particular encoding. By freeing up these axes, people are unrestricted when creating their own meaningful groupings of the data-points in any area of the visualization. Each firefly's visual characteristics depict certain aspects about the participant:

1. Colour -the survey participants' location.

2. Opacity -the survey participants' age-range. Younger agerange is more opaque than older age-ranges. 3. Size -the participants' self-reported knowledge of HIV/AIDS. Smaller sizes mean lesser knowledge than bigger sizes. 4. Glyph -some fireflies have a ✦ diamond star symbolizing their membership to a Canadian aboriginal group. 5. Motion -the participants' attitude towards HIV/AIDS. More movement means more discomfort, while less movement mean less discomfort. Groupings of fireflies can be made with predefined sorting categories based on the participants' demographics. The right-hand side of the visualization shows a list of available sorting categories (location, age-range, knowledge, and attitude). Clicking on each will group the fireflies into clusters based on the category. Another way of grouping fireflies is to perform textual queries, for example, by typing "province=alberta" in the query box. Lastly, clicking on fireflies will pull other fireflies that are similar to it. Similarity is currently determined by participant age-range and knowledge level, however, we plan on using a more complex similarity algorithm (e.g., apriori algorithm) in the future. Clustered fireflies can also be moved around, allowing people to fine-tune the positions of their groupings.

CONCLUSION

Biomimicry is a great inspiration for finding solutions to problems. The InfoVis community can benefit from it and leverage biomimicry for designing new visualization techniques. We illustrated how this process can lead to expressive visualization metaphors in Fireflies. The apparent behaviour animation we used gives striking character to fireflies representing participants who have some discomfort towards HIV/AIDS. This allows the visualization to immediately give people an idea of the amount of discomforted participants at-a-glance. Furthermore, the enticing motion of the fireflies as they form clusters could engage people to look for other clusters to explore the dataset more thoroughly.

Our hope is that in the future, this preliminary exploration can be extended and generalized into a set of guidelines for applying biomimicry inspirations to InfoVis.

Figure 1 :

 1 Figure 1: A sprinkle of data-Fireflies is a biomimicry-inspired visualization depicting data from a 2012 Canadian HIV/AIDS attitudinal survey.Each participant from the study is encoded as a firefly (coloured dot) whose motion depicts their comfort levels regarding HIV/AIDS. Fireflies are arranged randomly in 2D space, enticing individuals to interact with the visualization to make their own meaningful groupings.

ACKNOWLEDGEMENTS

We would like to thank David Ledo for his contribution during the conception of this research work, as well as the following organizations for providing funding and equipment: Alberta Innovates Technology Futures (AITF), Natural Sciences and Engineering Research Council of Canada (NSERC), and SMART Technologies.